Coordinated traversal: (t+1)-round Byzantine agreement in polynomial time
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 246-255
- https://doi.org/10.1109/sfcs.1988.21941
Abstract
The problem of efficiently performing Byzantine agreement in t+1 rounds in the face of arbitrarily malicious failures is treated. A communication-efficient polynomial-time protocol is presented for n>8t. The protocol is an early stopping protocol, halting in min(t+1, f+2) rounds in the worst case, where f is the number of processors that fail during the run. This is provably optimal. The protocol is based on a careful combination of early stopping, fault masking, and a technique called coordinated traversal. The combination of the three provides a powerful method for restricting the damage that a faulty processor, however malicious, can do. One of the byproducts of this protocol is a polynomial-time (t+1)-round protocol for the Byzantine firing squad problem.Keywords
This publication has 10 references indexed in Scilit:
- Programming simultaneous actions using common knowledgeAlgorithmica, 1988
- Shifting gears: changing algorithms on the fly to expedite Byzantine agreementPublished by Association for Computing Machinery (ACM) ,1987
- A communication-efficient canonical form for fault-tolerant distributed protocolsPublished by Association for Computing Machinery (ACM) ,1986
- Knowledge and Common Knowledge in a Byzantine Environment I: Crash failuresPublished by Elsevier ,1986
- Fast distributed agreement (preliminary version)Published by Association for Computing Machinery (ACM) ,1985
- The distributed firing squad problemPublished by Association for Computing Machinery (ACM) ,1985
- A lower bound for the time to assure interactive consistencyInformation Processing Letters, 1982
- Polynomial algorithms for multiple processor agreementPublished by Association for Computing Machinery (ACM) ,1982
- Cryptographic protocolsPublished by Association for Computing Machinery (ACM) ,1982
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980