Thumbnail
Access Restriction
Subscribed

Author Attiya, Hagit ♦ Fouren, Arie
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Contention-sensitive complexity ♦ Asynchronous shared-memory systems ♦ Collect ♦ Read/write registers ♦ Renaming ♦ Wait-free algorithms
Abstract This article introduces the $\textit{sieve},$ a novel building block that allows to adapt to the number of simultaneously active processes (the point contention) during the execution of an operation. We present an implementation of the sieve in which each sieve operation requires $\textit{O}(\textit{k}$ log $\textit{k})$ steps, where $\textit{k}$ is the point contention during the operation.The sieve is the cornerstone of the first wait-free algorithms that adapt to point contention using only read and write operations. Specifically, we present efficient algorithms for long-lived renaming, timestamping and collecting information.
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 2003-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 50
Issue Number 4
Page Count 25
Starting Page 444
Ending Page 468


Open content in new tab

   Open content in new tab
Source: ACM Digital Library