Access Restriction

Author Aspnes, James ♦ Attiya, Hagit ♦ Censor-Hillel, Keren ♦ Ellen, Faith
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Concurrent objects ♦ Atomic snapshot ♦ Generalized counters ♦ Restricted-use objects
Abstract This article presents a novel implementation of a snapshot object for $\textit{n}$ processes, with $O(log^{2}$ $\textit{b}$ log $\textit{n})$ step complexity for update operations and $\textit{O}(log$ $\textit{b})$ step complexity for scan operations, where $\textit{b}$ is the number of updates. The algorithm uses only reads and writes. For polynomially many updates, this is an exponential improvement on previous snapshot algorithms, which have linear step complexity. It overcomes the existing $Ω(\textit{n})$ lower bound on step complexity by having the step complexity depend on the number of updates. The key to this implementation is the construction of a new object consisting of a pair of max registers that supports a scan operation.
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 2015-03-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 1
Page Count 22
Starting Page 1
Ending Page 22

Open content in new tab

   Open content in new tab
Source: ACM Digital Library