Zohir Bouzid
email: zohir.bouzid@lip6.fr

Corentin Travers
email: travers@labri.fr

Parallel Consensus is Harder than Set Agreement in Message Passing

Keywords: Consensus, Failure detectors, Fault tolerance, Agreement, Message passing, Kneser graph

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 2 , k-parallel 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-parallel consensus.

I. INTRODUCTION

The k-set agreement problem: The k-set agreement problem (Chaudhuri, [START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF]) is one of the fundamental problems in fault tolerant distributed computing. Each process proposes a value and every non-faulty process is required to decide a value (termination) such that every decided value has been proposed (validity) and no more than k distinct values are decided (agreement). The problem generalizes the consensus problem, which corresponds to the case where k = 1. In asynchronous systems, it is well known that 1set agreement is impossible as soon as at least one process may fail by crashing [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF], whereas the case k = n does not require any coordination at all. For intermediate values of k (1 < k < n), asynchronous k-set agreement tolerating t process crash failures is possible if and only if k > t [START_REF] Borowsky | Generalized flp impossibility result for t-resilient asynchronous computations[END_REF], [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF], [START_REF] Saks | Wait-free k-set agreement is impossible: The topology of public knowledge[END_REF], in shared memory or message-passing systems.

The k-parallel consensus problem: The k-parallel consensus problem [START_REF] Afek | The k-simultaneous consensus problem[END_REF] 1 is another generalization of consensus. Each process proposes a value and is required to decide a pair (c, v), where c is an integer 1 ≤ c ≤ k and v is a proposed value (validity). Each non-faulty process has to decide (termination) and, for any two pairs with the same first component, the second component must be the same, i.e., for any decided pairs (c, v), (c ′ , v ′ ), c = c ′ =⇒ v = v ′ (agreement). Intuitively, processes are trying to solve simultaneously k instances of the consensus problem in such a way that each process decides in at least one instance. For any instance, decisions occurring in that instance must be consistent with the validity and agreement requirements of consensus. A decided pair (c, v) may thus be interpreted as follows: value v is decided in the cth instance of consensus.

While k-set agreement weakens the safety property of consensus by allowing k values to be decided, k-parallel consensus may be though as weakening its liveness property by considering k instances in parallel, and allowing some instances to remain undecided. Practically, parallel consensus might be useful in situations where processes participate concurrently in k different applications: a kparallel consensus protocol can guarantee progress in at least one application [START_REF] Gafni | Generalized universality[END_REF], [START_REF] Gafni | The committee decision problem[END_REF].

Failure detectors: A failure detector is a distributed oracle that provides processes with possibly unreliable information on failures [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. According to the quality of the information, several classes of failure detectors can be defined and may be used to solve otherwise impossible problems. For example, an eventual leadership failure detector (Ω, [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]) provides the processes with an id which is eventually 1) the same at each process and, 2) the id of a non-faulty process. Whereas k-set agreement cannot be solved in asynchronous message passing systems in which at most t processes may fail if k ≤ t, [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF] presents an asynchronous Ω-based k-set agreement protocol that tolerates up to t process failures, for any t, k ≤ t < kn k+1 .

A failure detector D is necessary for solving a distributed problem P if given any failure detector D ′ that can be used to solve P , it is possible to emulate D. It has been shown that a failure detector called Σ k is necessary for k-set agreement in message passing systems [START_REF] Bonnet | On the road to the weakest failure detector for k-set agreement in message-passing systems[END_REF].

k-set agreement vs. k-parallel consensus: The paper investigates the relative hardness of k-set agreement and k-parallel consensus in n-process asynchronous messages passing systems with crash failures. Let t < n denote the bound on the number of failures.

Clearly, if a protocol for k-parallel consensus is provided, one can solve k-set agreement. A fundamental result in [START_REF] Afek | The k-simultaneous consensus problem[END_REF] is that the converse is true in asynchronous shared memory system. That is, both problems are computationally equivalent in shared memory: given any wait-free 2 protocol for k-set agreement (respectively, for k-parallel consensus), one can construct a wait-free protocol for k-parallel (respectively, for k-set agreement).

The equivalence has been instrumental in determining the weakest failure detector for k-set agreement in asynchronous shared memory systems [START_REF] Gafni | The weakest failure detector for solving k-set agreement[END_REF], [START_REF] Zielinski | Anti-omega: the weakest failure detector for set agreement[END_REF], a question which is still unsolved for message passing systems. In addition, while many k-set agreement protocols for messages passing systems with various synchrony assumptions or augmented with failure detectors have been proposed, e.g., [START_REF] Aguilera | Partial synchrony based on set timeliness[END_REF], [START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF], [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF], [START_REF] Delporte-Gallet | The weakest failure detector for message passing setagreement[END_REF], [START_REF] Mostéfaoui | On the computability power and the robustness of set agreementoriented failure detector classes[END_REF], [START_REF] Mostéfaoui | Relations linking failure detectors associated with k-set agreement in messagepassing systems[END_REF], [START_REF] Parvédy | Strongly terminating early-stopping k-set agreement in synchronous systems with general omission failures[END_REF], to the best of our knowledge no specific protocol is known for k-parallel consensus. A first step to remedy this situation will consist in a generic transformation for turning any k-set agreement protocol into a k-parallel consensus protocol, if such a transformation exists.

The equivalence extends to asynchronous process message passing systems when a majority of processes are nonfaulty (i.e., t < n 2 ), as in this case shared memory can be emulated t-resiliently [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF]. The question addressed in this paper is whether the equivalence between the two problems extends beyond the majority threshold. Our main result is that the answer is "no": we show that if t > n+k-2

2

, kparallel consensus is strictly harder than k-set agreement in an asynchronous n-process messages passing systems in which at most t processes can fail by crashing.

Contributions of the paper:

We study both problems through the lens of the amount of information on failures required to solve them. This is usually captured in the framework of failure detectors. On one hand, it is known that failure detector (Σ k × Ω) is sufficient for k-set agreement [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF]. On the other hand, we identify a new class of failure detectors, namely V Σ k , and show that it is necessary for k-parallel consensus (Section IV). The question of whether k-parallel consensus can be solved t-resiliently using a kset agreement protocol thus boils down to whether V Σ k 2 A wait-free protocol tolerates any number of crash failures. can be emulated t-resiliently from Σ k × Ω (Section VI). If t is small enough, namely t < kn k+1 , Σ k can be emulated t-resiliently without relying on any failure detector. In this case, it is enough to study for which values of t failure detector V Σ k can be implemented t-resiliently (Section V). It is shown that n-k+2 2 is a tight threshold. Interestingly, the proof relies on the chromatic number of a certain class of graphs, namely Kneser graphs. Finally, Section VII presents our main impossibility results, obtained by assembling the various pieces from the previous sections.

Table I summarizes the main contributions of the paper. k-SA and k-PC are shorthands for k-set agreement and kparallel consensus respectively. MP n,t denotes a message passing system made of n processes, t of which may crash. MP n,t [Ω] stands for system MP n,t equipped with a failure detector Ω. X ≃ X ′ , X ≺ X ′ , X X ′ mean respectively that X and X ′ implements each other, X ′ implements X but X ′ does not implement X, X ′ implements X. See Section II for more details about the notations. Due to space limitations, some proofs are missing. They can be found in a companion technical report [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message Passing[END_REF].

II. PRELIMINARIES

Message passing asynchronous distributed system: We consider a distributed system made of a set Π of n asynchronous processes {p 1 , . . . , p n }. Each process runs at its own speed, independently of the other processes.

Processes communicate by sending and receiving messages over a reliable but asynchronous network. Each pair of processes {p i , p j } is connected by a bi-directional channel. Channels are reliable and asynchronous, meaning that each message sent by p i to p j is received by p j after some finite, but unknown, time; there is no global upper bound on message transfer delays.

The system is equipped with a global clock whose ticks range T is the set of positive integers. This clock is not available to the processes, it is used from an external point of view to state and prove properties about executions.

Failures: Processes may fail by crashing. A process that crashes prematurely halts and never recovers. In an execution, a process is faulty if it fails and correct otherwise. A failure pattern is a function F from T to Π where F(τ ) is the set of processes that have failed by time τ . We define Correct(F) and F aulty(F) = Π\Correct(F) to be the set of correct processes and the set of faulty processes according to F, respectively. When F is clear from the context, we simply write Faulty and Correct instead of Faulty(F) and Correct(F) respectively.

An environment (or adversary [START_REF] Delporte-Gallet | The disagreement power of an adversary[END_REF]) is a set of failure patterns. The wait-free environment consists in all failure patterns in which at least one process is correct. For 1 ≤ t ≤ n -1, the t-resilient environment contains every failure pattern in which no more than t processes are faulty (the (n -1)-resilient environment is the wait-free environment).

t 0 n 2 n+k-2 2 kn k+1 n MPn,t Σ k implementable Σ k not implementable [14], Section V V Σ k implementable V Σ k not implementable Section V Σ k ≃ V Σ k Σ k ≺ V Σ k Section VI k-SA ≃ k-PC k-SA k-PC k-SA ≺ k-PC [6],
Failure detectors: Informally, a failure detector [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] is a distributed oracle that provides (perhaps inaccurate) hints on the current failure pattern of the execution. Operationally, a failure detector provides at each process p i a read-only variable FD i , whose value at time τ is denoted FD τ i . This value is the output of the failure detector for process p at time τ .

We recall next the main features of the framework in which failure detectors are defined, as introduced in [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. A failure detector history H with range R is a function H : Π × T → R. H(p i , τ ) may be seen as the output of the local failure detector module of process p i at time τ . A failure detector D with range R D is a function that maps each failure pattern to set of failure detector histories with range R D . Given a failure pattern F, D(F) denotes the set of failure detector histories allowed by D when the failure pattern is F.

For example, the range of the quorum failure detector Σ, defined in [START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF] is 2 Π , the set of all subsets of Π.

H : Π×T → 2 Π ∈ Σ(F) iff ∀τ, τ ′ ∈ T, ∀p i , p j ∈ Π : H(p i , τ )∩ H(p j , τ ′ ) = ∅ and ∃τ c ∈ T : ∀p i ∈ Correct(F ), ∀τ ≥ τ c , H(p i , τ ) ⊆ Correct(F).
That is, any two sets output by the failure detector intersect and eventually, for every correct process, the output of Σ contains only correct processes.

Comparing failure detectors: Let D1, D2 denote two failure detectors. Failure detector D1 is weaker than D2 in environment E, denoted D1 D2, if there exists a distributed algorithm T D2→D1 that uses D2 to emulate the output of D1. More specifically, algorithm T D2→D1 maintains at each process p i a variable OUT D1 intended to emulate the output of D1 at p i ; The variable can be used at each process to replace the actual output of D1: in any execution, p i cannot distinguish between reading the variable OUT D1 or querying the failure detector D1. If D1 is weaker than D2 and D2 weaker than D1 in environment E, D1 and D2 are said to be equivalent in E (denoted D1 ≃ D2). On the contrary, if D2 is not weaker than D1, D1 is strictly weaker than D2 (denoted D1 ≺ D2).

Given a distributed task T , such as consensus, failure detector D is a weakest failure detector for T in environment E if [START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF] there exists an algorithm A D for T in E that uses D and (2) for every failure detector D ′ that can be used to solve T in E, there exists an algorithm T D ′ →D that uses D ′ to emulate D. Note that if D1 and D2 are weakest failure detectors for T , then D1 ≃ D2.

Comparing tasks: Given two distributed tasks T 1 and T 2 defined for n processes, task T 1 implements task T 2 in environment E if, given a protocol for T 1, one can construct a protocol for T 2 in E by interleaving steps of a message passing protocol with calls to any number of instances of the protocol for T 1. The protocol for T 1 is a "black-box": it is only required that it solves T 1 in E. We say that T 1 is

harder than T 2 in E if T 1 implements T 2 whereas T 2 does not implement T 1.
Notations: Given var i a local variable of process p i , we denote by var τ i its value at time τ . MP n,t denotes a nprocess asynchronous message passing system in which at most t processes may fail.

III. THE FAILURE DETECTORS

Σ k , V Σ k AND Ω
This section recalls the definition of the failure detector classes Σ k , Ω and introduces the new class V Σ k . For each process p i , FD τ i denotes the value output by the failure detector at time τ .

The family {Σ k } 1≤k≤n : A failure detector of the class Σ k maintains at each process a variable QUORUM i that contains at any time a set of process ids. The sets output, called quorums, satisfy the following properties:

• Intersection. Any set containing at least k+1 quorums has two intersecting quorums. Formally, let Q be the set of all quorums output at all the processes at all times. That is,

Q = {B | ∃p i ∈ Π, ∃τ ∈ T : QUORUM τ i = B}. Then, for every X ⊆ Q with |X| > k : ∃B, B ′ ∈ X : B ∩ B ′ = ∅.
• Liveness. Eventually, for each correct process, every quorum contains only correct processes ids. That is, ∃τ ∈ T : [START_REF] Bonnet | On the road to the weakest failure detector for k-set agreement in message-passing systems[END_REF] where it is shown to be necessary to solve k-set agreement in message passing systems. A (Σ k × Ω)-based protocol tolerating any number of process crashes that solves k-set agreement is presented in [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF]. The class Σ 1 is the same as Σ, the weakest failure detector to implement a register in crash-prone message passing systems [START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF].

∀p i ∈ Correct, ∀τ ′ ≥ τ : quorum τ ′ i ⊆ Correct Σ k was introduced in
The eventual leader failure detector Ω: A failure detector of the class Ω maintains at each process p i a variable LEADER i that contains a process id. It satisfies the following property:

• Eventual leadership. Eventually, for every correct process p i , LEADER i contains forever the same identity of a correct process. That is,

∃p ℓ ∈ Correct, ∃τ ∈ T : ∀τ ′ ≥ τ, ∀p i ∈ Correct, LEADER τ ′ i = ℓ. (Ω × Σ)
is the weakest failure detector for consensus in message passing systems in any environment [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF], [START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF].

The family {V Σ k } 1≤k≤n : The failure detector V Σ k (read Vector-Σ k ) outputs at each process p i an array QUORUMS i of size k. At any time, each component QUORUMS i [c], 1 ≤ c ≤ k of the array contains a set of process ids (a quorum). Intuitively, a failure detector V Σ k may be seen as k instances of a failure detector of the class Σ. In each instance, the intersection property of the class Σ is satisfied, whereas the liveness property may not hold. It is only required that liveness is satisfied in at least one instance. Formally:

• Intersection. Any two quorums output in the same entry c at the same process or at distinct processes intersect. That is, ∀c,

1 ≤ c ≤ k, ∀τ, τ ′ ∈ T, ∀p i , p i ′ ∈ Π : QUORUMS τ i [c] ∩ QUORUMS τ ′ i ′ [c] = ∅. • Liveness.
There exists some entry c such that, eventually, every quorum output in this entry at any correct process contains only correct processes. That is,

∃τ ∈ T, ∃c, 1 ≤ c ≤ k : ∀p i ∈ Correct, ∀τ ′ ≥ τ, QUORUMS τ ′ i [c] ⊆ Correct. IV. NECESSITY OF V Σ k FOR k-PARALLEL CONSENSUS
This section shows that failure detector V Σ k is necessary for solving k-parallel consensus. That is, failure detector D can be used to solve k-parallel consensus, then V Σ k can be emulated using D.

Theorem IV.1. For all t, k, 1 ≤ t, k ≤ n, for any protocol A and any failure detector

D, if A solves k-parallel consensus in MP n,t [D] then V Σ k D.
The strategy of the proof is similar to the one in [START_REF] Bonnet | On the road to the weakest failure detector for k-set agreement in message-passing systems[END_REF]. There, it is shown that failure detector Σ k is necessary to solve k-set agreement in message passing systems. The proof is simple and elegant, and, as we are about to see, can be generalized to the case of k-parallel consensus.

A protocol that emulates a failure detector V Σ k is described in Figure 1. Recall that we are given an algorithm A and a failure detector D such that A solves k-parallel consensus in MP n,t [D]. We assign for each set S ∈ 2 Π an instance of A denoted A S . Each process p i participates in instance A S only if p i ∈ S. The value proposed by p i in this instance is S, i . In more details, algorithm A consists in n automata A 1 , . . . , A n , one per process. Process p i starts 2 n-1 copies of A i , one copy, denoted A S i , for each set S ∈ 2 Π : i ∈ S. The proposal of p i in A S i is S, i and each message sent by A S i is tagged for the purpose of not confusing messages sent in different instances of A. When a receive step is performed in A S i , a message with tag S (if any) is selected from p i 's input message buffer and delivered to the automata. Failure detector queries are performed normally: when a failure detector value is needed by A S i , the local failure detector module of p i is queried. p i performs steps of each automata A S i , i ∈ S in any fair way, for example in a round-robin fashion.

The output of the failure detector V Σ k at process p i consists in a k-component array OUT i . Process p i maintains in addition a k-component array of sets denoted

Q i . If p decides (c, d) in instance A S , set S is added to the cth component of Q i [c]. For each c, 1 ≤ c ≤ k, p i periodically strives to assign to the cth component of OUT i a set S ∈ Q i [c] that contains only correct process (if Q i [c]
contains such a set). To that end, each process periodically broadcasts HEARTBEAT messages (task T2). HEARTBEATs are used to rank processes id. Process p i maintains an ordered list order i of processes ids. Each time a HEARTBEAT from process p j is received, j is moved at the beginning of the list (Task T3). As each faulty process sends finitely many HEARTBEATs, there exists a time after which each correct process id appears before any faulty process id. Therefore, given two sets S, S ′ of process, S ⊆ Correct and S ′ ⊆ Correct, the largest rank of the ids of the processes in S is eventually always smaller than the largest rank of the ids in S ′ . When p i updates OUT i [c], it selects a set S that has the smallest largest rank of its ids among the sets currently in

Q i [c] output by V Σ k (lines 5-7). If Q i [c] contains a set of correct processes, this guarantees that eventually OUT i [c] ⊆ Correct.
Process p i may not decide in every instance A S in which it participate, as it may wait forever for messages from some process p j , j / ∈ S. However, for any S such that Correct ⊆ S, every correct process that participates in A S , must eventually decide since A correctly solves k-parallel consensus. Hence, some component c i of Q i eventually contains a set of correct processes, and therefore, OUT i [c i ] is eventually a subset of the correct processes. Moreover, the protocol ensures that when a set S is added to Q i [c i ], it is eventually added to the c i th component of every Q j , for every correct process p j (tasks T1 and T4). It thus follows that eventually at each correct process p j , OUT j [c] ⊆ Correct for some c, 1 ≤ c ≤ k, thereby ensuring the liveness property of the class V Σ k .

For the intersection property of the class V Σ k , it remains to see that for any two sets S, S ′ assigned to the cth component of the emulated failure detector output, perhaps at different processes, S ∩ S ′ = ∅, for any c, 1 ≤ c ≤ k. Note that S, S ′ are assigned to the cth component of the emulated failure detector only if (c, d) and (c, d ′ ) are decided in instances A S and A S ′ respectively.

Let S, S ′ be two disjoint subsets of Π. Suppose that processes p ∈ S and p ′ ∈ S ′ decide the pairs (c, d) and (c ′ , d ′ ) in A S and A S ′ respectively. We demonstrate that, in this case, c = c ′ . First, as any value proposed in A S (respectively, in A S ′ ) is of the form S, j (respectively, S ′ , j ), where p j ∈ S (respectively, p j ∈ S ′ ) d = d ′ by the validity of property of k-parallel consensus. Second, because S ′ ∩ S = ∅, prefixes of the executions of A S and A S ′ can be "merged" in a single execution of A in which the set of participating processes is S ∪ S ′ . That is, there exists a single execution α of A that is indistinguishable from the execution of A S (respectively, of A S ′ ) for p (respectively, for p ′ ). p and p ′ thus decide respectively (c, d) and (c ′ , d ′ ) in α. As d = d ′ , it thus follows that c ′ = c. A proof can be found in the full version [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message Passing[END_REF].

init Q i [1..k] ← [{Π}, . . . , {Π}]; /* array of set of sets */ order i ← (1, . . . , n); /* ordered list of processes ids */ OUT[1..k] ← [Π, . . . , Π]; /* V Σ k output */ for each S ∈ 2 Π : i ∈ S do
launch an instance A S i of A i with input S, i enddo /* instances run in parallel independently */ start tasks T1,T2,T3,T4 task T1: when p i decides in A S i : (1) let (c, d) be the decision of

p i ; Q i [c] ← Q i [c] ∪ {S};
(2) send (c, S) to all /* d = S, j for some j ∈ S */ task T2: repeat periodically (3) send HEARTBEAT(i) to all task T3: when HEARTBEAT(j) is received: (4) move j at the head of the list order i (5) for each c :

1 ≤ c ≤ k do OUT i [c] ← E (6) where E ∈ Q i [c] and ∀S ∈ Q i [c], (7)
max j∈E rank(j, order i ) ≤ max j∈S rank(j, order i ) /* rank(j, order i ): rank of j in the ordered list order i */ task T4: when (c, S) is received:

(8) Q i [c] ← Q i [c] ∪ {S}; Figure 1. Emulation of V Σ k from an algorithm A that uses a failure detector D to solve k-parallel consensus (code for p i ) V. t-RESILIENT PROTOCOLS FOR V Σ k AND Σ k
This section investigates whether there is a t-resilient protocol for implementing a failure detector Σ k or V Σ k . For the class Σ k , the answer is known [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF]. For completeness, the result is recalled at the end of this section (Theorem V.5).

For the class V Σ k , we show that the existence of a protocol emulating a failure detector V Σ k is strongly related to the chromatic number of a certain family of graphs, namely, Kneser graphs. We show that there exists a tresilient protocol that emulates a failure detector V Σ k if and only if the Kneser graph KG n,n-t has a proper vertex k-coloring.

A. t-resilient emulation of V Σ k
This section is devoted to the proof of the following Theorem: The Kneser graph KG n,k is the undirected graph whose vertices are the subsets of k elements of a set of size n, and where two vertices share an edge whenever the two corresponding sets are disjoint. For example, KG n,1 is the complete graph, and KG 5,2 is isomorphic to the Petersen graph. An important result about Kneser graphs is their chromatic number. The chromatic number χ(KG n,k ) of the Kneser graph is exactly n -2k + 2 if n ≥ 2k, and 1 otherwise. This result was conjectured by Martin Kneser early in 1955 and proved for the first time by Lovász [START_REF] Lovász | Kneser's conjecture, chromatic number, and homotopy[END_REF] in 1978. His proof was the first one using algebraic topology to solve a problem in combinatorics, giving rise to the field of topological combinatorics. Simpler proofs were later given by Bárány [START_REF] Bárány | A short proof of kneser's conjecture[END_REF], Greene [START_REF] Greene | A new short proof of kneser's conjecture[END_REF] and Matoušek [START_REF] Matoušek | A combinatorial proof of knesers conjecture[END_REF].

Theorem V.1. Let n,
Kneser graphs, and their chromatic number are central to show that it is impossible to emulate t-resiliently V Σ k for certain values of n, k and t. We reduce the existence of a protocol that emulates V Σ k in MP n,t to the problem of whether k colors are sufficient to properly color KG n,n-t (Lemma V.2). Conversely, we show that if V Σ k can be emulated in MP n,t , there is a k-coloring of KG n,n-t (Lemma V.3).

A t-resilient protocol emulating V Σ k : A simple algorithm that emulates a failure detector of the class V Σ k in MP n,t is described in Figure 2. The algorithm requires that t ≤ n+k-2 2

. The algorithm relies on a k-coloring of the Kneser graph KG n,n-t . As seen in the preliminaries, the chromatic number of

KG n,n-t is χ(KG n,n-t ) = n -2(n -t) + 2 = 2t -n + 2 ≤ k if n ≥ 2(n -t) and 1 otherwise. Therefore, for t ≤ n+k-2 2
, the graph KG n,n-t can be properly colored with k colors.

The processes are initially provided with a function color that maps each subset of Π of size nt to an integer in the range [1, k] such that any two disjoint sets are mapped to distinct integers. That is, color is a k-coloring of KG n,n-t . Since the chromatic number of this graph is χ(KG n,n-t ) = 2tn + 2 if n ≥ 2(nt) and 1 otherwise, the function color does exist as t ≤ n+k-2 2 . Each process p i maintains a vector of sets of processes OUT i [1..k] intended to contain the output of the emulated failure detector V Σ k . Each entry of OUT i is initially equal to Π, the set of processes ids in the system. To ensure the liveness property of V Σ k , i.e., the existence for each correct process p i of an entry ℓ i such that eventually, the ℓ i th entry of OUT i contains only correct processes ids, each process periodically broadcasts HEARTBEAT (line 1). When a HEARTBEAT is received from some process p j , the identity of p j is added to the local set Q i (line 2). Whenever nt distinct ids have been accumulated in Q i , the output of V Σ k is updated as follows. The current set S of ids in Q i is assigned to the cth entry of OUT i , where c is the color of S (line 3). Then p i broadcasts Q i together with its color c in a QUORUM message. Finally, Q i is reset to the empty set. When a QUORUM(Q j , c) message is received from p j , the cth element of OUT i is updated to Q i .

Note that it thus follows that eventually, some entry of the output of V Σ k at all processes contains only correct processes, as every faulty process eventually stops sending HEARTBEATs messages, and thus its id eventually stops occurring in Q i . Moreover, using the map color to assign sets of (nt) processes ids to entries of the vector OUT i guarantees the intersection property of V Σ k . Indeed, by definition of the map color, two sets are assigned to the same entry only if they intersect.

init OUT i [1..k] ← [Π, . . . , Π]; /* output of V Σ k */ color : {S ⊆ Π : |S| = n -t} → {1, . . . , k}; /* k-coloring of KG n,n-t */ Q i ← ∅;
/* set of processes ids, initially empty */ start task T1,T2,T3 task T1: repeat periodically (1) send HEARTBEAT(i) to all task T2: when HEARTBEAT(j) is received:

(2) Q i ← Q i ∪ {j}; (3) if |Q i | = n -t then let c = color(Q i ); OUT i [c] ← Q i ; (4) send QUORUM(Q i , c) to all; Q i ← ∅ endif task T3: when QUORUM(Q, c) is received: (5) OUT i [c] ← Q Figure 2. Emulation of V Σ k in MPn,t, t ≤ n+k-2 2 (code for p i )
Lemma V.2. Let n, t, k be integers such that 1 ≤ t, k ≤ n and t ≤ n+k-2

2

. The algorithm described in Figure 2 implements a failure detector V Σ k in MP n,t .

Proof: The proof is divided in two parts corresponding to the two properties of the class V Σ k , namely liveness and intersection. Liveness. Define τ to be the time at which: (i) all faulty processes have already crashed, (ii) all messages sent by them have already been received by correct processes. There exists a time τ ′ ≥ τ such that for every correct process p i , the processes that are accumulated in Q i at any time after τ ′ are correct. This is because there are at least nt correct processes, and each of them never stops sending HEARTBEAT messages (line 1). Let Q ⊆ Correct be any set of nt ids accumulated by a given correct process p ℓ after τ ′ , say at τ ℓ . Let c denote color(Q). Every process p j ∈ Correct \ {p ℓ } will receive the message QUORUM(c, Q) from p ℓ , say at τ j . Hence for every

p i ∈ Correct, OUT i [c] contains Q at τ i . After τ i , since τ i ≥ τ ′ , whether OUT i [c]
is updated (as a result of accumulating a new set of ids by p i or receiving a QUORUM message) or not, its value is necessarily a subset of Correct. Intersection. Let ℓ, 1 ≤ ℓ ≤ k and let S i , S j be two sets of processes ids corresponding to the ℓth entry of the output of the emulated failure detector at some processes p i and p j (with p i not necessarily distinct from p j ). That is, at some time τ i (respectively, τ j ), OUT i [ℓ] = S i (respectively, OUT j [ℓ] = S j ). If S i or S j is equal to Π, S i ∩ S j = ∅ as OUT i [ℓ] and OUT j [ℓ] always contain processes ids. Otherwise, S i is the value of the variable Q i at some time, and ℓ is the color assigned to the set S i by the map color . Similarly, color maps S j to ℓ. Since disjoint sets are mapped to distinct colors, it follows that S i ∩ S j = ∅.

An impossibility result: We now prove that the condition linking t, k and n of Lemma V.2 is tight for the existence of a protocol that emulates V Σ k in MP n,t : Lemma V.3. Let n, t, k be integers such that 1 ≤ t, k ≤ n and n+k-2 2 < t. There is no algorithm that emulates a failure detector of the class V Σ k in MP n,t .

We actually prove this Lemma as a corollary of a slightly more general result:

Lemma V.4. Let n, t, k be integers such that 1 ≤ t, k ≤ n and n+k-2 2 < t. There is no algorithm that emulates a failure detector of the class V Σ k in MP n,t [Ω].
Proof: The proof is by contradiction. Assume that there exists an algorithm A that implements a failure detector

V Σ k in MP n,t [Ω] with n+k-2 2 < t, i.e, k < 2t -n + 2.
We show that we can use A to properly color KG n,n-t with k colors. This contradicts the fact that the chromatic number of KG n,n-t is χ(KG n,n-t ) = 2tn + 2 when t ≥ n 2 and 1 otherwise.

Let S = S 1 , . . . , S u , u = n n-t be an enumeration of all subsets of Π of size nt. We construct an execution α of A from which we derive a proper k-coloring of KG n,n-t . The construction proceeds inductively by forming longer and longer prefix α i of α. At the end of α i , each set S j , 1 ≤ j ≤ i has received a color c j , 1 ≤ c j ≤ k such that any two disjoint sets receive distinct colors.

Base step. Let α ′ 1 be an execution of A in which the set of correct processes is S 1 . Moreover, the faulty processes are initially crashed in α ′ 1 . At each process p i ∈ S 1 , the output of the failure detector Ω is the same process id ℓ 1 , where p ℓ1 ∈ S 1 . Let p j be a process in S 1 . By the liveness property of V Σ k , there exists a time τ 1 and an entry c 1 such that, at time τ 1 , the c 1 th entry of the failure detector output at process p j is a set S ⊆ S 1 . This is because S 1 is the set of correct processes in α ′ 1 and eventually one entry of the vector output by V Σ k at each correct process must contain only correct processes ids.

In execution α 1 , no process fails. However, processes in Π\S 1 do not take a step before time τ 1 . Moreover, execution α 1 and α ′ 1 are indistinguishable up to time τ 1 for every process in S 1 . In particular, for every process in S 1 , the output of Ω until time τ 1 is ℓ 1 . Hence, as in execution α ′ 1 , process p j ∈ S 1 output at time τ 1 a vector whose c 1 th entry is a set contained in S 1 . We then let every process take enough steps for every message sent before τ 1 to be received. The color c 1 is assigned to S 1 .

Induction step. Suppose that the prefix α i has been constructed, for some i, 1 ≤ i < u. We describe how to extend α i to form the prefix α i+1 .

Let α ′ i+1 be an execution of A that extends α i and in which the set of correct processes is S i+1 . More precisely, α i is a prefix of α ′ i+1 and every process in Π \ S i+1 fails immediately after α i . Processes in S i+1 then keep taking steps forever and, after α i , the output of Ω at each process in S i+1 is the same id ℓ i+1 for some process p ℓi+1 ∈ S i+1 . The eventual leadership property of the class Ω is thus satisfied. Let p j be an arbitrary process in S i+1 . As in the base case, it follows from the liveness property of the class V Σ k that there exists an entry c i+1 such that eventually the c i+1 th entry of the vector output by A at p j is included in S i+1 , which is the set of correct processes in that execution. Let τ i+1 be a time following α i at which this occurs.

Execution α i+1 and α ′ i+1 are indistinguishable for every process in S i+1 up to time τ i+1 . In particular, for every process in S i+1 , the output of Ω is ℓ i+1 after α i and until time τ i+1 , and processes in Π\S i+1 take no step after α i and until τ i+1 . After τ i+1 , we let each process takes enough step in order to every message sent before τ i+1 to be received. As α i+1 and α ′ i+1 are indistinguishable for every process in S i+1 , the c i+1 th entry of the vector output by A at process p j at time τ i+1 is the same as in α ′ i+1 , that is a set included in S i+1 . We assign the color c i+1 to S i+1 .

Final step. Suppose we have constructed prefix α u as described above. Execution α is an infinite execution with prefix α u . After α u , each process takes infinitely many steps, for example in round-robin fashion; the output of Ω at each process is the same id of some arbitrary correct process.

Every message sent is eventually received.

Note that execution α is a valid execution of A in MP n,t [Ω] with no failure. In particular, note that since after prefix α u , the underlying failure detector outputs the same correct process id at every process, the failure detector history is a valid history for a failure detector of the class Ω. The output of A must therefore fulfill the properties of the class V Σ k . We claim that the coloring of each S i ,

1 ≤ i ≤ u with c i , 1 ≤ i ≤ u, as indicated in the construction is a proper k-coloring of KG n,n-t .
Notice first that each c i is an entry of the vector of size k output by A, i.e., 1 ≤ c i ≤ k. Finally, let S i , S j be two sets such that S i ∩ S j = ∅. By construction, at time τ i , the c i th entry of the vector output by A at some process is a set s i ⊆ S i . Similarly, at time τ j , the c j th entry of the vector output by A at some process is a set s j ⊆ S j . As S i ∩ S j = ∅, we have s i ∩ s j = ∅. It thus follows from the intersection property of V Σ k that c i = c j , as desired.

As 1 ≤ k, and n+k-2

2 < t, it follows that 2(n -t) ≤ n. The chromatic number of KG n,n-t is thus χ(KG n,n-t ) = n -2(n -t) + 2 = 2t -n + 2. This is a contradiction since we have k < 2t -n + 2.
Lemma V.3 is a consequence of Lemma V.4, as any protocol emulating V Σ k in MP n,t emulates V Σ k in any system in which a failure detector is available. Theorem V.1 then immediately follows from Lemma V.2 and Lemma V.3.

B. t-resilient emulation of Σ k

For completeness, we recall here the condition linking the parameters t, k and n under which there exists a t-resilient protocol emulating a failure detector Σ k : Theorem V.5 ([13]). Let n, k, t be integers such that 1 ≤ t, k ≤ n. There exists a protocol that emulates a failure detector Σ k in MP n,t if and only if t < kn k+1 .

VI. {V Σ k } 1≤k≤n VS. {Σ k } 1≤k≤n
This section compares the two families {V Σ k } 1≤k≤n and {Σ k } 1≤k≤n . For establishing that k-set agreement is weaker than k-parallel consensus, we are mainly interested in the values of parameters n, t, k for which V Σ k can be emulated in MP n,t [Σ k ]. This is because Σ k can be used to solve k-set agreement and V Σ k is necessary for k-parallel consensus. Hence, a protocol that uses a k-set agreement protocol to solve k-parallel consensus in MP n,t implies that V Σ k can be emulated in MP n,t [Σ k ]. Nevertheless, for completeness, we also study for which values of the parameters n, t and k a failure detector Σ k can be emulated in MP n,t [V Σ k ] (Section VI-B).

A. Emulation of V Σ k ′ in MP n,t [Σ k ]
The values of t, n, k and k ′ for which a failure detector V Σ k ′ can be emulated in MP n,t [Σ k ] are completely characterized by the following theorem:

Theorem VI.1. Let n, t, k, k ′ , 1 ≤ k, k ′ , t < n. There is a protocol that emulates a failure detector V Σ k ′ in MP n,t [Σ k ] if and only if k = 1 or t ≤ n+k ′ -2 2 . Proof: If t ≤ n+k ′ -2 2
, we know from Lemma V.2 that there is a protocol that emulates V Σ k ′ in MP n,t , and thus also in

MP n,t [Σ k ]. If k = 1, V Σ k ′ can be emulated in MP n,t [Σ]
by simply replicating k ′ times the outputs of Σ.

Suppose now that k ≥ 2 and t > n+k ′ -2

2

. Assume for contradiction that there exists a protocol A that emulates

V Σ k ′ in MP n,t [Σ k ].
Let S 1 , . . . , S u , u = n n-t be every subset of Π of size nt. For every S i ∈ S, let α i be an execution of A in which (1) the set of correct processes is S i , (2) each faulty process fails initially and (3) the output of the underlying failure detector Σ k is always S i , at every process. By the liveness property of the class V Σ k ′ , there exists a time τ i and c i , 1 ≤ c i ≤ k ′ such that the c i th entry of the vector output by V Σ k ′ at some correct process in α i is a set s i ⊆ S i . Now, we show that there exists S j , S ℓ such that S i ∩ S j = ∅ and c j = c ℓ = c. Assume not for contradiction. This means that f :

S i → c i is a k ′ -coloring of KG n,n-t . Therefore, the chromatic number of KG n,n-t is χ(KG n,n-t ) ≤ k ′ . As t > n+k ′ -2 2
, it follows that k ′ < 2tn + 2. Contradiction! Let α be an execution of A defined as follows. The set of correct processes in α is S j ∪ S ℓ . At each process in S j (respectively, S ℓ ), the output of Σ k is always S j (respectively, S ℓ ). Since k ≥ 2, this is a valid output for Σ k in an execution where the set of correct processes is S j ∪ S ℓ . Faulty processes do not take a step in α. As for correct processes, each message sent by the processes in S j (respectively, S ℓ ) before time τ = max(τ j , τ ℓ ) is delayed if it is sent to a process in S ℓ (respectively, S j ). Otherwise it is received as in α j (respectively, α ℓ ). After time τ , every delayed message is received, and every message sent after that time is eventually received.

Up to time τ , α and α j are thus indistinguishable for any processes in S j and, similarly, α and α ℓ are indistinguishable for any processes in S ℓ . Therefore, in α, the cth(= c j = c ℓ ) entry of the vector output by A is a set s j ⊆ S j at some process, and a set s ℓ ⊆ S ℓ at some other process. As S j ∩ S i = ∅, this contradicts the intersection property of the class V Σ k ′ .

The impossibility part of the Theorem can be extended to the case in which a failure detector Ω is available:

Corollary VI.2. Let n, t, k, k ′ , 1 ≤ k, k ′ , t < n. There is no protocol that emulates a failure detector V Σ k ′ in MP n,t [Σ k × Ω] if k ≥ 2 and t > n+k ′ -2 2 .
Proof: Essentially the same strategy as in the previous proof can be reused. What is left undefined in the executions α i considered there is the output of the failure detector Ω. In each α i , 1 ≤ i ≤ u, Ω may always outputs the same process q ∈ S i at each process. Then, in the definition of α, the output of Ω is the same as in α j (respectively, α ℓ ) up to time τ for each process in S j (respectively, S ℓ ). After time τ , the output of Ω is the same process ∈ S i ∪ S ℓ at every correct process in α. This is consistent with the eventual leadership property of the class Ω and does not help each process in S j (respectively, S ℓ ) to distinguish until time τ between α j (respectively, α ℓ ) and α.

B. From V Σ k to Σ k
Next theorem complements Theorem VI.1 by characterizing the values of the parameters t, n and k ′ for which it is possible to t-resiliently emulate Σ k ′ when a failure detector V Σ k is available. The proof can be found in the full version [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message Passing[END_REF].

Theorem VI.3. Let n, t, k, k ′ , 1 ≤ k, k ′ , t < n. There is a protocol that emulates a failure detector Σ k ′ in MP n,t [V Σ k ] if and only if k ≤ k ′ or t < k ′ n k ′ +1 . VII. SEPARATION RESULTS
This section glues together the results presented in Section IV, Section V and Section VI to establish the following main theorem:

Theorem VII.1. Let n, t, k, k ′ , 1 ≤ k, k ′ ≤ t < n such that 2 ≤ k and n+k ′ -2 2 < t. There is no protocol for k ′ -parallel consensus in MP n,t [k-SA].
The proof strategy is as follows: On one hand, it has been shown in [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF] that k-set agreement can be solved in MP n,t [Ω × Σ k ], for any value of t. On the other hand, we have seen that V Σ k ′ is necessary for solving k ′ -parallel consensus (Theorem IV.1). The impossibility of a t-resilient solution to k ′ -parallel consensus using a k-set agreement protocol thus reduces to the impossibility of a t-resilient emulation of V Σ k ′ based on Ω × Σ k . The latter has been answered in the previous Section (Corollary VI.2).

Proof: Let k ≥ 2 and t > n+k ′ -2

2

. The proof is by contradiction. Assume that there exists a k ′ -parallel consensus protocol A in MP n,t [k-SA]. More precisely, A uses any number of copies of a k-set agreement protocol B to solve k ′ -parallel consensus. Protocol B is any t-resilient protocol for k-set agreement. No assumption is made regarding the internals of protocol B. It particular, B might be a failure detector-based protocol.

It is known that k-set agreement can be solved in MP n,t [Ω × Σ k ] [13] -the protocol presented there imposes no requirement on t and k. B may thus be the protocol presented in [START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF]. Therefore, by combining protocol A and B, it follows that k ′ -parallel consensus can be solved in

MP n,t [Ω × Σ k ].
In section IV, we have shown that V Σ k is necessary for k ′ -parallel consensus. That is, if there is a k ′ -parallel consensus protocol using a failure detector D, then one may use D to emulate a failure detector of the class V Σ k . As k ′ -parallel consensus can be solved in MP n,t [Ω × Σ k ] by combining protocols A and B, it thus follows that there exists a protocol T that emulates

V Σ k in MP n,t [Ω × Σ k ].
However, by corollary VI.2, there is no protocol that emulates

V Σ k in MP n,t [Ω × Σ k ] if k ≥ 2 and t > n+k ′ -2 2 : a contradiction.
The relative hardness of k-set agreement and k-parallel consensus is also expressed by the following theorem. The theorem gives tight bounds on t for k-set agreement and kparallel consensus to be solvable when an eventual leader is available: , k-parallel consensus can be solved in MP n,t [Ω] as follows: Each process p i participates parallelly in k instances A 1 , . . . , A k of an (Ω × Σ)-based consensus protocol A. p i proposes its initial value in each instance; if p i decides v in instance A c , the pair (c, v) is returned by p i as its output for k-parallel consensus. Emulation of Σ in instance j consists in outputting the jth component of the vector provided by V Σ k .

Theorem VII.2. Let 1 ≤ k ≤ t < n. In MP n,t [Ω], 1
The liveness property of the class V Σ k ensures that for some c, 1 ≤ c ≤ k, the cth entry of the vector output by V Σ k eventually contains a subset of the correct processes. Moreover, for any entry j, every pair of sets in the jth entry of the vector provided by V Σ k have a non-empty intersection. Therefore, the cth entry of the output of V Σ k satisfy the same property as the output of a failure detector Σ. It thus follows that every correct process eventually decides in A c .

Since in every instance A j , 1 ≤ j ≤ k, the emulation of Σ preserves the intersection property, no two process decide different values in A j . This is because the safety property of consensus relies only on the fact that the intersection of any two sets output by Σ is non-empty. Hence, if (j, v) and (j, v ′ ) are decided, then v = v ′ , for any j, 1 ≤ j ≤ k.

VIII. CONCLUSION

The paper has investigated the relationship linking the k-set agreement and the k-parallel consensus problems in asynchronous crash-prone message-passing systems. While k-parallel consensus t-resiliently implements k ′ -set agreement for any value of t < n, and any k ′ ≤ k, the paper has shown that k-set agreement does not implement k ′ -parallel consensus for any k ′ , 1 ≤ k ′ ≤ n if n+k ′ -2 2 < t and 2 ≤ k. In addition, when an eventual leader Ω is available, it has established that k-parallel consensus can be solved if and only if t ≤ n+k-2

2

. This is to be compared with k-set agreement, which can be solved if and only if t < kn k+1 . The paper leaves open the following question: For n 2 ≤ t ≤ n+k-2

2

, what is the smallest value of k ′ for which kset agreement t-resiliently implements k ′ -parallel consensus in message passing? As a starting point, we demonstrate below that given a k-set agreement protocol and assuming t ≤ n+k-2 2 , (2k -1)-parallel consensus can be achieved. Note that this is not trivial: for example, if 2(2k + 1) < n, 2k -1 ≤ t for every t, n 2 ≤ t ≤ k+n-2

2

.

Partition the set of processes in two sets A = {p 1 , . . . , p k-1 } and B = {p k , . . . , p n }. Each p i in A broadcasts (i, v i ) where v i is p i 's initial value before deciding that pair. The nk + 1 remaining processes emulate a shared memory reduction of k-parallel consensus to k-set agreement, as described in [START_REF] Afek | The k-simultaneous consensus problem[END_REF], assuming that no more than t B = ⌊ n-k 2 ⌋ processes among them fail. If p i ∈ A obtains a decision (c, d), it broadcast the pair (c + (k -1), d) before deciding it. Any process that receives a pair (c, d) decides this pair. Note that we have 1 ≤ c ≤ 2k -1, and if pairs (c, d), (c, d ′ ) are decided, d = d ′ . If the number of actual failures in B exceeds t B , the emulation may not terminate, but safety is not violated (that is, a simulated write or read operation may not terminate).

For termination, let f A , f B be the actual number of failures in sets A and B respectively. If f A < k -1, the protocol terminates as A contains a correct process. Otherwise, f A = k -1 and consequently f B ≤ t-(k -1) ≤ n+k- 22

-(k -1) = n-k 2 .
That is, a majority of the processes in A are correct. The emulation of the shared memory protocol thus terminates, which enables every correct process to decide.

Another avenue for future research is to determine the weakest failure detector for k-parallel consensus. A candidate is the (new) failure detector class W k : the output of W k is a k-component array. Each component contains the same output as a failure detector Ω × Σ, except that the eventual leadership property of Ω and the liveness property of Σ are only required to hold in a single component. This component must be the same for both properties and for every process. See [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message Passing[END_REF] for more details.

  MP n,t [D] denote the same system equipped with a failure detector of the class D. Given two failure detectors D, D ′ with ranges R D and R D ′ respectively, D × D ′ denote the failure detector with range R D × R D ′ and histories D(F) × D ′ (F) for any failure pattern F.

2 .

 2 k, t be integers such that 1 ≤ t, k ≤ n. There exists a protocol that emulates a failure detector of the class V Σ k in MP n,t if and only if t ≤ n+k-2 Preliminaries: A coloring of a graph is a labelling of the graph's vertices with colors drawn from the integers {1, 2, 3, . . .}. A coloring is called a k-coloring if it uses at most k colors and proper if no two adjacent vertices share the same color. The chromatic number of a graph G, denoted χ(G), is the smallest number of colors needed to properly color G, i.e. the smallest value of k for which a proper kcoloring of G is possible.

  ) There is a k-set agreement protocol if and only if t < Bonnet and Raynal[START_REF] Bonnet | On the road to the weakest failure detector for k-set agreement in message-passing systems[END_REF] have shown that Σ k is necessary for k-set agreement. Moreover, Σ k can be emulated in MP n,t [Ω] if and only if t < kn k+1 . Hence, the existence of an Ω-based k-set agreement protocol toleratingt implies a t-resilient emulation of Σ k in MP n,t [Ω]. This is not possible if t ≥ kn k+1 . A k-set agreement protocol in MP n,t [Σ k × Ω] is presented in[START_REF] Bouzid | anti-omega x × σz-based kset agreement algoritms[END_REF]. Since Σ k can be emulated in MP n,t provided that t < kn k+1 , k-set agreement can be solved in MP n,t [Ω] for t < kn k+1 .2) Similarly, we have shown that V Σ k is necessary for k-parallel (Section IV) and that V Σ k can be emulated in MP n,t [Ω] if and only if t ≤ n+k-2

	kn k+1 ; 2) There is a k-parallel consensus protocol if and only if
	t ≤ n+k-2 2	.
	Proof: 1) 2	(Lemma V.4). There-
	fore, no protocol solves k-parallel consensus in MP n,t [Ω]
	if t > n+k-2 2 For t ≤ n+k-2 . 2

In this paper, k-parallel consensus problem is called k-simultaneous consensus. However, there is a body of work on simultaneous consensus, e.g.[START_REF] Coan | Simultaneity is harder than agreement[END_REF],[START_REF] Moses | Programming simultaneous actions using common knowledge[END_REF], in which simultaneity refers to when agreement is reached. We use the terminology k-parallel consensus to avoid confusion.

This work was supported in part by the DIGITEO project PACTOLE and by the ANR project DISPLEXITY.