Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity
James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen · Journal of the ACM · 2015
This article presents a novel implementation of a snapshot object for n processes, with O (log 2 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.