The notification based approach to implementing failure detectors in distributed systems

ABSTRACT

Failure Detector (FD) is the fundamental component of fault tolerant computer systems. In recent years, many research works have been done on the study of QoS and implementation of FDs for distributed computing environments. Almost all of these works are based on the heartbeat approach (HBFD). In this paper, we propose a general model for implementing FDs which separates the processes to be monitored from the underlying running environment. We identify the potential problems of HBFD approach and propose an alternative approach to implementing FDs, called notification based FD (NTFD). Instead of letting the process periodically send heartbeat messages to show it is still alive, in NTFD, the underlying watchdog mechanism sends failure notification messages only when the failure of a monitored process is detected locally. Compared with HBFD implementation under our model, NTFD is more efficient and scalable, and can guarantee the strong accuracy property. Trade-off of achieving QoS of FD is analyzed and the results show that NTFD has much higher probability to achieve a better balance between completeness and accuracy, yet provides a much lower probability of false report and lower system cost. Based on the analysis, we propose the design of a hybrid FD which combines the advantages of HBFD and NTFD.

REFERENCES

• 1: Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
• 2: 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]
• 3: 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]
• 4: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks, Theoretical Computer Science, v.220 n.1, p.3-30, June 6, 1999 [doi>10.1016/S0304-3975(98)00235-7 ]
• 5: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Failure Detection and Consensus in the Crash-Recovery Model, Proceedings of the 12th International Symposium on Distributed Computing, p.231-245, September 24-26, 1998
• 6: Danny Dolev , Roy Friedman , Idit Keidar , Dahlia Malkhi, Failure Detectors in Omission Failure Environments, Cornell University, Ithaca, NY, 1996
• 7: Danny Dolev , Roy Friedman , Idit Keidar , Dahlia Malkhi, Failure detectors in omission failure environments, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.286, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259501]
• 8: Robbert van Renesse, Yaron Minsky, and Mark Hayden. "A gossip-style failure detection service." In Proceedings of Middleware '98, September 1998.
• 9: 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]
• 10: 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
• 11: 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 ]
• 12: Bertier, M.; Marin, O.; Sens, P., "Performance analysis of a hierarchical failure detector" Dependable Systems and Networks, 2003. Proceedings. 2003 International Conference on 22--25 June 2003 Page(s):635--644
• 13: Raul Ceretta Nunes , Ingrid Jansch-Porto, QoS of Timeout-Based Self-Tuned Failure Detectors: The Effects of the Communication Delay Predictor and the Safety Margin, Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04), p.753, June 28-July 01, 2004
• 14: Irineu Sotoma , Edmundo Roberto Mauro Madeira, A Markov Model for Quality of Service of Failure Detectors in the Pressure of Loss Bursts, Proceedings of the 18th International Conference on Advanced Information Networking and Applications, p.62, March 29-31, 2004
• 15: Lorenzo Falai , Andrea Bondavalli, Experimental Evaluation of the QoS of Failure Detectors on Wide Area Network, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.624-633, June 28-July 01, 2005 [doi>10.1109/DSN.2005.47]
• 16: Szu-Chi Wang; Sy-Yen Kuo, "Communication Strategies for Heartbeat-Style Failure Detectors in Wireless Ad Hoc Networks",. In Proceedings of International Conference on Dependable Systems and Networks, 2003. 22--25 June 2003
• 17: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112627]
• 18: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 19: Yennun Huang; Chandar Kintala; "Software fault tolerance in the application layer" Software Fault tolerance, John Wiley & Sons Ltd. 1995
• 20: Christof Fetzer, Perfect Failure Detection in Timed Asynchronous Systems, IEEE Transactions on Computers, v.52 n.2, p.99-112, February 2003 [doi>10.1109/TC.2003.1176979 ]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

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

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management

General Terms:
Design, Management, Reliability

Keywords:
QoS, failure detector, fault tolerance, heartbeat, performance evaluation