Eventual election of multiple leaders for solving consensus in anonymous systems

Tang, Jian; Jiménez, Ernesto; Herrera, Carlos y Arévalo Viñuales, Sergio (2015). Eventual election of multiple leaders for solving consensus in anonymous systems. "The Journal of Supercomputing" (n. null); pp. 1-18. ISSN 0920-8542. https://doi.org/10.1007/s11227-015-1460-6.

Descripción

Título: Eventual election of multiple leaders for solving consensus in anonymous systems
Autor/es:
  • Tang, Jian
  • Jiménez, Ernesto
  • Herrera, Carlos
  • Arévalo Viñuales, Sergio
Tipo de Documento: Artículo
Título de Revista/Publicación: The Journal of Supercomputing
Fecha: 2015
Materias:
Palabras Clave Informales: Keywords Failure detectors · Consensus · Anonymity · Fault tolerance ·Anonymous omega
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Otro
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 (2MB) | Vista Previa

Resumen

In classical distributed systems, each process has a unique identity. Today, new distributed systems have emerged where a unique identity is not always possible to be assigned to each process. For example, in many sensor networks a unique identity is not possible to be included in each device due to its small storage capacity, reduced computational power, or the huge number of devices to be identified. In these cases, we have to work with anonymous distributed systems where processes cannot be identified. Consensus cannot be solved in classical and anonymous asynchronous distributed systems where processes can crash. To bypass this impossibility result, failure detectors are added to these systems. It is known that ? is the weakest failure detector class for solving consensus in classical asynchronous systems when amajority of processes never crashes. Although A? was introduced as an anonymous version of ?, to find the weakest failure detector in anonymous systems to solve consensus when amajority of processes never crashes is nowadays an open question. Furthermore, A? has the important drawback that it is not implementable. Very recently, A? has been introduced as a counterpart of ? for anonymous systems. In this paper, we show that the A? failure detector class is strictly weaker than A? (i.e., A? provides less information about process crashes than A?). We also present in this paper the first implementation of A? (hence, we also show that A? is implementable), and, finally, we include the first implementation of consensus in anonymous asynchronous systems augmented with A? and where a majority of processes does not crash.

Más información

ID de Registro: 37767
Identificador DC: http://oa.upm.es/37767/
Identificador OAI: oai:oa.upm.es:37767
Identificador DOI: 10.1007/s11227-015-1460-6
Depositado por: Memoria Investigacion
Depositado el: 22 Feb 2016 20:34
Ultima Modificación: 23 Feb 2016 20:37
  • 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