On the Minimal Synchronism Needed for Distributed Consensus

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

Authors

• Danny Dolev
• Cynthia Dwork
• Larry J. Stockmeyer

Keywords

• Protocols
• Computer science
• Synchronization
• Laboratories
• Communication systems
• Distributed computing
• Fault diagnosis
• Clocks
• Upper bound
• Consensus Protocol
• Amount Of Time
• Proof Of Theorem
• Reachable
• Correction Algorithm
• Strong Consensus
• Decision Value
• Asynchronous Communication
• Synchronous Communication
• Message Sender
• Atomic Steps