A Study of Wait-Free Hierarchies in Concurrent Systems
D. Scott McCrickard · 1994
An assignment of wait-free consensus numbers to object types results in a wait-free hierarchy. Herlihy was the first to propose such a hierarchy, but Jayanti noted that Herlihy's hierarchy was not robust. Jayanti posed as open questions the robustness of a hierarchy he defined and the existence of a robust, wait-free hierarchy. In this paper, we examine a number of object parameters that may impact on a hierarchy's robustness. In addition, we study a subset of Jayanti's hierarchy introduced by Afek, Weisberger, and Weisman called common2 and extend this subset to include the seemingly powerful 2-bounded peek-queue. Finally, we introduce a property called commonness and examine its applications to wait-free hierarchies and their robustness. College of Computing Georgia Institute of Technology Atlanta, Georgia 30332-0280 1 Introduction A concurrent system consists of a set of asynchronous processes that communicate through shared objects such as registers, queues, and test-and-set bit...