On the Robustness of Herlihy's Hierarchy

Abstract

A wait-free hierarchy maps object types to levels in $Z^{+} \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. Contrary to what many reserchers believe [AGTV92, AR92, Her91a], we prove that Herlihy's hierarchy is not robust. We then define some natural variants of Herlihy's hierarchy, which are also infinite wait-free hierarchies. With the exception of one, which is still open, these are not robust either. We conclude with the open question of whether non-trivial robust wait-free hierarchies exist.