The weakest failure detectors to solve certain fundamental problems in distributed computing

ABSTRACT

We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments -- i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.

REFERENCES

• 1: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 2: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 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: B. Charron-Bost and S. Toueg. Unpublished notes, 2001.
• 6: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui, Failure Detection Lower Bounds on Registers and Consensus, Proceedings of the 16th International Conference on Distributed Computing, p.237-251, October 28-30, 2002
• 7: C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Shared memory vs. message passing. Technical Report IC/2003/77, EPFL, Dec. 2003. Availabe at http://icwww.epfl.ch/publications/.
• 8: 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]
• 9: On Classes of Problems in Asynchronous Distributed Systems with Process Crashes, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.470, May 31-June 04, 1999
• 10: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 11: Rachid Guerraoui, Non-blocking atomic commit in asynchronous distributed systems with failure detectors, Distributed Computing, v.15 n.1, p.17-25, January 2002 [doi>10.1007/s446-002-8027-4]
• 12: R. Guerraoui, V. Hadzilacos, P. Kouznetsov, and S. Toueg. The weakest failure detectors for quittable consensus and non-blocking atomic commit. Technical report, LPD, EPFL, 2004. Availabe at http://lpdwww.epfl.ch/publications/.
• 13: Rachid Guerraoui , Petr Kouznetsov, On the Weakest Failure Detector for Non-Blocking Atomic Commit, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.461-473, August 25-30, 2002
• 14: Vassos Hadzilacos, On the Relationship Between the Atomic Commitment and Consensus Problems, Proceedings of the Asilomar Workshop on Fault-Tolerant Distributed Computing, p.201-208, January 1990
• 15: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 16: Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993 [doi>10.1007/BF02242708]
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: L. Lamport. On interprocess communication--Part I: Basic Formalism, Part II: Algorithms. Distributed Computing, 1,2(2):87--103, 1986.
• 19: Wai-Kau Lo , Vassos Hadzilacos, Using Failure Detectors to Solve Consensus in Asynchronous Sharde-Memory Systems (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.280-295, September 29-October 01, 1994
• 20: Achour Mostefaoui , Michel Raynal , Frédéric Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters, v.73 n.5-6, p.207-212, March 2000 [doi>10.1016/S0020-0190(00)00027-2]
• 21: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 22: D. Skeen. Crash Recovery in a Distributed Database System. PhD thesis, University of California at Berkeley, May 1982. Technical Memorandum UCB/ERL M82/45.
• 23: P. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proceedings of the 27th Symposium on Foundations of Computer Science, pages 233--246, 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases; Network operating systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Relations between models

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency; Transaction processing; Distributed databases

General Terms:
Algorithms, Reliability, Theory

Keywords:
consensus, non-blocking atomic commit, quittable consensus, register, weakest failure detector