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

A wait-free hierarchy [ACM Transactions on Programming Languages and System s, 11 (1991), pp. 124-149; Proceedings of the 12th ACM Symposium on Princip les of Distributed Computing, 1993, pp. 145-158] classifies object types on the basis of their strength in supporting wait-free implementations of oth er types. Such a hierarchy is robust if it is impossible to implement objec ts 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 lum ps all types into a single level. In particular, the consensus hierarchy (t he most closely studied wait-free hierarchy) is not robust. Our result impl ies that, in general, it is not possible to determine the power of a concur rent system that supports a given set of primitive object types by reasonin g about the power of each primitive type in isolation.