Failure Detectors and it's properties

Failure detection is essential for many algorithms. And any failure detector is composed of two basic properties.

1. Completeness
2. Accuracy

There can be 2 types of completeness property

1. Strong completeness
2. weak completeness

Strong completeness

Every crashed node is eventually detected by all correct nodes.

Weak completeness

Every crashed node is eventually detected by some correct nodes.

Actually the weak and the strong completeness is equivalent. Because given a weak completeness we can achieve strong completeness. As some correct nodes has the information about all crashed nodes it can disseminate[using BEB, and as the some nodes are correct so all the correct nodes will get the information] the list of crashed nodes and every one will be aware of the crashed nodes.

Correctness is a liveness property. It can be proved as if some node do not detect the crashed node yet then there is possibility that it will be detected at some point is the future :)

Now let's talk about the accuracy property. It can be classified into 4 as,

1. Strong accuracy
2. Eventual Strong accuracy
   
3. weak accuracy
4. Eventual weak accuracy
   

Strong accuracy

No correct node is ever suspected.

This is really a strong property and this is safety property as well. Because if you detect a correct node as failed then the property is violated for any execution after that.

Eventual Strong accuracy

Eventually no correct node is suspected.

So now this property becomes liveness property because if a correct node is suspected now then there is still a possibility that in future execution no correct node will be detected as failed.

Weak accuracy

There exists a correct node which is never suspected by any node.

So this is a safety property because if none of the node is recognized as correct node then the property can not be satisfied in any future execution.

Eventual Weak accuracy

Eventually there exists a correct node which is never suspected by any node. And this is a liveness property.

So any failure detector is a combination of completeness property and any of the accuracy properties.

So here are the possible failure detectors(considering that strong and weak completeness is equivalent)

Accuracy/Completeness	Strong
Strong	Perfect Failure Detector
Eventually Strong	Eventual Perfect Failure Detector
Weak	Strong Failure Detector
Eventually Weak	Eventual Strong Failure Detector

References

• Introduction to Reliable Distributed Programming by Rachid Guerraoui and Luís Rodrigues