Consensus in Anonymous Distributed Systems: Is There a Weakest Failure Detector?

François Bonnet 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : This paper is on failure detectors to solve the consensus problem in asynchronous systems made up of anonymous processes prone to crash and connected by asynchronous reliable channels. Anonymity means that any two processes cannot be distinguished one from the other: they have no name and execute the same code. The paper has several contributions. It first introduces two new classes of failures detectors, denoted AP and A, and presents an AP-based algorithm and an A-based algorithm that solve the consensus problem despite the three computational adversaries that are asynchrony, failures and anonymity. Then, the paper shows that, in crash-prone non-anonymous systems, (a) AP and the class of perfect failure detectors (denoted P) are equivalent, and (b) A and the class of eventual leader failure detectors (denoted) are also equivalent. Finally, the paper addresses the question of the weakest failure detector to solve consensus in an asynchronous crash-prone anonymous system. In non-anonymous systems, the class P of perfect failure detectors is strictly stronger than the class of eventual leader failure detectors that has been shown to be the weakest failure detector class for consensus in asynchronous crash-prone system. Quite surprisingly, the paper shows that their anonymous counterparts cannot be compared. Hence, while is the weakest failure detector class to solve consensus in non-anonymous systems, it is possible that there are several (hence incomparable) classes of weakest failure detectors for this problem in anonymous systems.
Type de document :
Rapport
[Research Report] PI 1938, 2009, pp.11
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00426674
Contributeur : Ist Rennes <>
Soumis le : mardi 27 octobre 2009 - 12:08:43
Dernière modification le : mercredi 11 avril 2018 - 01:56:44
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:19:52

Fichier

PI-1938.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00426674, version 1

Citation

François Bonnet, Michel Raynal. Consensus in Anonymous Distributed Systems: Is There a Weakest Failure Detector?. [Research Report] PI 1938, 2009, pp.11. 〈inria-00426674〉

Partager

Métriques

Consultations de la notice

347

Téléchargements de fichiers

279