Optimal implementation of the weakest failure detector for solving consensus (brief announcement) Export

@inproceedings{citeulike:4021583, abstract = {Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (\⋄ S ), is the weakest class allowing to solve Consensus 1 . This brief announcement presents a new algorithm implementing \⋄ S . Due to space limitation, the reader is referred to [4] for an in-depth presentation of the algorithm (system model, correctness proof, and performance analysis). Here, we present the general idea of the algorithm and compare it with other algorithms implementing unreliable failure detectors. The algorithm works as follows. We have n processes, p 1 , \…, p n . Initially, process p 1 starts sending messages periodically to the rest of processes. The rest of processes initially trust p 1 , and wait for its messages. If a process does not receive a message within some timeout period from its trusted process, then it suspects its trusted process and takes the next process as its new trusted process. If a process trusts itself, then it starts sending messages periodically to its successors. Otherwise, it just waits for periodical messages from its trusted process. If, at some point, a process receives a message from a process p i such that p i precedes its trusted process, then it will trust p i again, increasing the value of its timeout period with respect to p i . With this algorithm, eventually all the correct processes will permanently trust the same correct process. This provides the eventual weak accuracy property required by \⋄ S . By simply suspecting the rest of processes, we obtain the strong completeness property required by \⋄ S . Our algorithm compares favorably with the algorithms proposed in [2] and [3] in terms of the number and size of the messages periodically sent and the total amount of information periodically exchanged. Since algorithms implementing failure detectors need not necessarily be periodic, we propose a new and (we believe) more adequate performance measure, which we call eventual monitoring degree . Informally, this measure counts the number of pairs of correct processes that will infinitely often communicate. We show that the proposed algorithm is optimal with respect to this measure. Table 1 summarizes the comparison, where C denotes the number of correct processes and LFA denotes the proposed algorithm.}, address = {New York, NY, USA}, author = {Larrea, Mikel and Fern\'andez, Antonio and Ar\'evalo, Sergio}, booktitle = {PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing}, citeulike-article-id = {4021583}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=362113}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/343477.362113}, doi = {10.1145/343477.362113}, isbn = {1-58113-183-6}, keywords = {2000, consensus, failure\_detectors, implementation, model, weakest}, location = {Portland, Oregon, United States}, posted-at = {2009-02-07 12:24:52}, priority = {2}, publisher = {ACM}, title = {Optimal implementation of the weakest failure detector for solving consensus (brief announcement)}, url = {http://dx.doi.org/10.1145/343477.362113}, year = {2000} }

TY - CONF ID - citeulike:4021583 L3 - citeulike-article-id:4021583 N2 - Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (⋄ S ), is the weakest class allowing to solve Consensus 1 . This brief announcement presents a new algorithm implementing ⋄ S . Due to space limitation, the reader is referred to [4] for an in-depth presentation of the algorithm (system model, correctness proof, and performance analysis). Here, we present the general idea of the algorithm and compare it with other algorithms implementing unreliable failure detectors. The algorithm works as follows. We have n processes, p 1 , …, p n . Initially, process p 1 starts sending messages periodically to the rest of processes. The rest of processes initially trust p 1 , and wait for its messages. If a process does not receive a message within some timeout period from its trusted process, then it suspects its trusted process and takes the next process as its new trusted process. If a process trusts itself, then it starts sending messages periodically to its successors. Otherwise, it just waits for periodical messages from its trusted process. If, at some point, a process receives a message from a process p i such that p i precedes its trusted process, then it will trust p i again, increasing the value of its timeout period with respect to p i . With this algorithm, eventually all the correct processes will permanently trust the same correct process. This provides the eventual weak accuracy property required by ⋄ S . By simply suspecting the rest of processes, we obtain the strong completeness property required by ⋄ S . Our algorithm compares favorably with the algorithms proposed in [2] and [3] in terms of the number and size of the messages periodically sent and the total amount of information periodically exchanged. Since algorithms implementing failure detectors need not necessarily be periodic, we propose a new and (we believe) more adequate performance measure, which we call eventual monitoring degree . Informally, this measure counts the number of pairs of correct processes that will infinitely often communicate. We show that the proposed algorithm is optimal with respect to this measure. Table 1 summarizes the comparison, where C denotes the number of correct processes and LFA denotes the proposed algorithm. CY - Portland, Oregon, United States SN - 1-58113-183-6 AD - New York, NY, USA TI - Optimal implementation of the weakest failure detector for solving consensus (brief announcement) PB - ACM T2 - PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing KW - 2000 KW - consensus KW - failure_detectors KW - implementation KW - model KW - weakest AU - Larrea, Mikel AU - Fern\'andez, Antonio AU - Ar\'evalo, Sergio PY - 2000/// UR - http://dx.doi.org/10.1145/343477.362113 ER -