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.
Type de document :
Rapport
[Research Report] PI 1907, 2008, pp.26
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00339292
Contributeur : Anne Jaigu <>
Soumis le : lundi 17 novembre 2008 - 14:49:11
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:01:56

Fichiers

PI-1907.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00339292, version 1

Citation

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

Partager

Métriques

Consultations de la notice

368

Téléchargements de fichiers

207