Loading...
Please wait, while we are loading the content...
Similar Documents
Implementing the weakest failure detector for solving consensus
| Content Provider | Semantic Scholar |
|---|---|
| Author | Larrea, Mikel Anta, Antonio Fernández Arévalo, Sergio |
| Copyright Year | 2008 |
| Abstract | The concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (⋄S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (⋄P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://eprints.networks.imdea.org/567/1/larrea_et_al.pdf |
| Alternate Webpage(s) | http://oa.upm.es/25858/1/INVE_MEM_2013_161333.pdf |
| Alternate Webpage(s) | http://www.sc.ehu.es/acwlaalm/sdi/ijpeds12-submitted.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
