Help when needed, but no more: Efficient read/write partial snapshot

An atomic snapshot object is an object that can be concurrently accessed by asynchronous processes prone to crash. It is made of mm components (base atomic registers) and is defined by two operations: an update operation that allows a process to atomically assign a new value to a component and a snapshot operation that atomically reads and returns the values of all the components. To cope with the net effect of concurrency, asynchrony and failures, the algorithm implementing the update operation has to help concurrent snapshot operations so that they always terminate.This paper is on partial snapshot objects. Such an object provides a snapshot operation that can take any subset of the components as input parameter, and atomically reads and returns the values of this subset of components. The paper has two contributions. The first is the introduction of two properties for partial snapshot object algorithms, called help-locality and freshness  . Help-locality requires that an update operation helps only the concurrent partial snapshot operations that read the component it writes. When an update of a component rr helps a partial snapshot, freshness requires that the update provides the partial snapshot with a value of the component rr that is at least as recent as the value it writes into that component. (No snapshot algorithm proposed so far satisfies these properties). The second contribution consists of an update and a partial snapshot algorithm that are wait-free, linearizable and satisfy the previous efficiency properties. Interestingly, the principle that underlies the proposed algorithms is different from the one used so far, namely, it is based on the “write first, and help later” strategy. An improvement of the previous algorithms is also presented. Based on LL/SC atomic registers (instead of read/write registers), this improvement decreases the number of base registers from O(n2)O(n2) to O(n)O(n). This shows an interesting tradeoff relating the synchronization power of the base operations and the number of base atomic registers when using the “write first, and help later” strategy.

► New partial snapshot algorithm where updates help only conflicting snapshots.
► Two novel properties for snapshot algorithms: help-locality and freshness.
► New helping strategy for wait-free algorithms called “write first, help later”.
► A partial snapshot variant based on the pair of base LL/SC operations.