Revisiting Simultaneous Consensus with Crash Failures

Abstract : This paper addresses the “consensus with simultaneous decision” problem in a synchronous system prone to t process crashes. This problem requires that all the processes that do not crash decide on the same value (consensus) and that all decisions are made during the very same round (simultaneity). So, there is a double agreement, one on the decided value (data agreement) and one on the decision round (time agreement). This problem was first defined by Dwork and Moses who analyzed it and solved it using an analysis of the evolution of states of knowledge in a system with crash failures. The current paper presents a simple algorithm that optimally solves simultaneous consensus. Optimality means in this case that the simultaneous decision is taken in each and every run as soon as any protocol decides, given the same failure pattern and initial value. The design principle of this algorithm is simplicity, a first-class criterion. A new optimality proof is given that is stated in purely combinatorial terms.
Type de document :
Rapport
[Research Report] PI 1885, 2008, pp.17
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00260643
Contributeur : Ist Rennes <>
Soumis le : mardi 4 mars 2008 - 16:17:11
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 20 mai 2010 - 23:53:25

Fichiers

PI-1885.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00260643, version 1

Citation

Y. Moses, Michel Raynal. Revisiting Simultaneous Consensus with Crash Failures. [Research Report] PI 1885, 2008, pp.17. 〈inria-00260643〉

Partager

Métriques

Consultations de la notice

395

Téléchargements de fichiers

203