Skip to Main content Skip to Navigation

Help when needed, but no more: Efficient Read/Write Partial Snapshot

Damien Imbs 1 Michel Raynal 1 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : An atomic snapshot object is an object that can be concurrently accessed by asynchronous processes prone to crash. It is made of m 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 in order they can always terminate. This paper is on partial snapshot objects. Such an object provides a snapshot operation that takes a (dynamically defined) 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 uptodateness. 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 r helps a partial snapshot, uptodateness requires that the update provides the partial snapshot with a value of the component r 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 algorithms 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) to 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.
Document type :
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Monday, November 17, 2008 - 2:49:11 PM
Last modification on : Thursday, January 20, 2022 - 4:20:10 PM
Long-term archiving on: : Monday, June 7, 2010 - 11:01:56 PM


Files produced by the author(s)


  • HAL Id : inria-00339292, version 1


Damien Imbs, Michel Raynal. Help when needed, but no more: Efficient Read/Write Partial Snapshot. [Research Report] PI 1907, 2008, pp.26. ⟨inria-00339292⟩



Record views


Files downloads