DocumentCode :
2649567
Title :
Optimal implementation of the weakest failure detector for solving consensus
Author :
Larrea, Mikel ; Fernández, Antonio ; Arévalo, Sergio
Author_Institution :
Univ. Publica de Navarra, Pamplona, Spain
fYear :
2000
fDate :
2000
Firstpage :
52
Lastpage :
59
Abstract :
The concept of unreliable failure detector was introduced by T.D. Chandra and S. Toueg (1996) as a mechanism that provides information about process failures. Depending on the properties which the failure detectors guarantee, they proposed a taxonomy of failure detectors. It has been shown that one of the classes of this taxonomy, namely Eventually Strong (∇S), is the weakest class allowing a solution of the Consensus problem. The authors 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 the number of messages and the total amount of information periodically sent. In particular, previous algorithms require periodic exchange of 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 algorithm, the eventual monitoring degree, which does not rely on a periodic behavior and expresses the degree of processing required by the algorithms better. We show that the runs of our algorithm have optimal eventual monitoring degree
Keywords :
computational complexity; distributed algorithms; fault tolerant computing; message passing; Consensus problem; Eventually Strong; common correct process; completeness properties; optimal eventual monitoring degree; optimal implementation; periodic behavior; periodic exchange; process failures; unreliable failure detector; weakest class; weakest failure detector; Algorithm design and analysis; Computer aided manufacturing; Computer crashes; Condition monitoring; Contracts; Councils; Detectors; Fault detection; Fault tolerance; Taxonomy;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Reliable Distributed Systems, 2000. SRDS-2000. Proceedings The 19th IEEE Symposium on
Conference_Location :
Nurnberg
Print_ISBN :
0-7695-0543-0
Type :
conf
DOI :
10.1109/RELDI.2000.885392
Filename :
885392
Link To Document :
بازگشت