James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Limited-use atomic snapshots with polylogarithmic step complexity. Journal of the Association for Computing Machinery 62(1):3, February 2015. Erratum. An earlier version appeared in 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 375–384, under the title “Faster than optimal snapshots (for a while)” .
This paper presents a novel implementation of a snapshot object for n processes, with O(log² b log n) step complexity for update operations and O(log b) step complexity for scan operations, where 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 Ω(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.
@article{AspnesACHE2015,
author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Faith Ellen},
title = {Limited-use snapshots with polylogarithmic step complexity},
month = feb,
year = 2015,
journal = jacm,
volume = 62,
number = 1,
pages = 3
}
@article{AspnesACHE2015erratum,
author = {Aspnes, James and Attiya, Hagit and Censor-Hillel, Keren and Ellen, Faith},
title = {Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity},
journal = {J. ACM},
issue_date = {November 2018},
volume = {65},
number = {6},
month = nov,
year = {2018},
issn = {0004-5411},
pages = {38:1--38:2},
articleno = {38},
numpages = {2},
url = {https://doi.acm.org/10.1145/3231592},
doi = {10.1145/3231592},
acmid = {3231592},
publisher = {ACM},
address = {New York, NY, USA},
}