Eventual election of multiple leaders for solving consensus in anonymous systems

Tang, Jian and Jiménez, Ernesto and Herrera, Carlos and 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.

Description

Title: Eventual election of multiple leaders for solving consensus in anonymous systems
Author/s:
  • Tang, Jian
  • Jiménez, Ernesto
  • Herrera, Carlos
  • Arévalo Viñuales, Sergio
Item Type: Article
Título de Revista/Publicación: The Journal of Supercomputing
Date: 2015
ISSN: 0920-8542
Subjects:
Freetext Keywords: Keywords Failure detectors · Consensus · Anonymity · Fault tolerance ·Anonymous omega
Faculty: E.U. de Informática (UPM)
Department: Otro
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 (2MB) | Preview

Abstract

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.

More information

Item ID: 37767
DC Identifier: http://oa.upm.es/37767/
OAI Identifier: oai:oa.upm.es:37767
DOI: 10.1007/s11227-015-1460-6
Official URL: https://link.springer.com/article/10.1007%2Fs11227-015-1460-6
Deposited by: Memoria Investigacion
Deposited on: 22 Feb 2016 20:34
Last Modified: 03 Jun 2019 13:30
  • 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