Robust wait-free hierarchies

• Published in: Journal of the ACM 1997-07, Vol.44 (4), p.592-614
• Main Author: Jayanti, Prasad
• Format: Article
• Language: English
• Subjects: Algorithms; Asynchronous; Coarsening; Data communications; Hierarchies; Object oriented programming; Operating systems; Robustness; Studies
• ISSN: 0004-5411; 1557-735X
• DOI: 10.1145/263867.263888

The problem of implementing a shared object of one type from shared objects of other types has been extensively researched. Recent focus has mostly been on wait-free implementations , which permit every process to complete its operations on implemented objects, regardless of the speeds of other processes. It is known that shared objects of different types have differing abilities to support wait-free implementations. It is therefore natural to want to arrange types in a hierarchy that reflects their relative abilities to support wait-free implementations. In this paper, we formally define robustness and other desirable properties of hierarchies. Roughly speaking, a hierarchy is robust if each type is “stronger” than any combination of lower level types. We study two specific hierarchies: one, that we call h r m in which the level of a type is based on the ability of an unbounded number of objects of that type, and another hierarchy, that we call h r 1 , in which a type's level is based on the ability of a fixed number of objects of that type. We prove that resource bounded hierarchies, such as h r 1 and its variants, are not robust. We also establish the unique importance of h r m : every nontrivial robust hierarchy, if one exists, is necessarily a “coarsening” of h r m .