Implementing the weakest failure detector for solving consensus

Arévalo Viñuales, Sergio and Larrea, Mikel and Fernández Anta, Antonio (2013). Implementing the weakest failure detector for solving consensus. "International Journal of Parallel, Emergent and Distributed Systems", v. 28 (n. 6); pp. 537-555. ISSN 1744-5760. https://doi.org/10.1080/17445760.2012.753180.

Description

Title: Implementing the weakest failure detector for solving consensus
Author/s:
  • Arévalo Viñuales, Sergio
  • Larrea, Mikel
  • Fernández Anta, Antonio
Item Type: Article
Título de Revista/Publicación: International Journal of Parallel, Emergent and Distributed Systems
Date: 2013
ISSN: 1744-5760
Volume: 28
Subjects:
Freetext Keywords: Distributed computing, fault-tolerance, Consensus, failure detector, partial synchrony.
Faculty: E.U. de Informática (UPM)
Department: Informática Aplicada [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB)

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.

More information

Item ID: 25858
DC Identifier: http://oa.upm.es/25858/
OAI Identifier: oai:oa.upm.es:25858
DOI: 10.1080/17445760.2012.753180
Official URL: http://www.tandfonline.com/doi/full/10.1080/17445760.2012.753180#.U3D1f6LlDYg
Deposited by: Memoria Investigacion
Deposited on: 12 May 2014 19:04
Last Modified: 22 Sep 2014 11:38
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM