Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus).

Arévalo Viñuales, Sergio and Jiménez Merino, José Ernesto and Fernández Anta, Antonio and Imbs, Damien and Raynal, Michel (2012). Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus).. In: "IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)", 18/06/2012 - 21/06/2012, China.. pp. 275-284.

Description

Title: Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus).
Author/s:
  • Arévalo Viñuales, Sergio
  • Jiménez Merino, José Ernesto
  • Fernández Anta, Antonio
  • Imbs, Damien
  • Raynal, Michel
Item Type: Presentation at Congress or Conference (Article)
Event Title: IEEE 32nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS)
Event Dates: 18/06/2012 - 21/06/2012
Event Location: China.
Date: 2012
Subjects:
Freetext Keywords: Agreement problem, Asynchrony, Consensus, Distributed computability, failure detector, Homonymous system, Message-passing, Process crash.
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 (180kB) | Preview

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 identi?er). New classes of failure detectors suited to these systems are ?rst de?ned. Among them, the classes H? and H? are introduced that are the homonymous counterparts of the classes ? and ?, respectively. (Recall that the pair h?,?i de?nes 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 ofthe membership. One algorithm solves consensus with hH?, H?i, while the other uses only H?, but needs a majority of correct processes. Observe that the systems with unique identi?ers 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, while the analogous class A? de?ned for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the ?rst proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

More information

Item ID: 20097
DC Identifier: http://oa.upm.es/20097/
OAI Identifier: oai:oa.upm.es:20097
Deposited by: Memoria Investigacion
Deposited on: 06 Mar 2014 16:48
Last Modified: 21 Apr 2016 22:28
  • 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