Anonymous Asynchronous Systems: The Case of Failure Detectors

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 : Due the multiplicity of loci of control, a main issue distributed systems have to cope with lies in the uncertainty on the system state created by the adversaries that are asynchrony, failures, dynamicity, mobility, etc. Considering message-passing systems, this paper considers the uncertainty created by the net effect of three of these adversaries, namely, asynchrony, failures, and anonymity. This means that, in addition to be asynchronous and crash-prone, the processes have no identity. Trivially, agreement problems (e.g., consensus) that cannot be solved in presence of asynchrony and failures cannot be solved either when adding anonymity. The paper consequently proposes anonymous failure detectors to circumvent these impossibilities. It has several contributions. First it presents three classes of failure detectors (denoted AP, A∩ and A∑) and show that they are the anonymous counterparts of the classes of perfect failure detectors, eventual leader failure detectors and quorum failure detectors, respectively. The class A∑ is new and showing it is the anonymous counterpart of the class ∑ is not trivial. Then, the paper presents and proves correct a genuinely anonymous consensus algorithm based on the pair of anonymous failure detector classes (A∩, A∑) (“genuinely” means that, not only processes have no identity, but no process is aware of the total number of processes). This new algorithm is not a “straightforward extension” of an algorithm designed for non-anonymous systems. To benefit from A∑, it uses a novel message exchange pattern where each phase of every round is made up of sub-rounds in which appropriate control information is exchanged. Finally, the paper discusses the notions of failure detector class hierarchy and weakest failure detector class for a given problem in the context of anonymous systems.
Type de document :
[Research Report] PI 1945, 2010, pp.16
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
Contributeur : Ist Rennes <>
Soumis le : mercredi 3 février 2010 - 10:02:06
Dernière modification le : vendredi 16 novembre 2018 - 01:40:39
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:35:46


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00452799, version 1


François Bonnet, Michel Raynal. Anonymous Asynchronous Systems: The Case of Failure Detectors. [Research Report] PI 1945, 2010, pp.16. 〈inria-00452799〉



Consultations de la notice


Téléchargements de fichiers