ISSN : 1796-217X
Volume : 2    Issue : 4    Date : October 2007

Designing Efficient Algorithms for the Eventually Perfect Failure Detector Class
Mikel Larrea, Alberto Lafuente, Iratxe Soraluze, Roberto Cortiñas, and Joachim Wieland
Page(s): 1-11
Full Text:
PDF (360 KB)

This paper focuses on the design of unreliable failure detectors of the Eventually Perfect class (◊P)
in crash-prone partially synchronous systems. We adopt a monitoring mechanism based on
heartbeats over a logical ring arrangement of processes as the common design feature. This
provides good communication efficiency, a performance parameter which refers to the number of
links that carry messages forever. We follow two different approaches that result in two families of
failure detectors: a nearly communication-efficient family, which uses
n + C links forever, being C
the number of correct processes out of the
n processes in the system, and a communication
efficient family, which uses only
n links forever. Besides communication efficiency, we evaluate the
algorithms in terms of QoS parameters, which include the capability of the failure detector to provide
right answers as well as its reaction time.

Index Terms
distributed algorithms, fault tolerance, Consensus, unreliable failure detectors