A wait-free hierarchy ACM Transactions on Programming Languages and Systems, 11 (1991), pp. 124--149; Proceedings of the 12th ACM Symposium on Principles of Distributed Computing, 1993, pp. 145--158] classifies object types on the basis of their strength in supporting wait-free implementations of other types. Such a hierarchy is robust if it is impossible to implement objects of types that it classifies as "strong" by combining objects of types that it classifies as "weak." We prove that if nondeterministic types are allowed, the only wait-free hierarchy that is robust is the trivial one, which lumps all types into a single level. In particular, the consensus hierarchy (the most closely studied wait-free hierarchy) is not robust. Our result implies that, in general, it is not possible to determine the power of a concurrent system that supports a given set of primitive object types by reasoning about the power of each primitive type in isolation.

In this paper we study the ability of shared object types to implement Consensus in asynchronous sharedmemory systems where at most one process may cresh.More specifically, we consider the following question: Let n z 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 one-resilient Consensus among n -1 processes?We prove that for n = 3 the answer is negative, even if S consists only of deterministic types.(This strengthens an earlier result by the first author proving the same fact for nondetermtnistic types.)lVe also prove that, in contrast, for n >3 the answer to the above question is affirmative. Background and overviewIn this paper we consider some questions concerning fault-tolerant implementations of Consensus in asynchronous shared-memory systems.In such systems, some number of processes communicate with each other by accessing shared typed objects.Processes take steps in a completely asynchronous manner.In one step, a process may invoke an operation on a shared object.Thk causes the object to atomically change its state and return a response to the process invoking the operation.The new state entered by the object and the response returned to the operation are determined by the specification of the type to which the object belongs.A process may crush -i.e., stop taking steps "Supportedby a CanadianCommonwealthScholarship.

A wait-free hierarchy [Her91, Jay93] classifies object types on the basis of their strength in supporting waitfree implementations of other types.(In the context of the present paper, an implementation may use any number of objects of the given types, as well as read/write registers.)Such a hierarchy is robust if it is impossible to implement objects of types that it classifies as "strong" by combining objects of types that it classifies as "weak".We prove that, if nondeterministic types are allowed, the only wait-free hierarchy that is robust is the trivial one, which lumps all types into a single level.In particular, the Consensus hierarchy (the most closely studied wait-free hierarchy) is not robust.Our result implies that, in general, it is not possible to determine the power of a concurrent system that supports a given set of primitive object types by reasoning about the power of each primitive type in isolation.