HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Failure Detectors as Schedulers (An Algorithmically-Reasoned Characterization)

Abstract : This paper presents a new approach to study unreliable failure detectors. It uses the \emph{iterated immediate snapshot model} (IIS) to capture the precise amount of synchrony achievable by a failure detector. The IIS model is a round-based model consisting of one-shot objects that provide processes with a single operation to atomically write and snapshot the shared memory. In a wait-free asynchronous manner, processes access a predefined sequence of one-shot immediate snapshot objects. This model is equivalent (for wait-free task solvability) to the usual read/write shared memory model, but its runs are more structured and easier to analyze. It has already been instrumental in other works. The paper studies three known failure detector classes $\{\Diamond {\cal S}_x\}_{1\leq x\leq n}$, $\{\Omega^z\}_{1\leq z\leq n}$, and $\{\Diamond {\psi}^y\}_{1\leq y\leq n}$, via the IIS model ($x, y$ or $z$ are parameters that specify the scope of the corresponding failure detector class). It identifies restrictions of the IIS model that characterize the power of each of these classes. These restrictions are captured as additional properties that the underlying immediate snapshot objects have to satisfy, in essence, obtaining a subset of IIS runs. For each failure detector class $C$, it is shown that the basic read/write model enriched with $C$ and a restricted IIS model have the same computational power for wait-free solvable tasks. Immediate applications of these results are new lower bound proofs for $k$-set agreement in asynchronous systems enriched with a failure detector of each one of these classes. The proofs are simple, using novel distributed simulations, and shed light both to the IIS model and to the nature of the failure detectors.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Friday, March 30, 2007 - 11:43:45 AM
Last modification on : Thursday, January 20, 2022 - 4:20:08 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 3:07:48 AM


Files produced by the author(s)


  • HAL Id : inria-00139317, version 1


Sergio Rajsbaum, Michel Raynal, Corentin Travers. Failure Detectors as Schedulers (An Algorithmically-Reasoned Characterization). [Research Report] PI 1838, 2007, pp.38. ⟨inria-00139317⟩



Record views


Files downloads