skip to main content
article

Illustrating the impossibility of crash-tolerant consensus in asynchronous systems

Published: 01 April 2006 Publication History

Abstract

This exercise shows how a simple restricted algorithm can be used to present an introductory discussion on the crash-tolerant consensus problem in asynchronous distributed systems. This text is intended to support teaching the consensus problem in courses on distributed systems.

References

[1]
M. Barborak, A. Dahbura, and M. Malek. The consensus problem in fault-tolerant computing. ACM Computing Surveys, 25(2):171--220, June 1993.
[2]
M. Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In Proc. Annual ACM Symposium on Principles of Distributed Computing, pages 27--30, 1983.
[3]
T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685--722, July 1996.
[4]
T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, Mar. 1996.
[5]
C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, Apr. 1988.
[6]
M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, Apr. 1985.
[7]
A. Mostefaoui, S. Rajsbaum, and M. Raynal. Conditions on input vectors for consensus solvability in asynchronous distributed systems. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 153--162. ACM Press, 2001.
[8]
J. Turek and D. Shasha. The many faces of consensus in distributed systems. IEEE Computer, 25(6):8--17, June 1992.
[9]
H. Völzer. A constructive proof for FLP. Information Processing Letters, 92:83--87, 2004.

Cited By

View all
  • (2011)The failure detector abstractionACM Computing Surveys10.1145/1883612.188361643:2(1-40)Online publication date: 4-Feb-2011
  • (2010)When consensus meets self-stabilizationJournal of Computer and System Sciences10.1016/j.jcss.2010.05.00576:8(884-900)Online publication date: 1-Dec-2010
  • (2006)When consensus meets self-stabilizationProceedings of the 10th international conference on Principles of Distributed Systems10.1007/11945529_5(45-63)Online publication date: 12-Dec-2006

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review
ACM SIGOPS Operating Systems Review  Volume 40, Issue 2
April 2006
107 pages
ISSN:0163-5980
DOI:10.1145/1131322
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2006
Published in SIGOPS Volume 40, Issue 2

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2011)The failure detector abstractionACM Computing Surveys10.1145/1883612.188361643:2(1-40)Online publication date: 4-Feb-2011
  • (2010)When consensus meets self-stabilizationJournal of Computer and System Sciences10.1016/j.jcss.2010.05.00576:8(884-900)Online publication date: 1-Dec-2010
  • (2006)When consensus meets self-stabilizationProceedings of the 10th international conference on Principles of Distributed Systems10.1007/11945529_5(45-63)Online publication date: 12-Dec-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media