Abstract
Are randomized consensus algorithms more powerful than deterministic ones? Seemingly so, since randomized algorithms exist that reach consensus in expected constant number of rounds, whereas the deterministic counterparts are constrained by the r ≥ t + 1 lower bound in the number of communication rounds, where t is the maximum number of faults to be tolerated.
In this paper, however, we study the behavior of deterministic algorithms when consensus is repeatedly needed, say k times. We show that it is possible to achieve consensus with the optimal number of processors (n > 3t), and optimal amortized cost in all other measures: the number of communication rounds r*, the maximal message size m*, and the total bit complexity b*.
More specifically, we achieve the following amortized bounds for k consensus instances: r*=O(1 + t/k), b*=O(t2 + t1/k), and m*=O(1 + t2/k). When k ≥ t2, then r* and m* are O(1) and b*=O(t2) which is optimal.
Work of second and fourth authors partially supported by the NSERC (Natural Sciences and Engineering Research Council of Canada) International Postdoctoral Fellowship and research grants from the NSERC and the Advanced Systems Institute of British Columbia.
This work was carried out while this author was at the School of Computing Science, Simon Fraser University.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Bar-Noy and D. Dolev, “Consensus Algorithms with One-Bit Messages,” Distributed Computing, Vol 4, pp. 105–110, 1991.
A. Bar-Noy, D. Dolev, C. Dwork, and H. R. Strong, “Shifting Gears: Changing Algorithms on the Fly to Expedite Byzantine Agreement,” Proc. 6th ACM Symp. of Principles of Dist. Computing, pp. 42–51, 1987.
M. Ben-Or and R. El-Yaniv, “Interactive Consistency in Constant Time,” unpublished manuscript.
P. Berman and J. A. Garay, “Asymptotically Optimal Distributed Consensus,” Proc. ICALP 89, LNCS Vol. 372, pp. 80–94, 1989.
P. Berman, J. A. Garay, and K. J. Perry, “Asymptotically Optimal Early-Stopping Consensus,” IBM Research Report, in preparation.
D. Dolev and R. Reischuk, “Bounds of Information Exchange for Byzantine Agreement,” JACM, Vol. 32, pp. 191–204, 1985.
D. Dolev, R. Reischuk, and H.R. Strong, “Eventual is Earlier than Immediate,” Proc. 23rd Symp. on Foundations of Comp. Science, pp.196–203, 1982. Revised version appears under the title, “Early-Stopping in Byzantine Agreement,” JACM, Vol.37, pp. 720–741, 1990.
M.J. Fischer and N.A. Lynch, “A Lower Bound for the Time to Assure Interactive Consistency,” Information Processing Letters, Vol. 14, pp.183–186, 1982.
P. Feldman, and S. Micali, “Optimal Algorithms for Byzantine Agreement,” Proc. 20th Symposium on Theory of Computing, pp. 148–161, 1988.
M. Pease, R. Shostak, and L. Lamport, “Reaching Agreement in the Presence of Faults,” Journal of the ACM, Vol. 27, pp. 228–234, 1980.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Noy, A., Deng, X., Garay, J.A., Kameda, T. (1992). Optimal amortized distributed consensus. In: Toueg, S., Spirakis, P.G., Kirousis, L. (eds) Distributed Algorithms. WDAG 1991. Lecture Notes in Computer Science, vol 579. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022440
Download citation
DOI: https://doi.org/10.1007/BFb0022440
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55236-9
Online ISBN: 978-3-540-46789-2
eBook Packages: Springer Book Archive