On the Robustness of Herlihy's Hierarchy

A wait-free hierarchy maps object types to levels in $Z[superscript]{+} \cup \{ \infty \}$, and has the following property: if a type $T$ is at level $N$, and $T'$ is an arbitrary type, then there is a wait-free implementation of an object of type $T'$, for $N$ processes, using only registers and objects of type $T$. The infinite hierarchy defined by Herlihy is an example of a wait-free hierarchy. A wait-free hierarchy is robust if it has the following property: if $T$ is at level $N$, and $\cal S$ is a finite set of types belonging to levels $N$ -- 1 or lower, then there is no wait-free implementation of an object of type $T$, for $N$ processes, using any number and any combination of objects belonging to the types in $\cal S$. Robustness implies that there are no clever ways of combining weak shared objects to obtain stronger ones.