From a Store-Collect Object and Ω to Efficient Asynchronous Consensus

Michel Raynal 1 Julien Stainer 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 : This paper presents an efficient algorithm that build a consensus object. This algorithm is based on an Ω failure detector (to obtain consensus liveness) and a store-collect object (to maintain its safety). A store-collect object provides the processes with two operations, a store operation which allows the invoking process to deposit a new value while discarding the previous value it has deposited and a collect operation that returns to the invoking process a set of pairs (i, val) where val is the last value deposited by the process pi . A store-collect object has no sequential specification. While store-collect objects have been used as base objects to design wait-free constructions of more sophisticated objects (such as snapshot or renaming objects), as far as we know, they have not been explicitly used to built consensus objects. The proposed store-collect-based algorithm, which is round-based, has several noteworthy features. First it uses a single store-collect object (and not an object per round). Second, during a round, a process invokes at most once the store operation and the value val it deposits is a simple pair r, v where r is a round number and v a proposed value. Third, a process is directed to skip rounds according to its view of the current global state (thereby saving useless computation rounds). Finally, the algorithm benefits from the adaptive wait-free implementations that have been proposed for store-collect objects, namely, the number of shared memory accesses involved in a collect operation is O(k) where k is the number of processes that have invoked the store operation. This makes the proposed algorithm particularly efficient and interesting for multiprocess programs made up of asynchronous crash-prone processes that run on top of multicore architectures.
Type de document :
Communication dans un congrès
Euro-Par - Parallel Processing - 18th International Conference - 2012, 2012, Rhodes Island, Greece. pp.427-438, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00733080
Contributeur : Julien Stainer <>
Soumis le : lundi 17 septembre 2012 - 17:13:52
Dernière modification le : mercredi 16 mai 2018 - 11:23:13

Identifiants

  • HAL Id : hal-00733080, version 1

Citation

Michel Raynal, Julien Stainer. From a Store-Collect Object and Ω to Efficient Asynchronous Consensus. Euro-Par - Parallel Processing - 18th International Conference - 2012, 2012, Rhodes Island, Greece. pp.427-438, 2012. 〈hal-00733080〉

Partager

Métriques

Consultations de la notice

811