Access Restriction

Author Jayanti, Prasad
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1997
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword MIMD ♦ Asynchronous computing ♦ Hierarchy ♦ Implementation ♦ Robustness ♦ Shared memory ♦ Shared objects ♦ Synchronization ♦ Wait-freedom
Abstract 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 $\textit{hrm}$ in which the level of a type is based on the ability of an $\textit{unbounded}$ number of objects of that type, and another hierarchy, that we call $\textit{hr1},$ in which a type's level is based on the ability of a $\textit{fixed}$ number of objects of that type. We prove that resource bounded hierarchies, such as $\textit{hr1}$ and its variants, are not robust. We also establish the unique importance of $\textit{hrm}:$ every nontrivial robust hierarchy, if one exists, is necessarily a “coarsening” of $\textit{hrm}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1997-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 44
Issue Number 4
Page Count 23
Starting Page 592
Ending Page 614

Open content in new tab

   Open content in new tab
Source: ACM Digital Library