Access Restriction

Author Attiya, Hagit ♦ Dagan, Eyal
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Asynchronous shared-memory systems ♦ Contention-sensitive algorithms ♦ Deterministic coin tossing ♦ Load-linked/store-conditional operations ♦ Universal operations ♦ Wait-free algorithms
Abstract We present an algorithm for implementing binary operations (of any type) from unary $\textit{load-linked}$ (LL) and $\textit{store-conditional}$ (SC) operations. The performance of the algorithm is evaluated according to its $\textit{sensitivity},$ measuring the distance between operations in the graph induced by conflicts, which guarantees that they do not influence the step complexity of each other. The sensitivity of our implementation is $O(log^{*}$ $\textit{n}),$ where $\textit{n}$ is the number of processors in the system. That is, operations that are $Ω(log^{*}$ $\textit{n})$ apart in the graph induced by conflicts do not delay each other. Constant sensitivity is achieved for operations used to implement heaps and array-based linked lists.We also prove that there is a problem which can be solved in $\textit{O}(1)$ steps using binary LL/SC operations, but requires $\textit{O}(log$ $log^{*}$ $\textit{n})$ operations if only unary LL/SC operations are used. This indicates a non-constant gap between unary and binary, LL/SC operations.
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 2001-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 5
Page Count 25
Starting Page 1013
Ending Page 1037

Open content in new tab

   Open content in new tab
Source: ACM Digital Library