Asynchronous Consensus with Bounded MemoryReportar como inadecuado




Asynchronous Consensus with Bounded Memory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 2 GANG - Networks, Graphs and Algorithms LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt

Abstract : We present here a bounded memory consensus Obstruction-Free algorithm for the asynchronous shared memory model. More precisely for a set of n processes, this algorithm uses n + 1 multi-writer multi-reader MWMR registers, each of these registers being of size Ologn bits. Then we get a On logn-bits size complexity consensus algorithm with single-writer multi-reader SWMR registers and a On logn-bits 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.

Keywords : Shared memory space complexity consensus





Autor: Carole Delporte-Gallet - Hugues Fauconnier -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados