Failure detectors in homonymous distributed systems (with an application to consensus)

Arévalo Viñuales, Sergio ORCID: https://orcid.org/0000-0002-0807-0631, Jiménez Merino, José Ernesto ORCID: https://orcid.org/0000-0002-3432-6581, Fernández Anta, Antonio, Imbs, Damien and Raynal, Michel (2015). Failure detectors in homonymous distributed systems (with an application to consensus). "Journal of parallel and distributed computing", v. 83 ; pp. 83-95. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2015.05.007.

Description

Title: Failure detectors in homonymous distributed systems (with an application to consensus)
Author/s:
Item Type: Article
Título de Revista/Publicación: Journal of parallel and distributed computing
Date: September 2015
ISSN: 0743-7315
Volume: 83
Subjects:
Freetext Keywords: Agreement problem, asynchrony, consensus, distributed computability, failure detector, homonymous systems, message-passing, process crash
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of INVE_MEM_2015_217148.pdf]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview

Abstract

ABSTRACT

This paper is on homonymous distributed systems where processes are prone to crash failures and have no
initial knowledge of the system membership (‘‘homonymous’’ means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes HΩ and HΣ are introduced that are the homonymous counterparts of the Classes Ω and Σ, respectively. (Recall that the pair ⟨Ω, Σ⟩ defines the weakest failure detector to solve consensus.) Then, the paper shows how HΩ and HΣ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with ⟨HΩ, HΣ⟩, while the other uses only
HΩ, but needs a majority of correct processes.
Observe that the systems with unique identifiers and anonymous systems are extreme cases of
homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class HΩ can be implemented with partial synchrony (i.e., all messages sent after some bounded time GST will be received after at most an unknown bounded latency δ), while the analogous class AΩ defined for anonymous systems cannot be implemented (even in synchronous systems). Hence, the paper provides the first consensus algorithm for anonymous systems with this model of partial synchrony and a majority of correct processes.

Funding Projects

Type
Code
Acronym
Leader
Title
Government of Spain
TIN2013-46883
BigDataPaaS
Unspecified
Unspecified
Madrid Regional Government
S2013/ICE-2894
Cloud4BigData
Unspecified
Unspecified

More information

Item ID: 40480
DC Identifier: https://oa.upm.es/40480/
OAI Identifier: oai:oa.upm.es:40480
DOI: 10.1016/j.jpdc.2015.05.007
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Deposited by: Memoria Investigacion
Deposited on: 07 Apr 2017 19:40
Last Modified: 30 Nov 2022 09:00
  • 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