Every problem has a weakest failure detector

ABSTRACT

Several basic problems that arise in fault-tolerant distributed computing were shown to have a weakest failure detector. We show here that every problem that is solvable with a failure detector has a weakest failure detector.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Sam Toueg , Borislav Deianov, Revising the Weakest Failure Detector for Uniform Reliable Broadcast, Proceedings of the 13th International Symposium on Distributed Computing, p.19-33, September 27-29, 1999
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: 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]
• 4: 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]
• 5: 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]
• 6: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011818]
• 7: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Petr Kouznetsov, Mutual exclusion in asynchronous systems with failure detectors, Journal of Parallel and Distributed Computing, v.65 n.4, p.492-505, April 2005 [doi>10.1016/j.jpdc.2004.11.008]
• 8: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 9: 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]
• 10: Rachid Guerraoui, Michal Kapalka, and Petr Kouznetsov. The weakest failure detectors to boost obstruction-freedom. In DISC '06: Proceedings of the twentieth International Symposium on Distributed Computing, pages 399--412, LNCS vol. 4167. Springer-Verlag, September 2006.
• 11: Joseph Y. Halpern , Aleta Ricciardi, A knowledge-theoretic analysis of uniform distributed coordination and failure detectors, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.73-82, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301331]
• 12: 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]
• 13: Piotr Zielinski. Anti-omega: the weakest failure detector for set agreement. Technical Report UCAM-CL-TR-694, Computer Laboratory, University of Cambridge, Cambridge, UK, July 2007.

INDEX TERMS

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

Additional Classification:
  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: Computability theory

General Terms:
Algorithms, Reliability, Theory

Keywords:
asynchronous system, failure detector, fault-tolerance