Abstract
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 Θ(n 3).
This work was partially supported by AFOSR contract 87-0400 and NSF grant CR 8805978.
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
B. Bollobás, "Random Graphs", Combinatorics, London Math. Society Lect. Notes 52, Cambridge University Press, 1981, pp. 80–102.
A. Bar-Noy and D. Dolev, "Families of Consensus Algorithms", Proc. 3rd. Aegean Workshop on Computing, June/July 1988, pp. 380–390.
A. Bar-Noy, D. Dolev, C. Dwork and H.R. Strong, "Shifting gears: changing algorithms on the fly to expedite Byzantine Agreement", Proc. 6th. Annual ACM Symp. on Principles of Distributed Computing, pp. 42–51, August 1987.
P. Berman, J. Garay and K. Perry, "Asymptotically Optimal Distributed Consensus with Optimal Resiliency", The Pennsylvania State University, Computer Science Department Tech. Report CS-89-08, March 1989.
B. Coan, "A communication-efficient canonical form for fault-tolerant distributed protocols", Proc. 5th. Annual ACM Symp. on Principles of Distributed Computing, pp. 63–72, August 1986.
B. Coan, "Efficient agreement using fault diagnosis", personal communication, to appear in Proc. 26th. Annual Allerton Conference on Communication, Control and Computing, September 1988.
C. Dwork, D. Peleg, N. Pippenger and E. Upfal, "Fault tolerance in networks of bounded degree", Proc. 18th. ACM Symp. on Theory of Computing, pp. 370–379, May 1986.
D. Dolev, R. Reischuk and H.R. Strong, "Early Stopping in Byzantine Agreement", IBM Research Report RJ5406-55357, 1986.
D. Dolev and H.R.Strong, "Polynomial Algorithms for Multiple Processor Agreement", Proc. 14th. Annual ACM Symp. on Theory of Computing, pp. 401–407, May 1982.
L. Lamport, R.E. Shostak and M. Pease, "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, pp. 382–401, July 1982.
Y. Moses and O. Waarts, "Coordinated Traversal: (t+1)-Round Byzantine Agreement in Polynomial Time", Proc. 20th. Annual ACM Symp. on Theory of Computing, pp. 246–255, May 1988.
S. Toueg, K.J. Perry and T.K. Srikanth, "Fast Distributed Agreement", SIAM Journal on Computing, Vol. 16, No. 3, pp. 445–458, June 1987.
J.D. Ullman, "Computational Aspects of VLSI", Computer Science Press, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berman, P., Garay, J.A. (1989). Asymptotically optimal distributed consensus. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds) Automata, Languages and Programming. ICALP 1989. Lecture Notes in Computer Science, vol 372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035753
Download citation
DOI: https://doi.org/10.1007/BFb0035753
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51371-1
Online ISBN: 978-3-540-46201-9
eBook Packages: Springer Book Archive