Parallel Consensus is Harder than Set Agreement in Message Passing

Abstract : In the traditional consensus task, processes are required to agree on a common value chosen among the initial values of the participating processes. It is well known that consensus cannot be solved in crash-prone, asynchronous distributed systems. Two generalizations of the consensus tasks have been introduced: k-set agreement and k-parallel consensus. The k-set agreement task has the same requirements as consensus except that processes are allowed to decide up to k distinct values. In the k-parallel consensus task, each process participates simultaneously in k instances of consensus and is required to decide in at least one of them; any two processes deciding in the same instance must decide the same value. It is known that both tasks are equivalent in the wait-free shared memory model. Perhaps surprisingly, this paper shows that this is no longer the case in the n-process asynchronous message passing model with at most t process crashes. Specifically, the paper establishes that for parameters t, n, k such that t > n+k−2 , k-parallel consensus is strictly harder than k-set 2 agreement. The proof compares the information on failures necessary to solve each task in the failure detector framework and relies on a result in topological combinatorics, namely, the chromatic number of Kneser graphs. The paper also introduces the new failure detector class V Σk , which is a generalization of the quorum failures detector class Σ suited to k-parallel consensus.
Type de document :
Communication dans un congrès
ICDCS, Jul 2013, Philadelphia, PA, United States. IEEE, pp.611-620, 2013, 〈10.1109/ICDCS.2013.72〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00992783
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 11:51:24
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:43:02

Fichier

15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Zohir Bouzid, Corentin Travers. Parallel Consensus is Harder than Set Agreement in Message Passing. ICDCS, Jul 2013, Philadelphia, PA, United States. IEEE, pp.611-620, 2013, 〈10.1109/ICDCS.2013.72〉. 〈hal-00992783〉

Partager

Métriques

Consultations de la notice

207

Téléchargements de fichiers

62