Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Corentin Travers Connect in order to contact the contributor
Submitted on : Monday, May 19, 2014 - 11:51:24 AM
Last modification on : Saturday, June 25, 2022 - 10:34:49 AM
Long-term archiving on: : Monday, April 10, 2017 - 11:43:02 PM


Files produced by the author(s)



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



Record views


Files downloads