A Study of Wait-Free Hierarchies in Concurrent Systems

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