The k-simultaneous consensus problem

Abstract : This paper introduces and investigates the k-simultaneous consensus problem: each process participates at the same time in k independent consensus instances until it decides in any one of them. Two results are presented. The first shows that the k-simultaneous consensus problem and the k-set agreement problem are wait-free equivalent in read/write shared memory systems. The second shows that the multivalued version and the binary version of the k-simultaneous consensus problem are wait-free equivalent. These equivalences are independent of the number of processes. An immediate consequence of these results is that the k-set agreement problem and the k-simultaneous binary consensus problem are equivalent. This not only provides a new characterization of the k-set agreement problem but also provides a meaning to the notion of k-set binary agreement.
Type de document :
Rapport
[Research Report] PI 1920, 2009, pp.17
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00354248
Contributeur : Anne Jaigu <>
Soumis le : lundi 19 janvier 2009 - 12:52:32
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:42:37

Fichiers

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

Identifiants

  • HAL Id : inria-00354248, version 1

Citation

Yehuda Afek, Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers. The k-simultaneous consensus problem. [Research Report] PI 1920, 2009, pp.17. 〈inria-00354248〉

Partager

Métriques

Consultations de la notice

426

Téléchargements de fichiers

286