A Study of Wait-Free Hierarchies in Concurrent Systems

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6710

Title: A Study of Wait-Free Hierarchies in Concurrent Systems
Author: McCrickard, D. Scott
Abstract: 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.
Type: Technical Report
URI: http://hdl.handle.net/1853/6710
Date: 1994
Relation: CC Technical Report; GIT-CC-94-04
Publisher: Georgia Institute of Technology
Subject: Wait-free hierarchies
Concurrent systems
Wait-free consensus numbers
Object parameters

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-CC-94-04.pdf 171.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record