Failure detectors in homonymous distributed systems (with an application to consensus)

Arévalo Viñuales, Sergio; Jiménez Merino, José Ernesto; Fernández Anta, Antonio; Imbs, Damien y Raynal, Michel (2015). Failure detectors in homonymous distributed systems (with an application to consensus). "Journal of parallel and distributed computing", v. 83 ; pp. 83-95. ISSN 0743-7315.


Título: Failure detectors in homonymous distributed systems (with an application to consensus)
  • Arévalo Viñuales, Sergio
  • Jiménez Merino, José Ernesto
  • Fernández Anta, Antonio
  • Imbs, Damien
  • Raynal, Michel
Tipo de Documento: Artículo
Título de Revista/Publicación: Journal of parallel and distributed computing
Fecha: Septiembre 2015
Volumen: 83
Palabras Clave Informales: Agreement problem, asynchrony, consensus, distributed computability, failure detector, homonymous systems, message-passing, process crash
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

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


ABSTRACT This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (‘‘homonymous’’ means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes HΩ and HΣ are introduced that are the homonymous counterparts of the Classes Ω and Σ, respectively. (Recall that the pair ⟨Ω, Σ⟩ defines the weakest failure detector to solve consensus.) Then, the paper shows how HΩ and HΣ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with ⟨HΩ, HΣ⟩, while the other uses only HΩ, but needs a majority of correct processes. Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class HΩ can be implemented with partial synchrony (i.e., all messages sent after some bounded time GST will be received after at most an unknown bounded latency δ), while the analogous class AΩ defined for anonymous systems cannot be implemented (even in synchronous systems). Hence, the paper provides the first consensus algorithm for anonymous systems with this model of partial synchrony and a majority of correct processes.

Proyectos asociados

Gobierno de EspañaTIN2013-46883Sin especificarSin especificarSin especificar
Comunidad de MadridS2013/ICE-2894Sin especificarSin especificarSin especificar

Más información

ID de Registro: 40480
Identificador DC:
Identificador OAI:
Identificador DOI:
URL Oficial:
Depositado por: Memoria Investigacion
Depositado el: 07 Abr 2017 19:40
Ultima Modificación: 07 Abr 2017 19:40
  • InvestigaM
  • GEO_UP4
  • 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
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM