Illustrating the impossibility of crash-tolerant consensus in asynchronous systems

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: Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993 [doi>10.1145/152610.152612]
• 2: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 3: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 4: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 5: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 6: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 7: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece [doi>10.1145/380752.380792]
• 8: John Turek , Dennis Shasha, The Many Faces of Consensus in Distributed Systems, Computer, v.25 n.6, p.8-17, June 1992 [doi>10.1109/2.153253]
• 9: Hagen Völzer, A constructive proof for FLP, Information Processing Letters, v.92 n.2, p.83-87, 31 October 2004 [doi>10.1016/j.ipl.2004.06.008]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms