Observatorio de I+D+i UPM

Memorias de investigación
Communications at congresses:
"Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus)".
Year:2012
Research Areas
  • Information technology and adata processing
Information
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 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).
International
Si
Congress
IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)
960
Place
China.
Reviewers
Si
ISBN/ISSN
978-1-4577-0295-2
Start Date
18/06/2012
End Date
21/06/2012
From page
275
To page
284
IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)
Participants
  • Autor: Sergio Arevalo Viñuales (UPM)
  • Autor: Jose Ernesto Jimenez Merino (UPM)
  • Autor: Antonio FERNANDEZ ¿ ANTA (Institute IMDEA Networks)
  • Autor: Damien IMBS (IRISA, Campus de Beaulieu)
  • Autor: Michel RAYNAL (Institut Universitaire de France; IRISA)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Laboratorio de sistemas distribuidos (LSD)
  • Departamento: Informática Aplicada
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)