|
 ABSTRACT
Reaching agreement in a distributed system while handling malfunctioning behavior is a central issue for reliable computer systems. All previous algorithms for reaching the agreement required an exponential number of messages to be sent, with or without authentication. We give polynomial algorithms for reaching (Byzantine) agreement, both with and without the use of authentication protocols. We also prove that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
W. Diffie and M. Hellman, "New direction in cryptography," IEEE Trans. on Inform. IT-22,6(1976), 644-654.
|
| |
2
|
D. Dolev, "The Byzantine Generals Strike Again," Journal of Algorithms, vol. 3, no. 1, 1982.
|
| |
3
|
D. Dolev, "Unanimity in an Unknown and Unreliable Environment," 22nd Annual Symposium on Foundations of Computer Science, pp. 159-168, 1981.
|
| |
4
|
D. Dolev and H. R. Strong, "Authenticated Algorithms for Byzantine Agreement," submitted for publication; see also "Polynomial algorithms for multiple processor agreement," IBM Research Report RJ3342 {1981).
|
| |
5
|
R. A. DeMillo, N. A. Lynch, and M. Merritt, "Cryptographic Protocols," in these proceedings.
|
| |
6
|
L. Lamport, "Using Time Instead of Timeout for Fault-Tolerant Distributed Systems," Technical Report, Computer Science Laboratory, SRI International, 1981.
|
 |
7
|
|
| |
8
|
N. Lynch, and M. Fischer, "A Lower Bound for the Time to Assure Interactive Consistency," submitted for publication.
|
| |
9
|
|
| |
10
|
|
CITED BY 39
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.89-103, August 17-19, 1983, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Amotz Bar-Noy , Danny Dolev , Cynthia Dwork , H. Raymond Strong, Shifting gears: changing algorithms on the fly to expedite Byzantine agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.42-51, August 10-12, 1987, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf