Chandra and Toueg, the co-authors of the book Unreliable Failure Detectors for Reliable Distributed Systems, approached the concept of detecting failure nodes by introducing the unreliable failure detector. They describe the behavior of a unreliable failure detector in a distributed computing system as: after each process in the system entered a local failure detector component, each local component will examine a portion of all processes within the system. In addition, each process must also containprograms that are currently suspected by failure detectors.
Failure detector
Chandra and Toueg claimed that an unreliable failure detector can still be reliable in detecting the errors made by the system. They generalize unreliable failure detectors to all forms of failure detectors because unreliable failure detectors and failure detectors share the same properties. Furthermore, Chandra and Toueg point out an important fact that the failure detector does not prevent any crashes in the system, even if the crashed program has been suspected previously. The construction of a failure detector is an essential, but a very difficult problem that occurred in the development of the fault-tolerant component in a distributed computer system. As a result, the failure detector was invented because of the need for detecting errors in the massive information transaction in distributed computing systems.
Properties
The classes of failure detectors are distinguished by two important properties: completeness and accuracy. Completeness means that the failure detectors would find the programs that finally crashed in a process, whereas accuracy means that correct decisions that the failure detectors made in a process.
Degrees of completeness
The degrees of completeness depend on the number of crashed process is suspected by a failure detector in a certain period.
Strong completeness: "every faulty process is eventually permanently suspected by every non-faulty process."
Weak completeness: "every faulty process is eventually permanently suspected by some non-faulty process."
Degrees of accuracy
The degrees of accuracy depend on the number of mistakes that a failure detector made in a certain period.
Strong accuracy: "no process is suspected before it crashes."
Weak accuracy: "some non-faulty process is never suspected."
Eventual strong accuracy: "no non-faulty process is suspected after some time since the end of the initial period of chaos as the time at which the last crash occurs."
Eventual weak accuracy: "after some initial period of confusion, some non-faulty process is never suspected."
Classification
Failure detectors can be categorized in the following eight types:
Perfect failure detector
Eventually perfect failure detectors
Strong failure detectors
Eventually strong failure detectors
Weak failure detectors
Eventually weak failure detectors
Quasi-perfect failure detectors
Eventually quasi-perfect failure detectors
The properties of these failure detectors are described below:
Strong Perpetual Accuracy
Weak Perpetual Accuracy
Strong Eventual Accuracy
Weak Eventual Accuracy
Strong Completeness
P
S
♦P
♦S
Weak Completeness
Q
W
♦Q
♦W''
In a nutshell, the properties of failure detectors depend on how fast the failure detector detects actual failures and how well it avoids false detection. A perfect failure detector will find all errors without any mistakes, whereas a weak failure detector will not find any errors and make numerous mistakes.
Applications
Different types of failure detectors can be obtained by changing the properties of failure detectors. The first examples show that how to increase completeness of a failure detector, and the second example shows that how to change one type of the failure detector to another.
Boosting completeness
The following is an example abstracted from the Department of Computer Science at Yale University. It functions by boosting the completeness of a failure detector. initially suspects = ∅ do forever: for each process p: if my weak-detector suspects p, then send p to all processes upon receiving p from some process q: suspects := suspects + p - q
From the example above, if p crashes, then the weak-detector will eventually suspect it. All failure detectors in the system will eventually suspect the p because of the infinite loop created by failure detectors. This example also shows that a weak completeness failure detector can also suspect all crashes eventually. The inspection of crashed programs does not depend on completeness.
Reducing a failure detector ''W'' to a failure detector ''S''
The following are correctness arguments to satisfy the algorithm of changing a failure detector W to a failure detector S. The failure detector W is weak in completeness, and the failure detector S is strong in completeness. They are both weak in accuracy.
If all arguments above are satisfied, the reduction of a weak failure detector W to a strong failure detector S will agree with the algorithm within the distributed computing system.
