Summary
The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be\(O(\sqrt n )\), wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bar-Noy A, Dolev D: Consensus algorithms with one-bit messages. Distrib Comput 4:105–110 (1991)
Coan BA: Efficient agreement using fault diagnosis. Distrib Comput 7(2):87–98 (1993)
Dolev D, Reischuk R: Bounds on information exchange for Byzantine agreement. J ACM 32(1):191–204 (1985)
Dolev D, Reischuk R, Strong HR: Early stopping in Byzantine agreement. J ACM 37(4):720–741 (1990)
Fischer MJ, Lynch NA: A lower bound for the time to assure interactive consistency. Inf Process Lett 14:183–186 (1982)
Lamport L, Shostak R, Pease M: The Byzantine generals problem. ACM Trans Program Lang Syst 4(3):382–401 (1982)
Perry KJ: Early stopping protocols for fault-tolerant distributed agreement. Ph.D. dissertation, Cornell University, February 1985. Tech Rep 85-662, Department of Computer Science
Turpin R, Coan BA: Extending binary Byzantine agreement to multivalued Byzantine agreement. Inf Process Lett 18: 73–76 (1984)
Author information
Authors and Affiliations
Additional information
James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing, especially relating to problems of synchronization and fault tolerance.
Gil Neiger was born on February 19, 1957 in New York, New York. In June 1979, he received an A.B. in Mathematics and Psycholinguistics from Brown University in Proidence, Rhode Island. In February 1985, he spent two weeks picking cotton in Nicaragua in a brigade of international volunteers. In January 1986, he received an M.S. in Computer Science from Cornell University in Ithaca, New York and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. Since August 1988, he has been an Assistant Professor in the College of Computing (formely School of Information and Computer Science) at the Georgia Institute of Technology in Atlanta, Georgia. Dr. Neiger is a member of the editorial board of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.
This author was supported in part by the National Science Foundation under grants CCR-8909663, CCR-9106627, and CCR-9301454.
Rights and permissions
About this article
Cite this article
Burns, J.E., Neiger, G. Fast and simple distributed consensus. Distrib Comput 8, 59–64 (1994). https://doi.org/10.1007/BF02280828
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02280828