All of us are smarter than any of us
Wai-Kau Lo, Vassos Hadzilacos · 1997
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.