Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000604
Contributor : Anne Jaigu <>
Submitted on : Monday, November 7, 2005 - 11:00:07 AM
Last modification on : Thursday, January 7, 2021 - 4:18:13 PM
Long-term archiving on: : Friday, April 2, 2010 - 6:30:07 PM

Identifiers

  • HAL Id : inria-00000604, version 1

Citation

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⟩

Share

Metrics

Record views

374

Files downloads

223