On the Robustness of Herlihy's Hierarchy
On the Robustness of Herlihy's HierarchyPrasad Jayanti
Sign up to use
On the Robustness of Herlihy's Hierarchy

On the Robustness of Herlihy's Hierarchy

Sign up to use
Sign up to use
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.