Communication-efficient and crash-quiescent Omega with unknown membership

Arévalo Viñuales, Sergio and Jiménez Merino, José Ernesto and Larrea, Mikel and Mengual Galan, Luis (2011). Communication-efficient and crash-quiescent Omega with unknown membership. "Information Processing Letters", v. 111 (n. 4); pp. 194-199. ISSN 0020-0190. https://doi.org/10.1016/j.ipl.2010.11.012.

Description

Title: Communication-efficient and crash-quiescent Omega with unknown membership
Author/s:
  • Arévalo Viñuales, Sergio
  • Jiménez Merino, José Ernesto
  • Larrea, Mikel
  • Mengual Galan, Luis
Item Type: Article
Título de Revista/Publicación: Information Processing Letters
Date: 2011
ISSN: 0020-0190
Volume: 111
Subjects:
Freetext Keywords: Distributed computing; Fault tolerance; Unreliable failure detectors
Faculty: E.U. de Informática (UPM)
Department: Informática Aplicada [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (478kB) | Preview

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 () such that every correct process eventually and permanently outputs the set of all correct processes.

More information

Item ID: 11243
DC Identifier: http://oa.upm.es/11243/
OAI Identifier: oai:oa.upm.es:11243
DOI: 10.1016/j.ipl.2010.11.012
Official URL: http://www.sciencedirect.com/science/article/pii/S0020019010003625
Deposited by: Memoria Investigacion
Deposited on: 03 Jul 2012 11:49
Last Modified: 20 Apr 2016 19:23
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM