Failure Detectors as Schedulers (An Algorithmically-Reasoned Characterization)

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