Generalized irreducibility of consensus and<br>
the equivalence of $t$-resilient and wait-free implementations of consensus

<br><br>
Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti and Sam Toueg

<br><br>
We study the consensus problem,
        which requires multiple processes with different input values to
        eventually agree on one of these values,
        in the context of asynchronous shared memory systems.
Prior research focussed either
        on $t$-resilient solutions of this problem
        (which must be correct even if up to $t$ processes crash) or
        on wait-free solutions
        (which must be correct despite the crash of any number of processes).
In this paper, we show that these two forms of solvability are closely related.
Specifically, for all $n > t \ge 2$
        and all sets $\cal S$ of shared object types
        (that include simple read/write registers)
        there is a $t$-resilient solution to $n$-process consensus
        using objects of types in $\cal S$
        if and only if
        there is a wait-free solution to $(t+1)$-process consensus
        using objects of types in $\cal S$.

Our proof of this equivalence uses another result derived in this paper,
        that is of independent interest.
Roughly speaking, this result states that
        a wait-free solution to $(n-1)$-process consensus
        is never necessary in designing
        a wait-free solution to $n$-process consensus ---
        regardless of the types of objects available.
More precisely, for all $n \ge 2$ and for all sets $\cal S$ of shared object types
        (that include simple read/write registers)
        if there is a wait-free solution to $n$-process consensus
        that uses a wait-free solution to $(n-1)$-process consensus and
        objects of types in $\cal S$,
        then there is a wait-free solution to $n$-process consensus
        that uses only objects of types in $\cal S$.