Optimal Implementation of the Weakest Failure Detector for Solving Consensus
Mikel Larrea Antonio Fernández Sergio Arévalo
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
The concept of unreliable failure detector was introduced by Chandra and
Toueg as a mechanism that provides information about process failures.
Depending on the properties the failure detectors guarantee, they proposed
a taxonomy of failure detectors. It has been shown that one of the classes
of this taxonomy, named Eventually Strong (<>S), is the weakest class
allowing to solve the Consensus problem. In this paper, we present a new
algorithm implementing <>S. Our algorithm guarantees that eventually
all the correct processes agree on a common correct process. This property
trivially allows us to provide the accuracy and completeness properties
required by <>S. We show, then, that our algorithm is better than any
other proposed implementation of <>S in terms of classical measures
like number of messages or total amount of information periodically sent.
In particular, previous algorithms require to periodically exchange at
least a quadratic amount of information, while ours only requires O(n log
n) (where n is the number of processes). However, we also propose a new
measure to evaluate the efficiency of this kind of algorithms, called the
monitoring degree, which does not rely on a periodic behavior and expresses
better the degree of processing required by the algorithms. We show that
our algorithm is eventually optimal with respect to this measure.