Abstract
We consider asynchronous shared memory distributed systems, and investigate coordination problems in this model. We provide a waitfree randomized consensus protocol that requires an expected O(n2 log n) atomic operations.
This research was partially supported by the U.S.-Israel bi-national science foundation grant 88-00282.
Preview
Unable to display preview. Download preview PDF.
References
K. Abrahamson, On achieving consensus using a shared memory, Proc. of the 7th ACM Symp. on Principles of Distributed Computing, August 1988, pp. 291–302.
J. Aspnes, Time and space-efficient randomized consensus, Proc. of the 9th ACM Symp. on Principles of Distributed Computing, August 1990, pp. 325–331.
J. Aspnes and M. Herlihy, Fast randomized consensus using shared memory, Journal of algorithms, September 1990, pp. 441–461.
H. Attiya, D. Dolev, and N. Shavit, Bounded polynomial randomized consensus, Proc. of the 8th ACM Symp. on Principles of Distributed Computing, August 1989, pp. 281–294.
H. Attiya, N. Lynch, and N. Shavit, Are Wait-Free Algorithms Fast? Proc. of the 31st IEEE Symp. on Foundations of Computer Science, 1990.
G. Bracha and O. Rachman. Approximated Counters and Randomized Consensus. In Technical Report #662, Computer Science Department, Technion, Haifa, Israel. December 1990.
B. Chor, A. Israeli, and M. Li, On processor coordination using asynchronous hardware, Proc. of the 6th ACM Symp. on Principles of Distributed Computing, August 1987, pp. 86–97.
D. Dolev, C. Dwork, and L. Stockmeyer, On the minimal synchrony needed for distributed consensus, Journal of the ACM, Vol. 34, No 1, January 1987, pp. 77–97.
M. Herlihy, Wait Free Implementations of Concurrent Objects, Proc. of the 7th ACM Symp. on Principles of Distributed Computing, 1988, pp. 276–290.
L. Lamport, On interprocess communication, Distributed Computing 1,2, 1986, pp. 77–101.
M. Loui and H. Abu-Amara, Memory requirements for agreement among unreliable asynchronous processes, Advances in Computing Research, Vol. 4, JAI Press, Inc., 1987, 163–183.
M. Saks, N. Shavit and H. Woll, Optimal time randomized consensus-making resilient algorithms fast in practice, Proc. 2nd ACM Symp. on Discrete Algorithms, January 1991, pp. 351–362.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bracha, G., Rachman, O. (1992). Randomized consensus in expected O(n2log n) operations. 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/BFb0022443
Download citation
DOI: https://doi.org/10.1007/BFb0022443
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