Michel RAYNAL, IRISA, Campus de Beaulieu, 35042 Rennes Cedex, France
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. \squareSk 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 O) 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 \squareS_t+1 where t is the maximum number of processes that can crash during a run. The fact that \squareS_t+1 is easier to build than \square S or \omega and the design simplicity of the proposed protocol makes it attractive.
Index Terms:
Asynchronous distributed system, Eventual leader, Limited accuracy, Failure detection, Process crash.
Citation:
Achour MOSTEFAOUI, Michel RAYNAL, Corentin TRAVERS, Sergio RAJSBAUM, "From Failure Detectors with Limited Scope Accuracy to System-wide Leadership," aina, vol. 1, pp.81-86, 20th International Conference on Advanced Information Networking and Applications - Volume 1 (AINA'06), 2006