inria-00425127, version 2
Early Consensus in Message-passing Systems Enriched with a Perfect Failure Detector and its Application in the Theta Model
François Bonnet
a, 1Michel Raynal b, 1
N° PI 1937 (2009)
Résumé : The paper then presents an original algorithm that implements a perfect failure detector in the Theta model, an interesting model that achieves some form of synchrony without relying on physical clocks. Hence, the stacking of these algorithms provides an algorithm that solves consensus in the Theta model in min(f +2, t+1) communication rounds, i.e., in two rounds when there are no failures, which is clearly optimal.
- a – Ecole Normale Supérieure de Cachan
- b – Université de Rennes 1
- 1 : ASAP (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
- Domaine : Informatique/Autre
- Mots-clés : Asynchronous message-passing system – Consensus problem – Early decision – Perfect failure detector – Process crash – Theta-model
- Référence interne : PI 1937
- Versions disponibles : v1 (20-10-2009) v2 (20-10-2009)
- inria-00425127, version 2
- http://hal.inria.fr/inria-00425127
- oai:hal.inria.fr:inria-00425127
- Contributeur : Ist Rennes
- Soumis le : Mardi 20 Octobre 2009, 14:40:15
- Dernière modification le : Mardi 11 Mai 2010, 12:37:37
Documents associés
Exporter