Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Communication-efficient and crash-quiescent Omega with Unknown Membership
Year:2011
Research Areas
  • Engineering
Information
Abstract
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.
International
Si
JCR
Si
Title
Information Processing Letters
ISBN
0020-0190
Impact factor JCR
0,612
Impact info
Volume
111
10.1016/j.ipl.2010.11.012
Journal number
4
From page
194
To page
199
Month
SIN MES
Ranking
102/125 COMPUTER SCIENCE, INFORMATION SYSTEMS (SCI)
Participants
  • 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)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Informática Aplicada
S2i 2019 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)