On the nonexistence of resilient consensus protocols

DOI10.1016/0020-0190(91)90221-3MaRDI QIDQ756398zbMATH OpenOpenAlexFDO

Authors Gadi Taubenfeld

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(91)90221-3

zbMATH Keywords

asynchronous message passing systemscrash failurefault toleranceimpossibility proofresilient consensus protocol

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Review text

\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.

Recommendations

• Asynchronous consensus and broadcast protocols
• Impossibility of distributed consensus with one faulty process
• Randomized protocols for asynchronous consensus
• Asynchronous byzantine agreement protocols
• Lower bounds for asynchronous consensus

Cites work

• How processes learn
• scientific article; zbMATH DE number 4205964 (Why is no real title available?)
• Impossibility of distributed consensus with one faulty process

Cited in

(14)

• Knowledge in shared memory systems.
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• The computational structure of progress conditions and shared objects
• The deformed consensus protocol
• scientific article; zbMATH DE number 4205964 (Why is no real title available?)
• Consensus in the presence of mortal Byzantine faulty processes
• scientific article; zbMATH DE number 7561269 (Why is no real title available?)
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• Randomized protocols for asynchronous consensus
• The fault span of crash failures
• The Complexity Gap between Consensus and Safe-Consensus
• General resilient consensus algorithms
• Resilient consensus for infinitely many processes. (Extended abstract)
• A constructive proof for FLP

This page was built for publication: On the nonexistence of resilient consensus protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756398)