On the power of shared object types to implement one-resilient Consensus

Wai-Kau Lo and Vassos Hadzilacos

In this paper we study the ability of shared object types to implement Consensus
in asynchronous shared-memory systems where at most one process may crash. More
specifically, we consider the following question: Let $n\ge3$ and
$\mathcal{S}$ be a set of object types that can be used to solve one-resilient
Consensus among $n$ processes. Can $\mathcal{S}$ always be used to solve
one-resilient Consensus among $n-1$ processes? We prove that for $n=3$ the
answer is negative, even if $\mathcal{S}$ consists only of *deterministic*
types. (This strengthens an earlier result by the first author proving the same
fact for
*nondeterministic* types.) We also prove that, in contrast, for $n>3$
the answer to the above question is affirmative.