From failure detectors with limited scope accuracy to system-wide leadership

A failure detector is a device that provides the processes with information on failures. The accuracy property of a failure detector defines the type of mistakes it is not allowed to make. The limited scope of the accuracy property restricts it to only a part of the system. ◊S_k is a class of unreliable failure detectors with a limited scope accuracy. Eventually each process that crashes is suspected by every correct process, and there is a time after which some correct process is never suspected by only k processes. An eventual leader facility (usually denoted Ω)is a device that eventually provides all the processes with the identity of one of them that is correct. Such a facility is used as a basic service in a lot of fault-tolerant distributed protocols (e.g., asynchronous consensus protocols). This paper proposes a protocol that builds an eventual leader service from any unreliable failure detector of the class ◊S_t+1 where t is the maximum number of processes that can crash during a run. The fact that ◊S_t+1 is easier to build than ◊S or Ω and the design simplicity of the proposed protocol makes it attractive.