A Simple Snapshot Algorithm for Multicore Systems

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 n 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 presents a new and particularly simple construction of a snapshot object. This construction relies on a new principle, that we call “write first, help later” strategy. This strategy directs an update operation first to write its value and only then computes an helping snapshot value that can be used by a snapshot operation in order to terminate. Interestingly, not only the algorithms implementing the snapshot and update operations are simple and have easy proofs, but they are also efficient in terms of the number of accesses to the underlying atomic registers shared by the processes. An operation costs O(m) in the best case and O(n m) in the worst case.
Type de document :
Rapport
[Research Report] PI 1955, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00505233
Contributeur : Ist Rennes <>
Soumis le : vendredi 23 juillet 2010 - 09:47:48
Dernière modification le : mardi 16 janvier 2018 - 15:54:12
Document(s) archivé(s) le : lundi 25 octobre 2010 - 12:12:00

Fichier

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

Identifiants

  • HAL Id : inria-00505233, version 1

Citation

Damien Imbs, Michel Raynal. A Simple Snapshot Algorithm for Multicore Systems. [Research Report] PI 1955, 2010. 〈inria-00505233〉

Partager

Métriques

Consultations de la notice

370

Téléchargements de fichiers

259