All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust

Wai-Kau Lo and Vassos Hadzilacos

A wait-free hierarchy~\cite{Her91a,Jay93} classifies object types on the basis of their strength in supporting wait-free 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.