On the nonexistence of resilient consensus protocols (Q756398)

\textit{M. J. Fischer, N. A. Lynch} and \textit{M. S. Paterson} [J. Assoc. Comput. Mach. 32, 374-382 (1985; Zbl 0629.68027)] proved that in asynchronous message passing systems there cannot exist a consensus protocol that tolerates even a single undetectable crash failure. Their proof of this fundamental result relies on operational details such as sending and receiving messages, etc. \textit{M. Chandy} and \textit{J. Misra} [ACM Trans. Program. Lang. Syst. 8, 326-343 (1986; Zbl 0598.68031)] have taken an axiomatic nonoperational approach to the consensus problem. Their idea is to define asynchronous systems and consensus protocols by a set of axioms, making no mention of operational details. The result of Chandy and Misra is weaker than that of Fischer, Lynch and Paterson, since it is not assumed, that all messages sent are eventually delivered. We use the Chandy and Misra approach to prove a result that is similar to the one of Fischer, Lynch and Paterson. We present three axioms capturing the nature of asynchronous message passing systems and five axioms defining resilient consensus protocols. We then prove that there does not exist an asynchronous resilient consensus protocol by showing that the set of eight axioms is inconsistent.