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

                Wai-Kau Lo and Vassos Hadzilacos

                            ABSTRACT

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 \emph{deterministic} types.  (This strengthens an earlier
result by the first author proving the same fact for \emph{nondeterministic}
types.) We also prove that, in contrast, for $n>3$ the answer to the above
question is affirmative.