### Improved implementations of binary universal operationsImproved implementations of binary universal operations

Access Restriction
Subscribed

 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

Source: ACM Digital Library