Δ-Snap: Snapshotting the Differential

We define and solve the differential snapshot problem. A differential snapshot object maintains a dynamic set of components and supports two operations: an Update operation by which any process can read or modify a given component, and a ScanDiff operation by which a designated scanner process can snapshot the differential, i.e., the components that changed since the last snapshot. We design a linearizable and wait-free differential snapshot algorithm that allows updates via arbitrary read-modify-write (RMW) operations supported by hardware. We implement Update in O(1) steps and ScanDiff in O(Δ + p) steps, where Δ is the number of components that have been updated since the last ScanDiff operation and p is the number of processes that access the object.