Faster than Optimal Snapshots (for a While)

摘要

This paper presents a novel implementation of a snapshot object for n processes, with Ο(log~2 b 1og n) step complexity for update operations and Ο(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 polyloga-rithmic step complexity. This can be used, for example, to monitor the number of active processes, which is crucial to adaptive algorithms.