TY - GEN
T1 - Asymptotically optimal distributed consensus
T2 - 16th International Colloquium on Automata, Languages and Programming, 1989
AU - Berman, Piotr
AU - Garay, Juan A.
N1 - Funding Information:
t "ntis work was partially supported by AFOSR contract 87-0400 and NSF grant CR 8805978. $ Author's current address: Department of Computer Science, The University of Chicago, Ryerson Hall, Chicago, IL 60637.
Publisher Copyright:
© 1989, Springer-Verlag.
PY - 1989
Y1 - 1989
N2 - The Distributed Consensus problem requires correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. In this paper we present a protocol that achieves consensus with n>4t total processors using 2t+2 rounds of communication and messages of size 1. This is the first protocol in which all three parameters are simultaneously within a constant factor from their optima. Subsequently, we modify it to obtain a family of equally resilient protocols which use t(1 + 1/d) rounds and O(2d) message size, improving on previous results. Finally, we show that the first protocol can be adapted very efficiently to run on bounded-degree networks, so that consensus can be reached in the presence of O(n/log n) faulty processors in time O(n). It improves on the previous result, which implied that consensus can be reached in this setting in time Θ(n3).
AB - The Distributed Consensus problem requires correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. In this paper we present a protocol that achieves consensus with n>4t total processors using 2t+2 rounds of communication and messages of size 1. This is the first protocol in which all three parameters are simultaneously within a constant factor from their optima. Subsequently, we modify it to obtain a family of equally resilient protocols which use t(1 + 1/d) rounds and O(2d) message size, improving on previous results. Finally, we show that the first protocol can be adapted very efficiently to run on bounded-degree networks, so that consensus can be reached in the presence of O(n/log n) faulty processors in time O(n). It improves on the previous result, which implied that consensus can be reached in this setting in time Θ(n3).
UR - http://www.scopus.com/inward/record.url?scp=85034213702&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034213702&partnerID=8YFLogxK
U2 - 10.1007/BFb0035753
DO - 10.1007/BFb0035753
M3 - Conference contribution
AN - SCOPUS:85034213702
SN - 9783540513711
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 80
EP - 94
BT - Automata, Languages and Programming - 16th International Colloquium, Proceedings
A2 - Dezani-Ciancaglini, Mariangiola
A2 - Della Rocca, Simonetta Ronchi
A2 - Ausiello, Giorgio
PB - Springer Verlag
Y2 - 11 July 1989 through 15 July 1989
ER -