Unreliable failure detectors. The failure detector concept was introduced by Xxxxxxx and Xxxxx in [15] with the purpose of identifying the minimal extensions to an asynchronous system that would render consensus solvable. In [15], the authors identify two completeness properties and four accuracy properties. This classification leads to eight classes of failure detectors, which can be reduced to just four distinct classes, by applying reduction algorithms. In the following, we provide some basic definitions for the two completeness and four ac- curacy properties. The weak completeness property requires that there is a time after which ev- ery process that crashes is permanently suspected by some correct process. If we strengthen the constraint and we require that eventually every crashed process is permanently sus- pected by every correct process, we obtain the so-called strong completeness property. The perpetual accuracy property requires that accuracy is always satisfied. Eventual accu- racy relaxes this constraint: accuracy must be permanently satisfied only after some time. Strong accuracy states that no process is suspected before it crashes. The less constraint-full version of strong accuracy is weak accuracy: some correct process is never suspected. Among the classes of failure detectors, we particularly focus on three of them, which are relevant for our work, namely Eventually Weak, denoted by ♢W, Perfect, denoted by P, and Eventually Strong, denoted by ♢S. The Eventually Weak class of failure detectors is described in [15] as the weakest class that renders consensus solvable. A failure detector is in ♢W if it satisfies weak completeness and eventual weak accuracy. These two properties require that eventually some conditions are satisfied and hold forever. However, in a real system in which properties cannot be satisfied forever, it is required that they hold for a sufficiently long period of time. If we refer to the consensus problem, we can quantify the “sufficiently long” period of time as being long enough to allow the algorithm to terminate and each process to decide. The Perfect class, denoted by P, contains the failure detectors that satisfy the most constraint-full requirements, which are strong completeness and strong accuracy. Another important class of failure detectors, intensively investigated in the literature, is the class of Eventually Strong failure detectors, denoted by ♢S. A failure detector belonging to this class satisfies the properties of strong complete...
