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

In this paper we study the ability of shared object types to implement Cons ensus in asynchronous shared-memory systems where at most one process may c rash. More specifically, we consider the following question: Let n greater than or equal to 3 and S be a set of object types that can be used to solve one-resilient Consensus among n processes. Can S always be used to solve o ne-resilient Consensus among n - 1 processes? We prove that for n = 3 the a nswer is negative, even if S consists only of deterministic types. (This st rengthens an earlier result by the first author proving the same fact for n ondeterministic types.) We also prove that, in contrast, for n > 3 the answ er to the above question is affirmative.