On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes
Résumé
This paper considers the failure detector classes that have been considered in the literature to solve $k$-set agreement, and studies their relative power. It shows that the family of failure detector classes $\Diamond {\cal S}_x$ ($0\leq x \leq n$), and $\Diamond \psi^y$ ($0\leq y \leq n$), 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 \psi^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 \psi^{1}$ allows solving $t$-set agreement (but not $(t-1)$-set agreement), a system with failure detectors of both classes can solve consensus. More generally, the paper studies the failure detector classes $\Diamond {\cal S}_x$, $\Diamond \psi^y$ and $\Omega^z$, and shows which reductions among these classes are possible and which are not.The paper presents also a message-passing $\Omega^k$-based $k$-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.
Loading...