Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Communication-efficient and crash-quiescent Omega with Unknown Membership
Año:2011
Áreas de investigación
  • Ingenierías
Datos
Descripción
The failure detector class Omega (?) provides an eventual leader election functionality, i.e., eventually all correct processes permanently trust the same correct process. An algorithm is communication-efficient if the number of links that carry messages forever is bounded by n, being n the number of processes in the system. It has been defined that an algorithm is crash-quiescent if it eventually stops sending messages to crashed processes. In this regard, it has been recently shown the impossibility of implementing ? crash quiescently without a majority of correct processes. We say that the membership is unknown if each process pi only knows its own identity and the number of processes in the system (that is, i and n), but pi does not know the identity of the rest of processes of the system. There is a type of link (denoted by ADD link) in which a bounded (but unknown) number of consecutive messages can be delayed or lost. In this work we present the first implementation (to our knowledge) of ? in partially synchronous systems with ADD links and with unknown membership. Furthermore, it is the first implementation of ? that combines two very interesting properties: communication-efficiency and crash-quiescence when the majority of processes are correct. Finally, we also obtain with the same algorithm a failure detector (?P) such that every correct process eventually and permanently outputs the set of all correct processes.
Internacional
Si
JCR del ISI
Si
Título de la revista
Information Processing Letters
ISSN
0020-0190
Factor de impacto JCR
0,612
Información de impacto
Volumen
111
DOI
10.1016/j.ipl.2010.11.012
Número de revista
4
Desde la página
194
Hasta la página
199
Mes
SIN MES
Ranking
102/125 COMPUTER SCIENCE, INFORMATION SYSTEMS (SCI)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Sergio Arevalo Viñuales (UPM)
  • Autor: Jose Ernesto Jimenez Merino (UPM)
  • Autor: Luis Mengual Galan (UPM)
  • Autor: Mikel Larrea (Universidad del País Vasco)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Informática Aplicada
S2i 2021 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)