Simple constant-time consensus protocols in realistic failure models
- 1 July 1989
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 36 (3) , 591-614
- https://doi.org/10.1145/65950.65956
Abstract
Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.Keywords
This publication has 13 references indexed in Scilit:
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- RSA and Rabin Functions: Certain Parts are as Hard as the WholeSIAM Journal on Computing, 1988
- An O (log n ) expected rounds randomized byzantine generals protocolJournal of the ACM, 1987
- Complexity of network synchronizationJournal of the ACM, 1985
- Asynchronous consensus and broadcast protocolsJournal of the ACM, 1985
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- Vulnerabilities of network control protocolsACM SIGSOFT Software Engineering Notes, 1981
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980
- How to share a secretCommunications of the ACM, 1979