Asynchronous Consensus with Bounded Memory.

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 2, 1
2 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : We present here a bounded memory size Obstruction-Free consensus algorithm for the asynchronous shared memory model. More precisely for a set of n processes, this algorithm uses n+2n+2 multi-writer multi-reader registers, each of these registers being of size O(log(n))O(log⁡(n)) bits. From this, we get a bounded memory size space complexity consensus algorithm with single-writer multi-reader registers and a bounded memory size space complexity consensus algorithm in the asynchronous message passing model with a majority of correct processes. As it is easy to ensure the Obstruction-Free assumption with randomization (or with leader election failure detector ΩΩ) we obtain a bounded memory size randomized consensus algorithm and a bounded memory size consensus algorithm with failure detector.
Type de document :
Article dans une revue
Lecture notes in computer science, springer, 2016, Networked Systems, 9944, pp.15. 〈10.1007/978-3-319-46140-3_12〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01416509
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 14 décembre 2016 - 15:30:25
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier. Asynchronous Consensus with Bounded Memory.. Lecture notes in computer science, springer, 2016, Networked Systems, 9944, pp.15. 〈10.1007/978-3-319-46140-3_12〉. 〈hal-01416509〉

Partager

Métriques

Consultations de la notice

168