On scalable and efficient distributed failure detectors

ABSTRACT

Process groups in distributed applications and services rely on failure detectors to detect process failures completely, and as quickly, accurately, and scalably as possible, even in the face of unreliable message deliveries. In this paper, we look at quantifying the optimal scalability, in terms of network load, (in messages per second, with messages having a size limit) of distributed, complete failure detectors as a function of application-specified requirements. These requirements are 1) quick failure detection by some non-faulty process, and 2) accuracy of failure detection. We assume a crash-recovery (non-Byzantine) failure model, and a network model that is probabilistically unreliable (w.r.t. message deliveries and process failures). First, we characterize, under certain independence assumptions, the optimum worst-case network load imposed by any failure detector that achieves an application's requirements. We then discuss why traditional heart beating schemes are inherently unscalable according to the optimal load. We also present a randomized, distributed, failure detector algorithm that imposes an equal expected load per group member. This protocol satisfies the application defined constraints of completeness and accuracy, and speed of detection on an average. It imposes a network load that differs frown the optimal by a sub-optimality factor that is much lower than that for traditional distributed heartbeating schemes. Moreover, this sub-optimality factor does not vary with group size (for large groups).

REFERENCES

• 1: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Heartbeat: A Timeout-Free Failure Detector for Quiescent Reliable Communication, Proceedings of the 11th International Workshop on Distributed Algorithms, p.126-140, September 24-26, 1997
• 2: C. Almeida and P. Verissimo. Timing failure detection and real-time group communication in real-time systems. In Proceedings of 8th Euromicro Workshop on Real-Time Systems, June 1996.
• 3: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 4: Roger Bollo , Jean-Pierre Le Narzul , Michel Raynal , Frederic Tronel, Probabilistic Analysis of a Group Failure Detection Protocol, Proceedings of the Fourth International Workshop on Object-Oriented Real-Time Dependable Systems, p.156, January 27-29, 1999
• 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: Wei Chen , Sam Toueg , Marcos Kawazoe Aguilera, On the Quality of Service of Failure Detectors, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.191, June 25-28, 2000
• 7: S. A. Fakhouri, G. S. Goldszmidt, I. Gupta, M. Kalantar, and J. A. Pershing. Guffstream - a system for dynamic topology management in multi-domain server farms. Technical Report RC 21954, IBM T.J. Watson Research Center, February 2001.
• 8: Christof Fetzer , Flaviu Cristian, Fail-awareness in timed asynchronous systems, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.314-321, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248119]
• 9: 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]
• 10: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, A Probabilistically Correct Leader Election Protocol for Large Groups, Proceedings of the 14th International Conference on Distributed Computing, p.89-103, October 04-06, 2000
• 11: J. M. Helary and M. Hurfin. Solving Agreement problems with failure detectors; a survey. Annals of Telecommunications, 52(9-10):447-464, September-October 1997.
• 12: Mikel Larrea , Antonio Fernández , Sergio Arévalo, Optimal implementation of the weakest failure detector for solving consensus (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.334, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.362113]
• 13: Gregory F. Pfister, In search of clusters (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 14: R. van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Proceedings of International Conference and Distributed Systems Platforms and Open Distributed Processing (IFIP), 1998.

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.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Measurement, Performance, Theory

Keywords:
accuracy, distributed systems, efficiency, failure detectors, scalability