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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01416509
Contributor : Carole Delporte-Gallet <>
Submitted on : Wednesday, December 14, 2016 - 3:30:25 PM
Last modification on : Friday, January 4, 2019 - 5:33:38 PM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

242