Probabilistic analysis of a group failure detection protocol
- 1 January 1999
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A group membership failure (in short, a group failure) occurs when one of the group members crashes. A group failure detection protocol has to inform all the non-crashed members of the group that this group entity has crashed. Ideally, such a protocol should be live (if a process crashes, then the group failure has to be detected) and safe (if a group failure is claimed, then at least one process has crashed). Unreliable asynchronous distributed systems are characterized by the impossibility for a process to get an accurate view of the system state. Consequently, the design of a group failure detection protocol that is both safe and live is a problem that cannot be solved in all runs of an asynchronous distributed system. We analyse a group failure detection protocol whose design naturally ensures its liveness. We show that by tuning appropriately some of its duration-related parameters, the safety property can be guaranteed with a probability as close to 1 as desired. This analysis shows that, in real distributed systems, it is possible to achieve failure detection with a negligible probability of wrong suspicions.Keywords
This publication has 7 references indexed in Scilit:
- Failure mode assumptions and assumption coveragePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Consensus service: a modular approach for building agreement protocols in distributed systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fault-tolerant Total Order Multicast to asynchronous groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The timed asynchronous distributed system modelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A solution to atomic commitment based on an extended consensus protocolPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985