### On the space complexity of randomized synchronizationOn the space complexity of randomized synchronization

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

Source: ACM Digital Library