A wait-free hierarchy maps object types to levels in {1, 2, 3,...} U {co}, and has the following property: if a type 2' is at level N, then, for all types T', 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 TO bust if it has the following property: if a t ype T is at level N, and 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 S. Robustness implies that there are no clever ways of combining weak shared objects to obtain stronger ones. Contrary to what many researchers believe, 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 a non-trivial robust wait-free hierarchies exists.
Jayanti REF defined robustness of a hierarchy as the property that an object at a higher level in the hierarchy cannot be implemented using any number or combination of objects lower in the hierarchy.
On the robustness of Herlihy's hierarchy
PODC '93
Mathematics Computer Science