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

Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes

Abstract : Solving agreement problems (such as consensus and $k$-set agreement) in asynchronous distributed systems prone to process failures has been shown to be impossible. To circumvent this impossibility, distributed oracles (also called unreliable failure detectors) have been introduced. A failure detector provides information on failures, and a failure detector class is defined by a set of abstract properties that encapsulate (and hide) synchrony assumptions. Some failure detector classes have been shown to be the weakest to solve some agreement problems (e.g., $\Omega$ is the weakest class of failure detectors that allow solving the;consensus problem in asynchronous systems where a majority of processes do not crash). This paper considers several failure detector classes and focuses on their additivity or their irreducibility. It mainly investigates two families of failure detector classes (denoted $\Diamond {\cal S}_x$ and $\Diamond \phi^y$, $0\leq x,y \leq n$), shows that they can be ``added'' to provide a failure detector of the class $\Omega^z$ (a generalization of $\Omega$). It also characterizes the power of such an ``addition'', namely, $\Diamond {\cal S}_x +\Diamond \phi^y \leadsto \Omega^z \Leftrightarrow x+y+z>t+1$, where $t$ is the maximum number of processes that can crash in a run. As an example, the paper shows that, while $\Diamond {\cal S}_{t}$ allows solving 2-set agreement (and not consensus) and $\Diamond \phi^{1}$ allows solving $t$-set agreement (but not $(t-1)$-set agreement), their ``addition'' allows solving consensus. More generally, the paper studies the failure detector classes $\Diamond {\cal S}_x$, $\Diamond \phi^y$ and $\Omega^z$, and shows whic reductions among these classes are possible and which are not. The paper presents also an $\Omega^k$-based $k$-set set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the $k$-set agreement problem. \\ Ce rapport étudie la composition de classes de détecteurs de fautes. Il montre aussi que certaines classes ne peuvent être composées pour donner des détecteurs d'une puissance supérieure.
Document type :
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Monday, November 7, 2005 - 11:00:07 AM
Last modification on : Tuesday, June 15, 2021 - 4:14:49 PM
Long-term archiving on: : Friday, April 2, 2010 - 6:30:07 PM


  • HAL Id : inria-00000604, version 1


Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers. Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes. [Research Report] PI 1758, 2005, pp.24. ⟨inria-00000604⟩



Record views


Files downloads