Adaptive Partial Snapshots with Logarithmic Step Complexity

Abstract

The standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a Scan() operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n). In this paper, we consider an alternative version of the snapshot type, where a Scan() operation stores a consistent snapshot of all n memory locations, but does not return anything. Instead, a process can later observe the value of any component of that snapshot using a separate Observe() operation. This allows us to implement the type from fetch-and-increment and compare-and-swap objects, such that Scan() operations have constant step complexity and Update() and Observe() operations have step complexity O(logn).