Thumbnail
Access Restriction
Subscribed

Author Fich, Faith ♦ Herlihy, Maurice ♦ Shavit, Nir
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Consensus ♦ Lower bounds ♦ Space complexity
Abstract The “waite-free hierarchy” provides a classification of multiprocessor synchronization primitives based on the values of $\textit{n}$ for which there are deterministic wait-free implementations of $\textit{n}-process$ consensus using instances of these objects and $\textit{read-write}$ registers. In a randomized wait-free setting, this classification is degenerate, since $\textit{n}-process$ consensus can be solved using only O(n) read-write registers.In this paper, we propose a classification of synchronization primitives based on the space complexity of randomized solutions to $\textit{n}-process$ consensus. A historyless object, such as a $\textit{read-write}$ register, a $\textit{swap}$ register, or a The “waite-free hierarchy” provides a classification of multiprocessor synchronization primitives based on the values of $\textit{n}$ for which there are deterministic wait-free implementations of $\textit{n}-process$ consensus using instances of these objects and $\textit{read-write}$ registers. In a randomized wait-free setting, this classification is degenerate, since $\textit{n}-process$ consensus can be solved using only O(n) read-write registers.In this paper, we propose a classification of synchronization primitives based on the space complexity of randomized solutions to $\textit{n}-process$ consensus. A historyless object, such as a $\textit{read-write}$ register, a $\textit{swap}$ register, or a $\textit{test&set}$ register, is an object whose state depends only on the lost nontrivial operation thate was applied to it. We show that, using $\textit{historyless}$ objects, &OHgr;(n object instances are necessary to solve $\textit{n}-process$ consensus. This lower bound holds even if the objects have unbounded size and the termination requirement is nondeterministic solo termination, a property strictly weaker than randomized wait-freedom.We then use this result to related the randomized space complexity of basic multiprocessor synchronization primitives such as shared counters, fetch&add registers, and $\textit{compare&swap}$ registers. Viewed collectively, our results imply that there is a separation based on space complexity for synchronization primitives in randomized computation, and that this separation differs from that implied by the deterministic “wait-free hierarchy.” registers. Viewed collectively, our results imply that there is a separation based on space complexity for synchronization primitives in randomized computation, and that this separation differs from that implied by the deterministic “wait-free hierarchy.”
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 1998-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 5
Page Count 20
Starting Page 843
Ending Page 862


Open content in new tab

   Open content in new tab
Source: ACM Digital Library