A Novel Failure Detection Algorithm for Reliable Distributed Systems

A failure detection service is perfect if it eventually detects all failures and every detection correctly identifies a failure that has occurred. Such a perfect failure detection service serves as a basic building block for many reliable distributed systems, for example in distributed lock services. In this paper, the authors introduce a perfect failure detection scheme in order to improve the fault tolerance of the service. They provide the precise system model and specification for a failure detection service. They present two novel algorithms that implement the failure detection service. They further develop a set of Quality-of-Service (QoS) metrics for perfect failure detection services, and apply probabilistic analysis to quantify the QoS metrics of the two algorithms.