Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Wednesday, February 3, 2010 - 10:02:06 AM
Last modification on : Thursday, October 27, 2022 - 3:45:00 AM
Long-term archiving on: : Friday, June 18, 2010 - 6:35:46 PM


Files produced by the author(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⟩



Record views


Files downloads