Communication-efficient and crash-quiescent Omega with unknown membership

Arévalo Viñuales, Sergio; Jiménez Merino, José Ernesto; Larrea, Mikel y 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.

Descripción

Título: Communication-efficient and crash-quiescent Omega with unknown membership
Autor/es:
  • Arévalo Viñuales, Sergio
  • Jiménez Merino, José Ernesto
  • Larrea, Mikel
  • Mengual Galan, Luis
Tipo de Documento: Artículo
Título de Revista/Publicación: Information Processing Letters
Fecha: 2011
Volumen: 111
Materias:
Palabras Clave Informales: Distributed computing; Fault tolerance; Unreliable failure detectors
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 (478kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 11243
Identificador DC: http://oa.upm.es/11243/
Identificador OAI: oai:oa.upm.es:11243
Identificador DOI: 10.1016/j.ipl.2010.11.012
URL Oficial: http://www.sciencedirect.com/science/article/pii/S0020019010003625
Depositado por: Memoria Investigacion
Depositado el: 03 Jul 2012 11:49
Ultima Modificación: 20 Abr 2016 19:23
  • 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