On the minimal synchronism needed for distributed consensus
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 393-402
- https://doi.org/10.1109/sfcs.1983.41
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Randomized byzantine generalsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Resilient consensus protocolsPublished by Association for Computing Machinery (ACM) ,1983
- Impossibility of distributed consensus with one faulty processPublished by Association for Computing Machinery (ACM) ,1983
- 'Eventual' is earlier than 'immediate'Published by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982
- Polynomial algorithms for multiple processor agreementPublished by Association for Computing Machinery (ACM) ,1982
- Bounds on information exchange for Byzantine AgreementPublished by Association for Computing Machinery (ACM) ,1982
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980