Simultaneous 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 participants. It is well known that consensus cannot be solved in crashed-prone, asynchronous distributed systems. Two generalizations of the consensus problem have been introduced: k-set agreement and k-simultaneous 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-simultaneous 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, the 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)/2 , k-simultaneous consensus is strictly harder than k-set 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-simultaneous consensus.
Type de document :
Pré-publication, Document de travail
2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00752610
Contributeur : Corentin Travers <>
Soumis le : samedi 17 novembre 2012 - 00:10:32
Dernière modification le : jeudi 5 avril 2018 - 11:46:04
Document(s) archivé(s) le : vendredi 31 mars 2017 - 16:00:22

Fichier

scsa-main-LONGVERSION.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00752610, version 2

Collections

Citation

Zohir Bouzid, Corentin Travers. Simultaneous Consensus is Harder than Set Agreement in Message Passing. 2012. 〈hal-00752610v2〉

Partager

Métriques

Consultations de la notice

225

Téléchargements de fichiers

59