Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Robustness of Herlihy's Hierarchy

On the Robustness of Herlihy's Hierarchy

File(s)
93-1332.pdf (2.97 MB)
93-1332.ps (331.99 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6098
Collections
Computer Science Technical Reports
Author
Jayanti, Prasad
Abstract

A wait-free hierarchy maps object types to levels in $Z^{+} \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. Contrary to what many reserchers believe [AGTV92, AR92, Her91a], we prove that Herlihy's hierarchy is not robust. We then define some natural variants of Herlihy's hierarchy, which are also infinite wait-free hierarchies. With the exception of one, which is still open, these are not robust either. We conclude with the open question of whether non-trivial robust wait-free hierarchies exist.

Date Issued
1993-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1332
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance