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


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.