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 (2012). Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus).. En: "IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)", 18/06/2012 - 21/06/2012, China.. pp. 275-284.

Descripción

Título: Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus).
Autor/es:
  • Arévalo Viñuales, Sergio
  • Jiménez Merino, José Ernesto
  • Fernández Anta, Antonio
  • Imbs, Damien
  • Raynal, Michel
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)
Fechas del Evento: 18/06/2012 - 21/06/2012
Lugar del Evento: China.
Fecha: 2012
Materias:
Palabras Clave Informales: Agreement problem, Asynchrony, Consensus, Distributed computability, failure detector, Homonymous system, Message-passing, Process crash.
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 (180kB) | Vista Previa

Resumen

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 identi?er). New classes of failure detectors suited to these systems are ?rst de?ned. Among them, the classes H? and H? are introduced that are the homonymous counterparts of the classes ? and ?, respectively. (Recall that the pair h?,?i de?nes 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 ofthe membership. One algorithm solves consensus with hH?, H?i, while the other uses only H?, but needs a majority of correct processes. Observe that the systems with unique identi?ers 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, while the analogous class A? de?ned for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the ?rst proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

Más información

ID de Registro: 20097
Identificador DC: http://oa.upm.es/20097/
Identificador OAI: oai:oa.upm.es:20097
Depositado por: Memoria Investigacion
Depositado el: 06 Mar 2014 16:48
Ultima Modificación: 21 Abr 2016 22:28
  • 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