A Simple Snapshot Algorithm for Multicore Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

A Simple Snapshot Algorithm for Multicore Systems

Résumé

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.
Fichier principal
Vignette du fichier
PI-1955.pdf (454.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00505233 , version 1 (23-07-2010)

Identifiants

  • HAL Id : inria-00505233 , version 1

Citer

Damien Imbs, Michel Raynal. A Simple Snapshot Algorithm for Multicore Systems. [Research Report] PI 1955, 2010. ⟨inria-00505233⟩
252 Consultations
389 Téléchargements

Partager

Gmail Facebook X LinkedIn More