James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Faster than optimal snapshots (for a while). 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 375–384.
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.
Applications of this construction include an implementation of a limited-use generalized counter with polylogarithmic step complexity. This can be used, for example, to monitor the number of active processes, which is crucial to adaptive algorithms.
@inproceedings{AspnesACHE2012,
author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Faith Ellen},
title = {Faster than optimal snapshots (for a while)},
month = jul,
year = 2012,
booktitle = {2012 ACM Symposium on Principles of Distributed Computing},
pages={375--384}
}