Towards optimal distributed consensus
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 410-415
- https://doi.org/10.1109/sfcs.1989.63511
Abstract
In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t+1, t+1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n>4t, r=t+1, and polynomial message size. The second protocol has n>3t, r=3t+3, and m=2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions.Keywords
This publication has 9 references indexed in Scilit:
- Families of consensus algorithmsPublished by Springer Nature ,2006
- Modular construction of nearly optimal Byzantine agreement protocolsPublished by Association for Computing Machinery (ACM) ,1989
- Coordinated traversal: (t+1)-round Byzantine agreement in polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Fast Distributed AgreementSIAM Journal on Computing, 1987
- 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
- Bounds on information exchange for Byzantine agreementJournal of the ACM, 1985
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982
- Polynomial algorithms for multiple processor agreementPublished by Association for Computing Machinery (ACM) ,1982