Abstract
Chandra and Toueg proposed a new approach to overcome the impossibility of reaching consensus in asynchronous message-passing systems subject to crash failures [6]. They augment the asynchronous message-passing system with a (possibly unreliable) failure detector. Informally, a failure detector provides some information about the processes that have crashed during an execution of the system. In this paper, we present several Consensus algorithms using different types failure detectors in asynchronous shared-memory systems. We also prove several lower bounds and impossibility results regarding solving Consensus using failure detectors in asynchronous shared-memory systems.
Supported by a Canadian Commonwealth Scholarship.
Supported, in part, by a grant from the Natural Sciences and Enginerring Research Council of Canada.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt and Nir Shavit. Atomic snapshots of shared memory. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, pages 1–13, August 1990.
Yehuda Afek, David S. Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with faulty shared memory. In Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pages 47–58, August 1992.
James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11:441–461, 1990.
Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocol. In Proceedings of the 2th ACM Symposium on Principles of Distributed Computing, pages 27–30, August 1983.
Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. In Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, August 1992. Also Technical report, Department of Computer Science, Cornell University, 1993, Ithaca, NY 14853-7501.
Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for asynchronous systems. In Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, August 1991.
Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77–97, January 1987.
Faith Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, pages 241–249, August 1993.
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the Association for Computing Machinery, 32(2):374–382, April 1985.
Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. Fault-tolerant wait-free shared objects. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992.
Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. In Advances in Computer Research, volume 4, pages 163–183. JAI Press Inc., 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lo, WK., Hadzilacos, V. (1994). Using failure detectors to solve consensus in asynchronous shared-memory systems. In: Tel, G., Vitányi, P. (eds) Distributed Algorithms. WDAG 1994. Lecture Notes in Computer Science, vol 857. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020440
Download citation
DOI: https://doi.org/10.1007/BFb0020440
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58449-0
Online ISBN: 978-3-540-48799-9
eBook Packages: Springer Book Archive