Implementing the weakest failure detector for solving consensus

Arévalo Viñuales, Sergio; Larrea, Mikel y 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.

Descripción

Título: Implementing the weakest failure detector for solving consensus
Autor/es:
  • Arévalo Viñuales, Sergio
  • Larrea, Mikel
  • Fernández Anta, Antonio
Tipo de Documento: Artículo
Título de Revista/Publicación: International Journal of Parallel, Emergent and Distributed Systems
Fecha: 2013
Volumen: 28
Materias:
Palabras Clave Informales: Distributed computing, fault-tolerance, Consensus, failure detector, partial synchrony.
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Informática Aplicada [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB)

Resumen

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.

Más información

ID de Registro: 25858
Identificador DC: http://oa.upm.es/25858/
Identificador OAI: oai:oa.upm.es:25858
Identificador DOI: 10.1080/17445760.2012.753180
URL Oficial: http://www.tandfonline.com/doi/full/10.1080/17445760.2012.753180#.U3D1f6LlDYg
Depositado por: Memoria Investigacion
Depositado el: 12 May 2014 19:04
Ultima Modificación: 22 Sep 2014 11:38
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM