A short introduction to failure detectors for asynchronous distributed systems

ABSTRACT

Since the first version of Chandra and Toueg's seminal paper titled "Unreliable failure detectors for reliable distributed systems" in 1991, the failure detector concept has been extensively studied and investigated. This is not at all surprising as failure detection is pervasive in the design, the analysis and the implementation of a lot of fault-tolerant distributed algorithms that constitute the core of distributed system middleware.The literature on this topic is mostly technical and appears mainly in theoretically inclined journals and conferences. The aim of this paper is to offer an introductory survey to the failure detector concept for readers who are not familiar with it and want to quickly understand its aim, its basic principles, its power and limitations. To attain this goal, the paper first describes the motivations that underlie the concept, and then surveys several distributed computing problems showing how they can be solved with the help of an appropriate failure detector. So, this short paper presents motivations, concepts, problems, definitions, and algorithms. It does not contain proofs. It is aimed at people who want to understand basics of failure detectors.

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: Marcos Kawazoe Aguilera. , Wei Chen , Sam Toueg, On Quiescent Reliable Communication, SIAM Journal on Computing, v.29 n.6, p.2040-2073, April 2000 [doi>10.1137/S0097539798341296]
• 3: Marcos Kawazoe Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Thrifty Generic Broadcast, Proceedings of the 14th International Conference on Distributed Computing, p.268-282, October 04-06, 2000
• 4: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872081]
• 5: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, 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.1011816]
• 6: Marcos Kawazoe Aguilera , Gérard Le Lann , Sam Toueg, On the Impact of Fast Failure Detectors on Real-Time Fault-Tolerant Systems, Proceedings of the 16th International Conference on Distributed Computing, p.354-370, October 28-30, 2002
• 7: Marcos Kawazoe Aguilera , Sam Toueg, Failure Detection and Randomization: A Hybrid Approach to Solve Consensus, SIAM Journal on Computing, v.28 n.3, p.890-903, Feb. 1999 [doi>10.1137/S0097539796312915]
• 8: 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
• 9: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 10: 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]
• 11: Marin Bertier , Olivier Marin , Pierre Sens, Implementation and Performance Evaluation of an Adaptable Failure Detector, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.354-363, June 23-26, 2002
• 12: 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]
• 13: 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]
• 14: Wei Chen , Sam Toueg , Marcos Kawazoe Aguilera, On the Quality of Service of Failure Detectors, IEEE Transactions on Computers, v.51 n.5, p.561-580, May 2002 [doi>10.1109/TC.2002.1004595]
• 15: Chor M., and Dwork C., Randomization in Byzantine Agreement. Adv. in Comp. Research, 5:443--497, 1989.
• 16: Francis Chu, Reducing &OHgr; to ◊W , Information Processing Letters, v.67 n.6, p.289-293, Sept. 30, 1998 [doi>10.1016/S0020-0190(98)00122-7]
• 17: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui, A Realistic Look At Failure Detectors, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.345-353, June 23-26, 2002
• 18: 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
• 19: Delporte-Gallet C., Fauconnier H. and Guerraoui R., Shared memory vs Message Passing. Tech Report IC/2003/77, EPFL, Lausanne, December 2003.
• 20: 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]
• 21: Delporte-Gallet C., Fauconnier H., Helary J.-M. and Raynal M. Early Stopping in Global Data Computation. IEEE Transactions on Parallel and Distributed Systems, 14(9):909--921, 2003.
• 22: Christol Fetzer , Michel Raynal , Frederic Tronel, An Adaptive Failure Detection Protocol, Proceedings of the 2001 Pacific Rim International Symposium on Dependable Computing, p.146, December 17-19, 2001
• 23: 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]
• 24: Roy Friedman , Achour Mostefaoui , Michel Raynal, A weakest failure detector-based asynchronous consensus protocol for f < n, Information Processing Letters, v.90 n.1, p.39-46, 15 April 2004 [doi>10.1016/j.ipl.2004.01.001]
• 25: 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
• 26: Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343630]
• 27: 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]
• 28: 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
• 29: Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004 [doi>10.1109/TC.2004.1268403]
• 30: Indranil Gupta , Tushar D. Chandra , Germán S. Goldszmidt, On scalable and efficient distributed failure detectors, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.170-179, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384010]
• 31: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 32: J.-M. Hélary , M. Hurfin , A. Mostefaoui , M. Raynal , F. Tronel, Computing Global Functions in Asynchronous Distributed Systems with Perfect Failure Detectors, IEEE Transactions on Parallel and Distributed Systems, v.11 n.9, p.897-909, September 2000 [doi>10.1109/71.879773]
• 33: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 34: M. Hurfin , A. Mostéfaoui , M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors, IEEE Transactions on Computers, v.51 n.4, p.395-408, April 2002 [doi>10.1109/12.995450]
• 35: Michel Hurfin , Michel Raynal, A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, v.12 n.4, p.209-223, September 1999 [doi>10.1007/s004460050067]
• 36: Richard Koo , Sam Toueg, Effects of message loss on the termination of distributed protocols, Information Processing Letters, v.27 n.4, p.181-188, April 8, 1988 [doi>10.1016/0020-0190(88)90023-3]
• 37: Lamport L., Proving the Correctness of Multiprocess Programs. IEEE Transactions on Software Engineering, SE-3(2):125--143, 1977.
• 38: Mikel Larrea , Sergio Arévalo , Antonio Fernández, Efficient Algorithms to Implement Unreliable Failure Detectors in Partially Synchronous Systems, Proceedings of the 13th International Symposium on Distributed Computing, p.34-48, September 27-29, 1999
• 39: Mikel Larrea , Antonio Fernández , Sergio Arévalo, Optimal Implementation of the Weakest Failure Detector for Solving Consensus, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.52, October 16-18, 2000
• 40: Achour Mostefaoui , Eric Mourgaya , Michel Raynal, An introduction to oracles for asynchronous distributed systems, Future Generation Computer Systems, v.18 n.6, p.757-767, May 2002 [doi>10.1016/S0167-739X(02)00048-1]
• 41: Mostefaoui A., Mourgaya E., and Raynal M., Asynchronous Implementation of Failure Detectors. Proc. Int. IEEE Conference on Dependable Systems and Networks (DSN'03), IEEE Computer Society Press, pp. 351--360, San Francisco (CA), 2003.
• 42: Achour Mostefaoui , David Powell , Michel Raynal, A Hybrid Approach for Building Eventually Accurate Failure Detectors, Proceedings of the 10th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'04), p.57-65, March 03-05, 2004
• 43: Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal, A Versatile and Modular Consensus Protoco, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.364-373, June 23-26, 2002
• 44: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003 [doi>10.1145/950620.950624]
• 45: Mostefaoui A., S. Rajsbaum S. and Raynal M., The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. Tech Report #1688, IRISA, Université de Rennes (France), 2005. http://www.irisa.fr/bibli/publi/pi/2005/1688/1688.html
• 46: Achour Mostéfaoui , Michel Raynal, Solving Consensus Using Chandra-Toueg's Unreliable Failure Detectors: A General Quorum-Based Approach, Proceedings of the 13th International Symposium on Distributed Computing, p.49-63, September 27-29, 1999
• 47: A. Mostefaoui , M. Raynal, Low cost consensus-based Atomic Broadcast, Proceedings of the 2000 Pacific Rim International Symposium on Dependable Computing, p.45, December 18-20, 2000
• 48: Mostefaoui A. and Raynal M., Leader-Based Consensus. Parallel Processing Letters, 11(1):95--107, 2001.
• 49: Achour Mostefaoui , Michel Raynal , Corentin Travers, Crash-Resilient Time-Free Eventual Leadership, Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems (SRDS'04), p.208-217, October 18-20, 2004
• 50: Achour Mostefaoui , Michel Raynal , Frederic Tronel, The Best of Both Worlds: A Hybrid Approach to Solve Consensus, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.513-522, June 25-28, 2000
• 51: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 52: F. Pedone , A. Schiper, Handling message semantics with Generic Broadcast protocols, Distributed Computing, v.15 n.2, p.97-107, April 2002 [doi>10.1007/s004460100061]
• 53: Powell D., Failure Mode Assumptions and Assumption Coverage. Proc. of the 22nd Int'l Symposium on Fault-Tolerant Computing (FTCS-22), Boston, MA, pp. 386--395, 1992.
• 54: Rabin M., Randomized Byzantine Generals. Proc. 24th IEEE Symposium on Foundations of Computer Science (FOCS'83), pp. 116--124, Los Alamitos (CA), 1983.
• 55: Michel Raynal, Quiescent Uniform Reliable Broadcast as an Introduction to Failure Detector Oracles, Proceedings of the 6th International Conference on Parallel Computing Technologies, p.98-111, September 03-07, 2001
• 56: Raynal M., Detecting Crash Failures in Asynchronous Systems: What? Why? How? Tutorial given at Proc. Int. Conference on Dependable Systems and Networks (DSN'04), Florence (Italy), 2004.
• 57: Raynal M. and Tronel F., Group Membership Failure Detection: a Simple Protocol and its Probabilistic Analysis. Distributed Systems Engineering Journal, 6(3):95--102, 1999.
• 58: André Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed Computing, v.10 n.3, p.149-157, April 1997 [doi>10.1007/s004460050032]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Reliability