Towards Optimal Distributed Consensus (Extended 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. >

Authors

• Piotr Berman
• Juan A. Garay 0001
• Kenneth J. Perry

Keywords

• Protocols
• Polynomials
• Computer networks
• Computer science
• Voting
• Length measurement
• Fault tolerance
• Distributed control
• Process control
• Contracts
• Final Value
• Default Values
• End Of Phase
• Early Stopping
• Question Format
• Application Of Rules
• Child Nodes
• Arithmetic Operations
• End Of Round
• Formal Statement
• Subsequent Ones
• Node Formation
• Number Of Processors
• Department Of Computer Science
• Message Size
• Protocol Execution
• Beginning Of Each Round
• Quality Protocols