Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00452799
Contributor : Ist Rennes <>
Submitted on : Wednesday, February 3, 2010 - 10:02:06 AM
Last modification on : Tuesday, June 15, 2021 - 4:16:09 PM
Long-term archiving on: : Friday, June 18, 2010 - 6:35:46 PM

File

PI-1945.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00452799, version 1

Citation

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

Share

Metrics

Record views

454

Files downloads

619