An Efficient Adaptive Partial Snapshot Implementation

Abstract

In an asynchronous shared-memory system with n processes, the single-writer snapshot type provides consistent views of an array A of n components, each of which can be updated by one of the processes. Formally, a process p can call Update(v) to write v into A[p], and call Scan() to obtain a view of A. Inherently, under realistic assumptions on the base objects’ size, the specification of this type leads to a lower bound of Ω(n) steps for method Scan(). In some cases, it suffices for a process to take a snapshot of k (1 ≤ k ≤ n) components of A, and thus, taking Ω(n) steps to obtain that snapshot is inefficient when k is small. In this thesis, we provide an implementation of the single-writer adaptive partial snapshot type, which allows a process to take a partial snapshot of k components in O(k log n) steps. We define a new version of Scan() that does not return anything and its behavior is defined in terms of another operation Observe(). An Observe(i) operation by process p returns the value that A[i] had at the point in time of p’s preceding Scan(). We implement a single-writer adaptive partial snapshot object from read-write registers, fetch-and-increment objects, and compare-and-swap objects, such that the step complexity of method Scan() is O(1) and that of methods Update() and Observe() is O(log n).