Dan Alistarh

Seth Gilbert

Rachid Guerraoui

Corentin Travers

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

 in an algorithmic way.

Introduction

Set agreement was first introduced by Chaudhuri [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF] to capture the power of allowing more choices than consensus [START_REF] Lamport | The byzantine generals problem[END_REF], where only a single decision value is permitted. Each process p i begins with an initial value v i ; eventually, every process outputs one of the initial values as a decision. In k-set agreement, the set of all values output can be of size at most k. The power of set agreement depends on the parameter k. When k = 1, set agreement reduces to consensus. When k = n, the problem is trivial, i.e., processes can act entirely independently.

Impossibility Results and Lower Bounds. In a collection of seminal papers, Borowski and Gafni [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF], Herlihy and Shavit [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF], and Saks and Zaharoglou [START_REF] Saks | Wait-free k-set agreement is impossible: The topology of public knowledge[END_REF] showed that fault-tolerant asynchronous set agreement is impossible (while at the same time revealing a deep connection between distributed computing and algebraic topology). Chaudhuri et al. [START_REF] Chaudhuri | A tight lower bound for k-set agreement[END_REF] further developed these techniques, establishing a tight lower bound on the round complexity of synchronous set agreement: in a system with t failures, at least ⌊ t k ⌋ + 1 rounds are necessary. More recently, Gafni et al. [START_REF] Gafni | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement[END_REF] and Guerraoui et al. [START_REF] Guerraoui | A topological treatment of early-deciding set-agreement[END_REF] considered the feasibility of reaching an early decision: how fast can an algorithm tolerating up to t failures decide in an execution with at most f < t failures? They both show (in two different ways) that at least ⌊ f k ⌋ + 2 rounds are needed.

Partial Synchrony. Set agreement has been extensively studied in both synchronous and asynchronous systems. Real world distributed systems, however, are neither purely synchronous nor purely asynchronous. Instead, they tend to exhibit periods of synchrony when the network is well behaved, and periods of asynchrony when the network is poorly behaved. (For example, consider a TCP network [START_REF] Vinton | A protocol for packet network intercommunication[END_REF] under varying loads, which may affect the message delivery delays.) To describe such a system, Dwork et al. [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] introduced the idea of partial synchrony. They assume for every execution some (unknown) time GST (global stabilization time), after which the system is synchronous. In this paper, we study the feasibility and complexity of set agreement in the context of partially synchronous systems, determining the minimum-sized window of synchrony in which k-set agreement can be solved. Of course, the lower bounds for synchronous systems [START_REF] Chaudhuri | A tight lower bound for k-set agreement[END_REF][START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF] imply an immediate lower bound here of ⌊ t k ⌋ + 1 rounds. The question, then, is whether there exists any matching algorithm that terminates in a synchronous window of size ⌊ t k ⌋ + 1, or is there some inherent cost to tolerating asynchrony? Moreover, how does this cost depend on t and k?

We answer these questions by showing that at least ⌊ t k ⌋ + 2 synchronous rounds are required for k-set agreement, and then introducing an algorithm that terminates in any window of synchrony of size at least ⌊ t k ⌋ + 4 rounds. Together, these results show that there exists an inherent price to tolerating asynchronous executions, and that this price is constant in the context of the set agreement problem.

Lower Bound By Reduction. The technique for deriving the lower bound is an important contribution, as it provides new insights into the complexity of set agreement. Instead of relying on topology, as is typically required for set agreement lower bounds, we derive our result by reducing the feasibility of asynchronous set agreement to the problem of solving set agreement in a window of size ⌊ t k ⌋ + 1. Since asynchronous set agreement is known to be impossible, this reduction immediately implies that at least ⌊ t k ⌋ + 2 synchronous rounds are required for k-set agreement. Our main tool is a technique for simulating "locally synchronous" executions in an asynchronous system. In particular, we show how to perform a k-fault-tolerant simulation of a messagepassing system in an asynchronous shared memory system where each simulated execution appears synchronous to some processes.

This technique can be viewed as a generalization of the simulation technique of [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF], moving from synchronous systems to cover the spectrum of partially synchronous ones. There are two new key observations. First, when the simulation is run for an epoch of length ⌊ t k ⌋ + 1 rounds, we show that either some simulator sees a window of synchrony of size ⌊ t k ⌋ + 1 rounds, or some simulator fails. Second, we observe that these epochs of length ⌊ t k ⌋ + 1 can be repeated until either some process fails, or some process decides. From this we conclude that we have successfully simulated a set agreement protocol, resulting in the desired reduction.

Early Deciding Synchronous Set Agreement. Our technique turns out to be of more general interest as we can re-derive and extend existing lower bounds for synchronous early deciding set agreement.

It has been previously shown [START_REF] Gafni | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement[END_REF][START_REF] Guerraoui | A topological treatment of early-deciding set-agreement[END_REF], using sophisticated techniques, that even in an execution with f < t failures, some process cannot decide prior to round ⌊ f k ⌋ + 2. Strictly speaking, these two results differ in how failures are counted. In [START_REF] Guerraoui | A topological treatment of early-deciding set-agreement[END_REF], the lower bound is global: some process requires at least ⌊ f k ⌋ + 1 rounds. In [START_REF] Gafni | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement[END_REF], the lower bound is local: every process decides after round ⌊ f k ⌋ + 1. The latter bound applies in the case where the total number of processes n is unbounded and an unbounded number of failures can occur.

Using our simulation technique, we re-derive both lower bounds in a simpler and more general manner, in the standard model where t and n are bounded and known a priori. Of note, both lower bounds are corollaries of a single theorem that relates the number of processes which decide early with the worst-case round complexity of an algorithm. Basically, we show that if d processes decide by round ⌊ f k ⌋ + 1 in executions with at most f failures, then in the worst-case, some process takes at least time ⌊ t k ⌋ + E(•) + 1 to decide (where E is a function of t, k and d).

Upper Bound for Eventually Synchronous Agreement. We then present the first known algorithm for k-set agreement that tolerates periods of asynchrony. Our algorithm guarantees correctness, regardless of asynchrony, and terminates as soon as there is a window of synchrony of size ⌊ t k ⌋ + O [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. For simplicity, we show synchronous round complexity of ⌊ t k ⌋+4. Closing the gap between these bounds remains an intriguing challenge.

Two basic ideas underlie our algorithm. First, processes collectively execute an asynchrony detection sub-protocol that determines whether a round appears synchronous or asynchronous. A process can decide when it sees ⌊ t k ⌋ + O(1) synchronous rounds. Even so, different sets of processes may have different views of the system when the decision occurs, since there are only ⌊ t k ⌋ + O(1) rounds to exchange information. Second, each process maintains an estimate, i.e., a value that it is leaning toward choosing. In each round, each process adopts the minimum estimate that it receives. If a process is about to decide, however, it can elevate the priority of its estimate, causing other processes to adopt its value instead.

The key property of the algorithm is that there are at most k different high priority estimates in the system when a decision occurs. In a synchronous system, this would follow from the following fact: if there are k + 1 distinct estimates that remain at the end of a round, then there must have been at least k failures during that round. In a partially synchronous system, however, this is not true, as asynchronies can play the same role as failures in keeping extra values in the system. Instead, we rely on a careful analysis of the distributed asynchrony detection.

Implications. Several implications arise from our simulation technique and its usage. First, it provides additional evidence that the impossibility of fault-tolerant asynchronous k-set agreement is a central result in distributed computing, as it implies non-trivial results in both partially synchronous and synchronous models. Second, it highlights close connections between models that have differing levels of synchrony. In particular, our simulation technique takes advantage of structural similarities between eventually synchronous set agreement and early deciding set agreement to establish lower bounds in two different models of synchrony. The uncertainty regarding asynchrony (found in a partially synchronous execution) turns out to be fundamentally similar to the uncertainty regarding failures (found in an early deciding execution).

Model

In this section, we define three basic models of computation: the partially synchronous model of computation, the synchronous model of computation, and the asynchronous model of computation.

The partially synchronous model ES n,t consists of n deterministic processes Π = {p 1 , . . . , p n }, of which up to t < n may fail by crashing. (Note that the algorithm in Section 5 uses t < n/2.) The processes communicate via a message-passing network, modeled much as in [START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Keidar | Timeliness, failure-detectors, and consensus performance[END_REF]: time is divided into rounds. In each round, a process sends messages, receives messages, and performs some local computation. We assume that processes may fail by crashing. If a process p fails while sending messages in a round r, any subset of the messages that p sends in that round may be delivered to their recipients. A process that has not crashed by the end of round r is called non-failed at round r.

In this model, there is no assumption that every message broadcast in a round is also delivered in that round. Instead, we assume only that if all non-failed processes broadcast a message in round r, then each process receives at least n-t messages in that round. (This can be implemented by delaying a round r + 1 message until at least nt round r messages have been received.) We assume that the network is partially synchronous: there is some round GST after which every message sent by a non-failed process is delivered in the round in which it is sent. Similar roundbased models have been studied by Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF] (the heard-of model), by Keidar et al. [START_REF] Keidar | Timeliness, failure-detectors, and consensus performance[END_REF] (the GIRAF model), and by Schmid [START_REF] Schmid | How to model link failures: A perception-based fault model[END_REF] (the perception-based fault model).

The synchronous model S n,t is identical to ES n,t , except that we assume every process knows, a priori, that GST = 0, i.e., that every message is delivered in the round that it is sent.

The asynchronous model AS n,k consists of n processes Π = {p 1 , p 2 , . . . , p n }, up to k of which may crash. The processes communicate via single-writer, multi-readers (SWMR) registers. The memory is organized in arrays X[1 . . . n] of n registers; entry X[i] of an array can be written only by p i . We assume that registers are initialized with an special value ⊥. Also, for simplicity, we consider that each register is written at most once. (Note that our simulations have this property.)

In addition to read() and write() operations, a process can also invoke X.snapshot() to read all the contents of X in a logically instantaneous single operation. Let x and x ′ be the result of any two snapshot operations on X. We assume that the following hold: Containment: x ⊆ x ′ ∨ x ′ ⊆ x3 ; Self inclusion: Let v be the value written by p i in X[i] prior to invoking X.snapshot(), with no intervening X[i].write(•) operations by any process; let x be the result of the snapshot operation; then x[i] = v. An implementation of snapshot on top of SWMR registers can be found in [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Attiya | Atomic snapshots in o(n log n) operations[END_REF], and thus they provide no extra power. k-set agreement is impossible in AS n,k [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].

Adopt-commit objects. Our simulation relies on adopt-commit objects to coordinate which messages are delivered in each simulated round. An adopt-commit object AC , introduced in [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF][START_REF] Yang | Structured derivations of consensus algorithms for failure detectors[END_REF], supports one operation propose(v) that returns a decision (dec, v) where dec ∈ {adopt, commit}. The object satisfies the following properties: Termination: Each invocation by a correct process terminates. Validity: If a process decides (dec, v) then some process invoked AC .propose(v). Agreement: If a process decides (commit, v), then every decision is (•, v). Convergence: If every process proposes the same v, then (commit, v) is the only possible decision.

Note that these properties ensure that the only case when distinct values v are returned by processes is when every process returns (adopt, •). Wait-free implementations of adopt-commit objects in AS n,k can be found in [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF][START_REF] Yang | Structured derivations of consensus algorithms for failure detectors[END_REF]. These implementations also satisfy: Commit Validity:

Assume p j invokes AC .propose(v); then p j cannot get back (commit, v ′ ) with v = v ′ .
3 Simulating Synchronous Views: a Lower Bound for k-Set Agreement

In this section, we present an algorithm for simulating executions of the partially synchronous model ES n,t in the asynchronous system AS n,k . Assuming an indulgent algorithm for solving k-set agreement in a windows of synchrony of size at most ⌊ t k ⌋ + 1, we use the simulation to derive a k-set agreement algorithm in AS n,k 4 . This leads to a contradiction, as k-set agreement is impossible in AS n,k . model.

Preliminaries.

Let A be a protocol designed for the round based model ES n,t , and let α be an execution of A. We can assume without loss of generality that algorithm A directs each nonfailed process to send a message to all processes in each round 5 . A trace of the execution α is a sequence of vectors (REC 1 , REC 2 , . . .), with the property that vector REC r is associated with round r and describes the set of messages received by each process in that round. In particular, if process p i has not failed by the end of round r, REC r [i] is the set of processes from which process p i receives messages in round r. On the other hand, if process p i crashes during round r, then REC r [i] = ⊥. Also, since a failed (crashed) process does not recover, REC r [i] = ⊥ implies that REC r+1 [i] = ⊥, and p i / ∈ REC r+1 [j] for each process p j that has not failed by the end of round r. Moreover, any set REC r [j] = ⊥ is of size at least nt.

A round r is synchronous if every non-failed process receives a message from each non-failed process in round r. A window of synchrony of size ℓ is a sequence of ℓ consecutive synchronous rounds. Formally, rounds r 1 , . . . , r 1 +ℓ-1 form a window of synchrony if the following properties hold: [START_REF] Afek | Atomic snapshots of shared memory[END_REF]

∀r 1 ≤ r < r 1 +ℓ-1, ∀i, j such that REC r+1 [j] = ⊥ and REC r [i] = ⊥, REC r+1 [j] ⊆ REC r [i] and (2) ∀i, j such that REC r [j] = ⊥ and REC r [i] = ⊥, p j ∈ REC r [i].
We say that process p i has a synchronous view of rounds r ′ , r ′ + 1, . . . , r in α if the state of p i is the same at the end of round r and at the end of an execution α ′ that consists in r rounds and in which rounds r ′ , r ′ + 1, . . . , r are synchronous.

Overview. The simulation pseudocode is presented in Figure 1. The aim is to simulate an execution of algorithm A in model ES n,t in which some processes have synchronous views of a large number of rounds, namely at least ⌊ t k ⌋ + 1 consecutive rounds. The basic idea is similar to that of [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF]-we simulate each synchronous round by writing messages to shared memory, and we then run a weak agreement protocol to determine which messages to "deliver" to each simulated process. In order to maintain synchronous views, we might have to mute some processes. Intuitively, a muted process continues receiving messages but its messages are not received by other, non-muted processes. If the message of some process p j is not received by some process p i in round r (this implies in a synchronous execution that p j fails in round r), then allowing in round r + 1 the message of p j to be delivered to p i causes the view of p i to be no longer synchronous. As our goal is to maintain a synchronous view at least one process, it might thus be required to mute some processes. Muted processes may however receive arbitrary messages even from other muted processes. As long as no messages from muted processes are received by a non-muted process, the views of the latter processes remain synchronous.

As we will see, in each simulated round, the messages from at most k non-muted processes may be delivered to some but not all processes. Thus, the simulation mutes at most k new processes per round, where k is the number of simulators that may crash in AS n,k . Hence, by the end of the simulation of the first ⌊ t k ⌋ rounds, at most t simulated processes may have been muted. Therefore, in round ⌊ t k ⌋, a simulated process p i that has a synchronous view of the first ⌊ t k ⌋ rounds may receive as few as nt messages (but not fewer) from distinct processes. More precisely, at most k(⌊ t k ⌋ -1) processes are muted in the simulation of the first ⌊ t k ⌋ -1 rounds and in addition, at most k messages from non-muted processes might be not delivered to p i in round

⌊ t k ⌋ + 1.
We are able to extend this synchronous view by one more round, i.e., we show that in round ⌊t/k⌋ + 1, for at least one process p j that will have a synchronous view of size ⌊t/k⌋ + 1. Thus, assuming an algorithm where every process decides by the end of round GST + ⌊t/k⌋ + 1, we conclude that simulated process p j must decide. Each process is simulated by one simulator. If the simulator of p j does not fail, it then can write this decision in shared memory thereby enabling every other simulator to decide. Otherwise, the simulator of p j fails. In this case, we continue, repeating the simulation for another ⌊t/k⌋ + 1 rounds, again resulting in either a process deciding or the failure of its simulator. Eventually, after k + 1 repetitions (which we refer to as phases), we argue that some process decides and its associated simulator does not fail. This simulation implies a lower bound on the round complexity of k-set agreement in ES n,t . We assume, for the sake of contradiction, that there exists an algorithm A for ES n,t in which, for every execution, every correct process decides by the end of round GST + ⌊t/k⌋ + 1. We then show that our simulation of A solves k-set agreement in AS n,k , which is impossible [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]. procedure simulate( mi, r ) % Simulate round r where pi sends message mi.

19 reci ← ∅; VAL[r][i].write(mi) 20 repeat viewi ← VAL[r].snapshot() until |{j : viewi[j] = ⊥}| ≤ k 21 Mi ← {j : viewi[j] = ⊥} ; 22 for j = 1 to n do 23 if j ∈ Si ∪ Mi then statei[j] ← AC[r][j].propose(suspect) 24 else statei[j] ← AC[r][j].propose(alive) 25 if statei[j] = (commit, suspect ) then Si ← Si ∪ {j} 26 else if statei[j] = (adopt, suspect ) then Si ← Si ∪ {j}; reci ← reci ∪ { j, VAL[r][j] } 27 else reci ← reci ∪ { j, VAL[r][j] } 28 % Complete view of round r, if necessary: 29 if |reci| < n -t then reci ← { j, viewi[j] : viewi[j] = ⊥} ; sFlag i ← false 30 if i, mi / ∈ reci then reci ← reci ∪ { i, viewi[i] } ; sFlag i ← false

Basic Setup

The simulation depends on three parameters: the algorithm A being simulated, the number of phases numP , and an array R 1 , R 2 , . . . , R numP+1 where each R i is the first round in the i th phase with R 1 = 1. That is, each phase i consists in R i+1 -R i rounds.

For process p i , the algorithm A is described by a function compute(r, rec, sFlag) i , where r is a round number and rec a set of messages received by p i in round r. (The third parameter, sFlag, indicates whether the view of p i of the rounds of the phase is so far synchronous, and is used primarily in Section 4.) The compute function returns a pair (d i , m i ), where m i is the message to be sent in the next round, and d i is the decision value or ⊥, if no decision has been reached. Without loss of generality, we assume that each process sends the same message to all processes, including itself.

Simulating Synchronous Rounds

Each process in AS n,k simulates one process in ES n,t . We will refer to the processes in AS n,k as simulators. We denote sim i the simulator in AS n,k that simulates the process p i in ES n,t . The simulation begins with a call to propose(v i ) (line 6), where v i is sim i 's proposal (recall that the aim of the simulators is to solve k-set agreement in AS n,k .). The simulation is divided into phases (lines 9-15); each phase is divided into rounds. Simulation overview. The simulation at sim i begins with an invocation of propose(v i ) (line 6), where v i is sim i 's proposal and also the input to A of the simulated process p i . This launches two tasks T 1 and T 2, that run in parallel. In task T 1 (lines 7-15), sim i simulates steps of algorithm A in order to obtain a decision d i for p i . When a decision is reached, sim i writes it in DEC [i], decides, and exits (line 15). In task T 2 (lines [START_REF] Keidar | Timeliness, failure-detectors, and consensus performance[END_REF][START_REF] Lamport | The byzantine generals problem[END_REF][START_REF] Parvédy | Strongly terminating early-stopping set agreement in synchronous systems with general omission failures[END_REF], sim i periodically reads the shared array DEC . When it observes a non-⊥ value, the simulator decides that value and exits.

Round overview. In order to simulate round r (lines 12-15), simulator sim i invokes simulate(m i , r) (line 13), where m i is p i 's message for round r, which was computed previously. The simulate procedure returns a set of pairs j, m j , where m j is the message received from p j by p i in the simulated round r. The simulator then calls the compute function (line 14), which returns d i , a possible decision, and m i , the next message to send.

Failed, muted and suspected processes. A simulated process p i fails in the simulated execution whenever its dedicated simulator sim i fails. Let us fix a phase ρ. To simplify the discussion, the rounds of this phase are numbered 1, . . . , R. The goal is to simulate an execution in which in each phase a process has a synchronous view of the rounds of the phase.

To that end, each simulator maintains a set of suspected processes S i and a flag sFlag i . The set is emptied and the flag is set to true a the beginning of each phase (line 9). sFlag i = true at the end of round r indicates that process p i has a synchronous view of rounds 1, . . . , r. p j ∈ S i at the end of round r means that simulator sim i suspects that there exists some round r ′ ≤ r in which the message of p j was not delivered to every process. Suspicions might not be accurate but they are complete in the following sense: if the message of p j is not delivered to some non-failed process in round r ′ , then p j is suspected by every simulator by the end of round r ′ + 1. Process p j is muted at round r if it is suspected by every non-failed simulator at the end of round r. As within a phase no processes are ever removed from sets S i , a muted process never recovers from this state during a phase. Furthermore, we ensure that for every muted process p j at round r, no process p i with sFlag i = true delivers a message from p j in round r + 1, for every round r of phase ρ. This property is central to show the existence of a process with a synchronous view at the end of each phase.

Simulating a round. The simulate function (lines 19-32) carries out the send/receive step. For round r, simulator sim i writes the message m i into the register VAL[r][i] (line 20), and then performs repeated snapshots of VAL[r] (line 21) to discover the messages proposed by other simulators. Since k simulators may fail in AS n,k , the simulator cannot wait for all n simulators to write a value to the array VAL[r]. As soon as sim i discovers (nk) messages in its snapshot of VAL[r], it continues. The variable M i then stores the set of up to k processes from which some message is missed. Since the array VAL[r] is read by snapshot operations, the sets M i are ordered by containment. Moreover, the largest set is of size at most k.

The simulators then agree on which messages to deliver in round r using a sequence of n adopt-commit objects (lines 23-28). Simulator sim i records the set of messages p i receive in round r in the local variable rec i , which is empty at the beginning of the simulation of the round (line 20). If a simulator sim i misses a message from a process p j in round r (i.e., if p j ∈ M i ), or if simulator sim i suspects p j (i.e., if p j ∈ S i ), then it proposes suspecting p j to the jth adoptcommit object AC [r][j] of the sequence (line 24). Otherwise, the simulator proposes that p j is alive (line 25). Three decisions are possible.

1. (commit, suspect) (line 26): in this case, the simulator mutes process p j in round r. By agreement, we know that every simulator either adopts or commits to suspecting p j , and so every non-failed simulator sim ℓ adds p j to S ℓ . The round r message m j of p j (if any) is not received by p i . This is materialized by the fact that rec i remains unchanged. 2. (adopt, suspect) (line 27): in this case, we cannot determine whether p j is simulated as muted or not in round r, as the decision of other simulators may be (adopt, suspect), (commit, suspect), or (adopt, alive); even so, to be safe, simulator sim i adds p j to S i . We know, however, by validity, that some process proposed p j as alive, and so VAL[r][j] must contains the message from p j , which we add to the set rec i of messages to be received. 3. (•, alive) (line 28): as in the second case, we add the message from VAL[r][j] to rec i .

Notice that if any simulator commits to suspect p j , then by agreement every other simulator sim ℓ either adopts or commits to suspect p j and adds p j to S ℓ . Then, in the following round, every simulator proposes suspect p j (line 24) which implies by convergence that every simulator commits to suspect p j . It thus follows that the message from p j , if any, is ignored. By using the adopt-commit objects in this way, we ensure that once a process is simulated as muted, it stays in this state in each subsequent round.

The end of the phase. This approach results in not delivering messages from up to k new processes in each round (see Lemma 6). Eventually, the set of messages received by a process may fall below nt, the bound on the minimal number of messages received per round in ES n,t . In this case, not all simulated processes may maintain a synchronous view. We establish however the existence of a process that receives at least nt messages per round and has a synchronous view of size ⌊ t k ⌋ + 1 at the end of the phase (Lemma 4).

If simulator sim i discovers that the set of messages rec i is too small or does not contain the message of p i , the set rec i is augmented to ensure that it contains enough messages (|rec i | ≥ n-t, line 30) and that it contains the round r message of p i (line 31). This augmentation is always possible since the number of missing messages in the array VAL[r] is bounded by k ≤ t and hence p i observes at least nt round r messages. Since the view of p i is then no longer synchronous, the flag sFlag i is set to true.

Finally, we examine whether and when processes decide. Assume we are simulating an execution of a set agreement protocol that decides by round GST + ⌊t/k⌋ + 1, and assume that each phase is of size at least ⌊t/k⌋ + 1. Then, since at least one simulated process p i has a synchronous view of the entire phase, we conclude that p i decides by the end of the phase. Either the simulator of p i fails, or it writes the decision to the shared memory DEC [i]. In the latter case, every other simulator eventually observes the decision (lines 16-18) and terminates. Thus, if no decision is reached, then a simulator fails in each phase. Since there are only k possible failures in AS n,k , by the end of phase k + 1 every simulator reaches a decision, completing a successful simulation of a k-set agreement protocol for ES n,t in AS n,k .

Analysis of the Simulation

We now provide some basic lemmas showing that the simulation is correct. The main claims are Lemma 2, which shows that the simulated execution is a correct execution of ES n,t , and Lemma 4, which shows that in every phase, there is at least one process that has a synchronous view of the entire phase.

We say that a simulator participates in the simulation of round r if it reaches the r-th iteration of the inner loop of task T1 (line 13). When we refer to the value of the variable var i of some simulator sim i at some point in the execution, we implicitly assume that at this point sim i has not failed. We first argue that the simulation is non-blocking. The only blocking statement is the repeat on line 21; since there are at most k failures, it never delays a simulator forever: Lemma 1. If no simulator decides and writes its value to DEC prior to round r, then no simulator is blocked forever while simulating round r.

Proof. The only possibility for a simulator to be blocked while simulating a round is in the repeat statement of line 21. Fix r ′ ≤ r to be the smallest round such that an invocation of simulate(•, r ′ ) by a correct simulator p i never terminates. As no simulator has decided while simulating rounds 1, . . . , r ′ -1, and there are at most k failures possible in the system, at least nk simulators eventually start simulating round r ′ . Therefore, the number of non-⊥ entries in VAL[r ′ ] is eventually ≥ nk. Consequently, every participating simulator terminates the simulation of round r ′ .

⊓ ⊔

Next, we observe that the algorithm simulates an execution of A in ES n,t , meaning that there is an execution of ES n,t where each process sends and receives the same messages as in the simulation.

Lemma 2. For every r ≥ 1, there exists an execution α of ES n,t executing A where in every round r ′ ≤ r of α, every process p j ∈ Π receives exactly the messages returned by simulate(m i , r ′ ).

Proof. Let r ≥ 1 be the first round for which no such execution α exists. Let α be the r -1 round execution that satisfies the requirements of the lemma through round r -1, i.e., such that for every p j ∈ Π, for every round r ′ ≤ r -1, process p j receives exactly the set of messages returned by simulate(m j , r ′ ) in round r ′ of α. Fix some process p j that does not receive the messages returned by the call to simulate(m j , r) in round r of α. First, it is easy to observe that every message returned by the call to simulate(m j , r) was sent by some process in round r of α, as every such message was previously written in VAL[r], and hence was computed (line 14) at the end of round r -1. Second, notice that the set rec returned is of size at least nt: otherwise, additional messages are selected from view j to ensure that this is the case (line 30); moreover, it is clear that the simulate procedure only proceeds when |view i | ≥ nk. Thus we can extend the execution α with the delivery to p j of the messages returned by the call to simulate(m j , r). Execution α remains a valid execution of ES n,t , contradicting our hypothesis that no such execution existed.

For simulator p i , let REC r i denote the value of the variable rec i after p i has executed the adoptcommit protocol, and before the completion steps of line 30 and line 31. That is, REC r i is the value of rec i on line 29 of the instance simulate(m i , r). We say that p j ∈ REC i if j, ∈ rec i . Let S r i be the value of S i when sim i completes the simulation of round r. The set S[r] = simi∈Π S r i is the set of suspected processes at the end of the simulation of round r. We now show that, within a phase, each REC r i set could have been received in a synchronous execution. In particular, if a process p i does not receive a message in round r from some p ℓ (p ℓ / ∈ REC r i ), then p ℓ is simulated as muted in round r + 1 and no sets REC r ′ j with r ′ > r ever again contain a message from p ℓ . This follows from the agreement and convergence properties of adopt-commit objects. Lemma 3. For every round r in phase ρ (except for the last), for every p i , p j ∈ Π:

REC r+1 j ⊆ REC r i .
Proof. Fix p i , p ℓ and r such that for some round r, p ℓ / ∈ REC r i . Then we conclude that the state of p ℓ is (commit, suspect). Due to the agreement property of adopt-commit, for every participating simulator sim j , the state of p ℓ is (•, suspect), and so sim j adds p ℓ to S j . Thus, in round r + 1, every participating simulator proposes (suspect) for p ℓ . Due to the convergence property of adoptcommit, every simulator gets back (commit, suspect) for p ℓ , and hence no set REC r+1 j includes p ℓ .

We now show that some process has a synchronous view of size r + 1 for every round 0 < r < R ρ+1 -R ρ . In other words, there exists an execution α of the system ES n,t in which (1) some process p i receives exactly the same sets of messages in α as in the simulation and, (2) every round R ρ , . . . , R ρ + r in α is synchronous. Lemma 4. Let r be some arbitrary round in phase ρ. If there is some simulator sim i such that p i ∈ REC r i and |REC r i | ≥ nf , for some f ≤ t, then there is an execution α of ES n,t executing A such that (1) every round R ρ , . . . , r is synchronous in α, (2) process p i receives exactly the set of messages returned by simulate( , r ′ ) in each round r ′ of α and, (3) at most f processes fail in α.

Proof. By Lemma 2, there exists a (R ρ -1)-rounds execution β of system ES n,t in which each process receives exactly the set of messages returned by the successive invocations of simulate( , r ′′ ) in each round 1 ≤ r ′′ ≤ R ρ -1. Let γ be the suffix of β defined as follows. Without loss of generality, we assume that in β no process has failed by the end of round R ρ -1 6 . For every round r ′ in {R ρ , . . . , r -1}:

1. ∀p j ∈ Π, process p j fails in round r ′ if and only if p j has not failed prior to round r ′ and there exists a simulator sim ℓ that does not simulate the reception of the message from p j in round r ′ , i.e., p j / ∈ REC r ′ ℓ .

2. If p j has not failed by the end of round r ′ according to the previous item, each process p ℓ receives a message from p j in round r ′ if and only if we have at simulator sim ℓ (1)

p ℓ ∈ REC r ′ ℓ , (2) |REC r ′ ℓ | ≥ n -t and (3) p j ∈ REC r ′ ℓ .
In round r ′ = r, process p j ∈ Π fails if and only if p j / ∈ REC r i . In that case, no processes receive a message from p j in round r.

Let α = β • γ. Since for every round r ′ < r in phase ρ, REC r ′ +1 i ⊆ REC r ′ j , by Lemma 3, we know that every round in γ is synchronous. Also, by construction, at most f failures occur in execution α. Finally, by construction, process p i receives the same sets of messages in α and in the simulation.

Let M r i denote the set of simulator ids from which sim i misses messages at line 22 in the invocation of simulate(•, r). Let view r i denote the value of the variable view i at simulator sim i after the repeat loop (line 21). We next establish that for every round r, the sets M r i at different simulators are ordered by containment.

Lemma 5. Let i 1 ≤ . . . ≤ i x the ids of the simulators that invoke simulate(•, r) and execute line 22 in these instances. Denote X this set. There exists a bijection σ :

X → {1, . . . , |X|} such that M r i σ(1) ⊆ . . . ⊆ M r i σ(x) . Moreover, we have view r i σ(1) ⊇ . . . ⊇ view r i σ(x) .
Proof. The array VAL[r] is read by each simulator sim ij in snapshots. By the containment property of snapshot operations, the views view r ij obtained by each simulator at line 21 are ordered by containment. Let σ : X → {1, . . . , |X|} a bijection such that σ(i j ) ≤ σ(i ℓ ) if and only if view iσ(j) ⊇ view iσ(ℓ) , for every i j , i ℓ ∈ X. It then follows that

M r i σ(1) ⊆ . . . ⊆ M r i σ(x) since M r i = {1, . . . , n} \ {ℓ : view i [ℓ] = ⊥} 7 for every i ∈ X.
The second part of the lemma follows from the definition of σ.

The next lemma shows a bound on the increase in suspicions in each simulated round: Lemma 6. For every r in phase ρ (except for the last),

|S[r + 1]\S[r]| ≤ k.
Proof. During the simulation of round r + 1, new suspicions may only be introduced when some simulator sim i misses a round r + 1 message at line line 21 from a process that has not been suspected before. Observe also that for every simulator sim i , the set of missed messages has the property that |M r i | ≤ k. Moreover, the sets M r i at different simulators are ordered by containment (Lemma 5). Consequently, at most k new suspicions are introduced in the simulation of round r + 1, from which we conclude that |S

[r + 1]\S[r]| ≤ k.
Finally, we show that new suspicions do not necessarily imply that less messages are received by all processes. Even when there are x new processes suspected in a simulated round, there are some processes that deliver the messages from these suspected processes. This fact allows us to extend the simulation one round further than might be expected.

Lemma 7. Let r be a round in phase ρ such that |S[r -1]| ≤ f for some f ≤ t. Let ∆ = S[r]\S[r -1]. (1) At least n -|S[r]| simulators sim i are such that p i ∈ REC r i and |REC r i | ≥ n -|S[r]|; (2) For every x ≤ |∆|, there exist x simulators sim i ∈ ∆ such that p i ∈ REC r i and |REC r i | ≥ n -f -(x -1). Proof. Let j such that p j / ∈ S[r]
. By definition of S[r], no simulators decide (commit, suspect) of (adopt, suspect) for p j in round r. Hence, every simulator sim i adds p j to REC r i (line 28). This holds in particular for each simulator sim i such that i ∈ Π \ S[r] which proves [START_REF] Afek | Atomic snapshots of shared memory[END_REF].

For [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF], let C = Π\S[r -1] denote the set of processes that have not been suspected by the end of round r -1. Fix x ≤ |∆|. Consider the simulation of round r. We order the simulators in ∆ according to the size of their snapshot 8 of VAL[r] at the end of the repeat loop (line 21), breaking ties using the order of ids. Since snapshots are related by containment, a simulator with higher rank has a larger snapshot, missing fewer messages from other simulators. Notice also that due to the self-inclusion property of the snapshot operations, a simulator always finds its own round r message included in the snapshot.

Consider the last x simulators sim y1 , . . . , sim yx in the order defined above, and fix some simulator sim y ℓ for 1 ≤ ℓ ≤ x. It follows from Lemma 5 that (1) M yx ⊆ . . . ⊆ M y2 ⊆ M y1 and, (2) y ℓ / ∈ M y ℓ . Observe also that by definition of S[r], each simulator sees a value in VAL[r] for every process p i ∈ Π\S [r]. And the only ids in C that can be missed by sim y ℓ are the ids of the simulators that are ordered after it, i.e., C ∩ M y ℓ ⊆ {y ℓ+1 , . . . , y x }.

Consider the proposals made by the simulator sim y ℓ for the adopt-commit objects (line 23). Notice that sim y ℓ proposes suspect only for processes in S y ℓ ∪ M y ℓ . By definition of C, C ∩ (S y ℓ ∪ M y ℓ ) = C ∩ M y ℓ ⊆ {y ℓ+1 , . . . , y x }. Consequently, for each i ∈ C\{y ℓ+1 , . . . , y x }, sim y ℓ proposes (alive) to the adopt-commit object associated with p i . Therefore, it follows from the commit validity property of adopt-commit objects that sim y ℓ cannot decide (commit, suspect) for each process in the set C\{y ℓ+1 , . . . , y x }, from which we obtain that C\{y ℓ+1 , . . . ,

y x } ⊆ REC r y ℓ . Hence, |REC r y ℓ | ≥ |C| -(x -ℓ) = |Π| -|S[r -1]| ≥ n -f -(x -ℓ)
and p y ℓ ∈ REC r y ℓ , as desired.

Lower Bound on Set Agreement in ES n,t

We now show how to use the simulation technique to prove a lower bound on set agreement in ES n,t . We begin, for the sake of contradiction, by assuming that algorithm A solves k-set agreement in ES n,t in any window of synchrony of size ⌊t/k⌋ + 1. The simulation uses k + 1 phases, each of length ⌊t/k⌋ + 1, i.e., R ρ = (ρ -1)(⌊t/k⌋ + 1) + 1. We show that the resulting simulation of A solves k-set agreement in AS n,k , which is known to be impossible, implying that no such algorithm A exists. Therefore, any k-set agreement protocol requires at least ⌊t/k⌋ + 2 synchronous rounds to decide.

In Section 3.3, we showed that the simulation is consistent with an execution of ES n,t . The crux of the proof is to establish that at least one simulated process has a synchronous view of the rounds of each phase. Since each phase is of length ⌊t/k⌋ + 1, and since A guarantees a decision in a window of synchrony of size ⌊t/k⌋ + 1, either such a process decides by the end the phase, having seen the entire phase as synchronous, or its dedicated simulator fails.

Informally, Lemma 4 indicates that whenever REC r i is the set of messages delivered to p i in round r, p i has a synchronous view of the first r -R ρ + 1 rounds of the phase and sees f = n-|REC r i | failures. That is, at the end of round r, the simulated execution is indistinguishable for p i from an execution in which rounds R ρ , . . . , r are synchronous and no more than f failures occur. As at most t processes may fail in model ES n,t , we want to show to that there exists simulator sim i such that p i ∈ REC R i and |REC R i | ≥ nt, where R is the last round of the phase. By the code, the sets of messages received by the simulated process p i is then REC R i , and thus per Lemma 4 p i has a synchronous view of the entire phase. The desired property is derived from Lemma 6 and Lemma 7. From Lemma 6, we obtain an upper bound on the number of suspected processes at the end of round R -1, namely at most t, as well as an upper bound, k, on the number of newly suspected processes in round R. Recall that each suspected processes p j may not be included in sets REC R i . This, however, may not hold for every simulator: by part (2) of Lemma 7, we have that sim i , |REC R i | ≥ nt for at least one simulator. Moreover, for such a simulator, p i ∈ REC R i .

Lemma 8. For every phase ρ, if no simulators decide and write their decision to DEC prior to the end of phase ρ, then at least one simulator that begins phase ρ fails before beginning phase ρ + 1.

Proof. Assume for the sake of contradiction that no simulators that begin phase ρ fail prior to the end of phase ρ, and that no simulators decide by the end of phase ρ. Let R ρ , . . . , R D be the ⌊ t k ⌋ + 1 simulated rounds of phase ρ. First, we bound the number of suspected processes |S[R D -1]| at the end of round R D -1: at the beginning of the phase, S[R ρ ] = ∅ since every simulator empties S i at the beginning of the phase (line 11); per Lemma 6, each round introduces at most k new suspicions; hence, |S[R D -1]| ≤ k⌊t/k⌋ ≤ t. Consequently, the precondition of Lemma 7 is satisfied. 2), there must also exist a simulator sim ℓ such that |REC R D ℓ | ≥ nt and p ℓ ∈ REC R D ℓ . Finally, by Lemma 4, process p ℓ has observed a legal execution of algorithm A in system ES n,t in which rounds R ρ , . . . , R D appear synchronous to p ℓ . Therefore, since there are ⌊t/k⌋+1 rounds in phase ρ, and since algorithm A guarantees a decision in any window of synchrony of size ⌊t/k⌋ + 1, either process p ℓ outputs a decision at the end of round R D and its simulators writes it to DEC or the simulator of p ℓ fails, leading to a contradiction.

Let ∆ = S[R D ] \ S[R D -1]. If ∆ = ∅, there must exist a simulator sim ℓ such that p ℓ ∈ REC R D ℓ and |REC R D ℓ | ≥ n -|S[R D ]| ≥ n -t per property (1) of Lemma 7. If ∆ = ∅, per Lemma 7(
We conclude that our simulation of algorithm A solves k-set agreement in AS n,k . Agreement follows from the fact that our simulation is a valid simulation of A in ES n,t (Lemma 2), and termination follows from Lemma 8, which shows that if there is no decision, then at least one simulator fails in every phase; since there are only k failures in AS n,k , by the end of phase k + 1, some simulator must decide.

Lemma 9. The algorithm in Figure 1 simulating A solves k-set agreement in AS n,k .

Proof. Termination: Eventually, every correct simulator decides: Assume for the sake of contradiction that some correct simulator never decides, which implies that no simulator ever writes out a decision to DEC . By Lemma 8, we know that in each phase ρ, some simulator must fail. Moreover, by Lemma 1, simulators continue to complete each phase. Thus, k + 1 simulators fail by the end of phase k + 1, contradicting the fact that most k simulators can fail.

Agreement: |{v | ∃i : DEC[i] = v ∧ v = ⊥}| ≤ k, Validity: ∀i : DEC[i] = ⊥ ⇒ DEC[i] = v,
where v is the initial value of some process: From Lemma 2, we know that the sets of messages produced at each round by the simulation are the sets of messages received by the processes in some execution of A in system ES n,t . Thus, agreement and validity follows immediately from the same properties of A.

Since k-set agreement is impossible in AS n,k , we conclude: Theorem 1. There is no algorithm A for ES n,t that decides by round GST + ⌊t/k⌋ + 1, i.e., within a window of synchrony of size ⌊t/k⌋ + 1.

The complexity of early deciding synchronous set agreement

We now show that the simulation presented in Section 3 can be used to derive lower bounds on the round complexity of early deciding synchronous k-set agreement. We say that a k-set agreement algorithm A is early deciding if processes that see at most f < t failures decide by the end of some early round R + 1 < ⌊t/k⌋ + 1. We make this more precise as follows.

Definition 1. Let d and R be positive integers, and let A be a k-set agreement algorithm in the S n,t model. We say that A is in ED(R, d) if in every run of A, for every f such that ⌊ f k ⌋ ≤ R, among the x processes that see at most f failures, at least min(x, d) of them decide by the end of round R + 1.

The main result of this section shows that every k-set agreement algorithm in ED(R, d) pays a penalty for deciding early in terms of its worst-case running time.

Main Result and Corollaries

The following theorem demonstrates an inescapable tradeoff between the number d of processes that can decide early, the early decision round R + 1, and the worst-case decision round R D = ⌊t/k⌋ + 1 + E for deciding under any circumstances.

Theorem 2. Let k, t, R be integers such that 1 < k ≤ t < n and 0 ≤ R < ⌊t/k⌋ -1. Then, for any d > 0, the following hold:

1. If d ≥ k,
, d) = ⌊ d(⌊t/k⌋-R-2)+(t mod k) k-d ⌋.
We know that every k-set agreement algorithm tolerating t failures requires ⌊t/k⌋ + 1 rounds to decide in the worst-case [START_REF] Chaudhuri | A tight lower bound for k-set agreement[END_REF][START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF]. This theorem shows that achieving property ED(R, d) implies sub-optimal worst case time complexity. We say that E is the price of deciding very early. Before discussing the proof, we state two corollaries. The first shows a (global) lower bound on the number of rounds for every process to decide early. It follows from Theorem 2 where d = n: Corollary 1. Let k, t, R be integers such that 0 < k ≤ t < n and R ≤ ⌊t/k⌋ -1. Every k-set agreement algorithm in S n,t has a run with f failures, for some f such that ⌊f /k⌋ ≤ R, in which some process decides after round R + 1.

Proof. For the sake of contradiction, let B be a k-set agreement algorithm such that for every f, f ≤ ⌊ f k ⌋ ≤ R, in every run with f failures, every process decides by the end of round R + 1. Notice that in every run of B, each process (that observes f failures with ⌊ f k ⌋ ≤ R) must decide by the end of round R + 1. Thus B is in ED(R, d) for d ≥ k, which implies that B does not exist. This bound is tight; matching algorithms can be found in [START_REF] Gafni | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement[END_REF][START_REF] Parvédy | Strongly terminating early-stopping set agreement in synchronous systems with general omission failures[END_REF]. Herlihy et al. prove the same result in [START_REF] Guerraoui | A topological treatment of early-deciding set-agreement[END_REF] 9 . However, their proof is based on combinatorial algebraic topology, whereas we rely on algorithmic reduction.

The second corollary states a (local) lower bound on the number of rounds needed for even one process to decide early, and relies on Theorem 2 where d = 1: Corollary 2. Let k, t, R be integers such that 1 < k ≤ t < n, and R < ⌊ t k ⌋k. Every k-set agreement algorithm in S n,t with worst-case round complexity ⌊t/k⌋+1 has a run with f failures, for f such that ⌊f /k⌋ ≤ R, in which no process decides by the end of round R + 1.

Proof. Suppose for contradiction that there exists an algorithm B with worst-case round complexity ⌊t/k⌋ + 1 such that in any run with f failures, at least one process decides by the end of round R + 1. Then B is in ED(R, 1). Note that for R ≤ ⌊ t k ⌋ -2k and

d = 1, E(d, t, k, R) = ⌊ d(⌊ t k ⌋-R-2)+(t mod k) k-d ⌋ ≥ 1.
Therefore, the worst-case complexity of any algorithm in ED(R, 1) is at least ⌊t/k⌋ + 2 by Theorem 2 : a contradiction.

A complementary local early deciding lower bound is derived in [START_REF] Gafni | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement[END_REF], for systems with an unbounded number of processes, in which an unbounded number of failures can occur. The two results are incomparable, since the models considered are distinct. By contrast, our theorem holds in the standard model in which the number of processes n and the number of failures t are both bounded and known.

Thus Theorem 2 not only allows us to derive previous lower bounds on local and global early decision, but also unifies those results by considering the more general question of the worst-case round complexity, given d processes that decide early.

Overview of the Analysis

Fix parameters t, k, R and d, E matching the conditions of Theorem 2. In this section, we focus on the (interesting) case where d ≤ k + 1 and E ≥ 0. For contradiction, assume that there exists an early deciding k-set agreement algorithm A in ED(R, d) such that d ≥ k or that has worst case round complexity R D < ⌊ t k ⌋ + 1 + E. We show that this implies the existence of a k-set agreement algorithm in AS n,k by simulating A using the algorithm described in Figure 1 with only one phase of length R D = ⌊t/k⌋ + 1 + E.

Assume, without loss of generality, that the compute(•, •, sFlag) procedure for algorithm A always returns (⊥, ⊤) if sFlag = false (The simulation never delivers ⊤ as a message since a process "sending" ⊤ is muted-see Lemma 10.).

The crux of the proof lies in identifying simulated processes that observe a synchronous execution with (1) no more than f failures, where ⌊f /k⌋ ≤ R, by the end of round R + 1 or (2) no more than t failures by the end of round R D < ⌊t/k⌋ + 1 + E. Such a process decides because A is the class ED(R, d) and R D is the worst-case round complexity of the algorithm A. If there are at least k + 1 such processes, the dedicated simulator of at least one them is correct. This simulator can write the decision in shared memory, enabling other simulators to decide.

By a careful analysis of the sets of messages delivered to the processes in the first R + 1 rounds of the simulation, we identify a non-empty set D of processes that either see less than f failures at the end of round R + 1, or whose simulator fails while simulating the first R + 1 rounds (Lemma 11).

A simulator that simulates a decision writes this decision to shared memory, allowing this value to be decided by other simulators (line 15). If this does not occur, the simulation of rounds r > R + 1 proceeds with at most k -|D| failures remaining among the simulators. Thus we can simulate "more" rounds (Lemma 12). We are then able to identify a set of k + 1 -|D| processes that see at most t failures at the end of R D rounds, from which we conclude that at least one correct simulator obtains a decision (Lemma 13 and Lemma 14). Finally, as there exists a single run of S n,t executing A in which each process receives the same set of messages (Lemma 15), we conclude that at most k proposed values are decided.

Proof of Theorem 2

We proceed by contradiction. We assume the existence of an algorithm A in ED(R, d) that solves k-set agreement in S n,t such that d ≥ k or with worst-case round complexity R D < ⌊ t k ⌋ + E + 1. Notice if E < 0, A trivially does not exist since every k-set agreement has a run in which at least one correct process has not decided by the end of round ⌊t/k⌋ [START_REF] Chaudhuri | A tight lower bound for k-set agreement[END_REF][START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF]. So, in the following we suppose that E(d, t, k, R) ≥ 0. Moreover, we consider without loss of generality that

1 ≤ d ≤ k + 1, as each algorithm in ED(R, d) is also in ED(R, d ′ ) for every d ′ < d.
Notation. We first fix some notation.

-Let F [r] denote the set of processes p i whose dedicated simulator sim i has failed before starting the simulation of round r + 1. -Let D[r] denote the set of processes p i whose dedicated simulator has decided before starting the simulation of round r + 1. -As in Section 3.3, S[r] = pi∈{p1,...,pn} S r i is the set of the suspected processes at the end of the simulation of round r. Similarly, REC r i is the value of the variable rec i at simulator sim i at line 29 of the instance simulate(m i , r) (and before the completion steps of line 30 and line 31).

-Let G[r] = {p i : p i ∈ REC r i ∧ |REC r i | ≥ n -t}. G[r]
is the set of processes p i that have sF lag i = true at the end of round r. For each process p i ∈ G[r], p i receives in round r of the simulated execution a message from each process p j ∈ REC r i . None of the processes in G[r] have been muted by the end of round r.

-R D is the worst-case decision round for algorithm A.

Notice that Lemma 1, Lemma 3, Lemma 4, Lemma 5 , Lemma 6 and Lemma 7 refer to only one phase of the simulation. Therefore, they still hold in the context of this proof. First, we use Lemma 3 to obtain that if a process is not in G[r] for round r, then none of the processes in G[r + 1] will "receive" its messages in the simulation of round r + 1. In other words, G[r] is the set of alive processes at the end of round r in the simulated execution.

Lemma 10. For every round r ∈ {1, . . . , R D -1} and process

p ℓ ∈ Π, if p ℓ / ∈ G[r], for all processes p i ∈ G[r + 1], p ℓ / ∈ REC r+1 i . Proof. Assume that p ℓ / ∈ G[r]. By definition of G[r], p ℓ / ∈ REC r ℓ ∨ |REC r ℓ | < n -t. Consider a process p i ∈ G[r + 1]. By Lemma 3, REC r+1 i ⊆ REC r ℓ . |REC r+1 i | ≥ n -t since p i ∈ G[r + 1]. Therefore, |REC r ℓ | ≥ n -t and thus p ℓ / ∈ REC r+1 i .
The following lemma is central to the proof. It states that at least min(k, d) simulators decide or fail before they start simulating round R + 2.

As algorithm A is in the class ED(R, d), a process that has a synchronous view of the first R + 1 rounds in which no more than f m = kR + k -1 failures occur might decide. We notice that (1) "late" simulators, namely simulators associated with processes that are newly suspected in round R+1, see at most f m failures (Lemma 7(2) and Lemma 6 which gives an upper bound on |S[R]|). Moreover, if at most kR+k-1 suspicions are generated, i.e., (2) |S[R+1]| ≤ kR+k-1, each non suspected process observes at most f m failures at the end of round R + 1 (Lemma 7(1)). By combining (1) and ( 2), we are able to identify at least min(k, d) simulators that either decide or fail, which proves the lemma.

Lemma 11. |D[R + 1] ∪ F [R + 1]| ≥ min(k, d). Proof. Let f m = kR + (k -1). Let p i be a process such that p i ∈ REC R+1 i and |REC R+1 i | ≥ n -f m , i.e.
simulator sim i simulates the reception of at least nf m messages including a message from p i in round R + 1. We know by Lemma 4 that there is a an (R + 1)-rounds execution α of system S n,t with f ≤ f m failures in which, for every round r, p i receives exactly messages rec r i . Therefore, p i may decide by the end of round R + 1 as algorithm A is in the class ED(R, d). Let CD be the set of processes that may decide in this way by the end of round R + 1.

Next, let ∆ = S[R + 1] \ S[R] be the set of processes that are newly suspected during the simulation of round R + 1. Let p j be a process in ∆. It follows from Lemma 7 that p j ∈ REC R+1

| ≥ n-((k + 1)R -1) = n -f m .
Hence, for every process in ∆, the simulated execution is indistinguishable from a (R+1)-rounds synchronous execution in which at most f m failures occur. Thus, ∆ ⊆ CD.

Consider now some process We now analyze suspicions generated in the simulations of the rounds r ≥ R + 3.

p j ∈ Π \ S[R + 1]. By Lemma 7(1), p j ∈ REC R+1 j and |REC R+1 j | ≥ n-|S[R+1]| = n-(|S[R]|+|∆|). If |∆| ≤ k -1, then |REC R+1 j | ≥ n-(kR+k - 1) = n-f m and thus Π \S[R +1] ⊆ CD. Therefore, ∆∪(Π \S[R +1]) ⊆ CD, from which we obtain that |CD| ≥ |∆ ∪ (Π \ S[R + 1])| = |Π \ S[R]| ≥ n -kR ≥ n -k(⌊ t k ⌋ -1) ≥ k + 1 ≥ d, as n -t ≥ 1.
Lemma 12. For every r ≥ R + 3, |S[r] \ S[r -1]| ≤ k -min(k, d).
Proof. Let us first observe that a simulator sim i that has decided or failed before starting to simulate round r does not participate in the simulation of round r. More precisely, for every r ′ ≥ r, sim i never writes in VAL[r ′ ][i] and consequently i in is the set M r ′ j for each simulator sim j that participates in round r ′ . So, in round r ′ , every simulator proposes (suspect) for p i , and, by the convergence property of adopt-commit objects, every simulator decides (commit, suspect)

for p i . Hence p i ∈ S[r ′ ]. In particular, this means that for r ≥ R + 2, D[R + 1] ∪ F [R + 1] ⊆ S[r] (P1). Let r ≥ R + 3 and p ℓ ∈ S[r] \ S[r -1]
. This can occur only if a simulator sim j misses the round r message of p ℓ , i.e., ℓ ∈ M r j . Per Lemma 5, we know that sets M r j are ordered by containment. Let M be the largest set. It thus follows that S[r] \ S[r -1] ⊆ M . Notice also that by the code (line 21) |M | ≤ k.

As noted earlier, for each simulator sim i that does not participate in round r, we have i / ∈ M r j where sim j is any participating simulator. In particular, this implies that

D[R + 1] ∪ F [R + 1] ⊆ M . Finally, note that (D[R + 1] ∪ F [R + 1]) ∩ (S[r] \ S[r -1]) = ∅ since D[R + 1] ∪ F [R + 1] ⊆ S[r -1] by property P1. Therefore, |S[r] \ S[r -1]| ≤ |M | -|D[R + 1] ∪ F [R + 1]| = k -|D[R + 1] ∪ F [R + 1]| ≤ k -min(k, d).
The last inequality follows from Lemma 11.

Next, we establish an upper bound of t on the number of suspected processes at the end of round R D . If in round r the message from some process p j is not delivered to some other process by the end of round r, p j must be suspected, i.e., p j ∈ S[r]. This upper bound is then used to prove that in last round, some simulated processes receive at least nt messages.

Lemma 13. |S[R D ]| ≤ t.
Proof. It follows from the fact that S[0] = ∅ and from Lemma 6 that S[R+2] ≤ (R+2)k. For the remaining round r = R+3, . . . , R D , we know by Lemma 12

that |S[r]\S[r-1]| ≤ k-min(k, d). Hence, |S[R D ]| ≤ k(R + 2) + (R D -(R + 3) + 1)(k -min(k, d))
We consider two cases, according to the value min(k, d).

-

If k ≤ d, we have |S[R D ]| ≤ k(R + 2). Since R + 2 ≤ ⌊ t k ⌋, |S[R D ]| ≤ t. -k > d.
In this case, we have

|S[R D ]| ≤ k(R + 2) + (R D -(R + 3) + 1)(k -d) ≤ k(R + 2) -k(R + 2) + d(R + 2) + R D (k -d) ≤ d(R + 2) + (⌊ t k ⌋ + E)(k -d) ≤ t + E(k -d) -(t mod k) -d(⌊ t k ⌋ -(R + 2)) By definition of E, E(k -d) -(d(⌊ t k ⌋ -(R + 2)) + (t mod k)) ≤ 0, from which we obtain |S[R D ]| ≤ t.
We can now state the main termination Lemma. It follows from Lemma 11 and from the analysis of the number of suspicions generated during the simulation of rounds R + 3, . . . , R D ( Lemma 12).

Lemma 14. (Termination) Every correct simulator decides.

Proof. Let us assume for the sake of contradiction that some correct simulator never decides. As every correct simulator eventually decides if one simulator writes a decision value in the shared array DEC (Task T2), it follows that no simulator ever writes a decision value in DEC . Consequently, for all rounds r, we have that D[r] = ∅. It follows from Lemma 1 that every correct simulator completes the simulation of rounds 1, . . . , R D , for a total number of at most ⌊ t k ⌋ + E simulated rounds. We know by Lemma 11 that at least min(d, k) simulators must have failed during the simulation of the first R + 1 rounds. If each of these simulators fails before deciding, we show that one process has a synchronous view of the R D rounds in which at most t failures occur. Moreover, the dedicated simulator of this process is correct. Hence, this simulator must decide : a contradiction.

Consider the last round [START_REF] Gafni | The Extended BG simulation and the characterization of t-resiliency[END_REF]. So, by Lemma 4, each process p i ∈ A has a synchronous view of rounds 1, . . . , R D in which at most t failures occur. Therefore, as in every execution of A, every non-faulty process has decided by the end of round of R D , each p i ∈ X must decide in round R D . It remains to show that the dedicated simulator of at least one of the processes in X is correct.

R D . Let ∆ = S[R D ] \ S[R D -1] and X = ∆ ∪ (Π \ S[R D ]). For every p i ∈ X, it follows from Lemma 7 that p i ∈ REC R D i and |REC R D i | ≥ n -|S[R D ]|. Notice that |S[R D ]| ≤ t (Lemma
Note that

S[R D ] = S[R D -1] ∪ ∆. As |∆| ≤ k -min(k, d) (Lemma 12), it follows that |S[R D ]| ≤ t, we have |S[R D -1]| ≤ t -(k -min(k, d)). Hence, |X| = |(Π \ S[R D ]) ∪ ∆| ≤ n -t + (k -min(k, d)) ≤ 1 + (k -min(k, d), since t < n.
We then notice that by Lemma 11 and the assumption that no simulator decides, |F [R + 1]| ≥ min(k, d). Therefore, as no more than k simulators may fail, there exists p i ∈ X such that sim i is a correct simulator.

The next lemma establishes that the simulated execution is a valid execution of model S n,t executing A.

Lemma 15. Let r such that G[r] = ∅ and |S[r]| ≤ t.

There is an execution α of system S n,t executing algorithm A such that ∀r ′ ≤ r, ∀p i ∈ G[r ′ ], process p i receives exactly the set of messages returned by simulate( , r ′ ) in round r ′ of α.

Proof. Let α be the r-rounds execution defined as follows. ∀r ′ ∈ {1, . . . , r -1} :

1. ∀p i ∈ {p 1 , . . . , p n }, process p i fails in round r ′ if and only p i has not failed prior to round r ′ and p i / ∈ pj ∈G[r ′ ] rec r ′ j . 2. ∀p i ∈ G[r ′ ], process p i receives a message from each process p j ∈ rec r ′ i during round r ′ . ∀p i / ∈ G[r ′ ], process p i receives a message from each process in pj ∈G[r ′ ] rec r ′ j .

We first verify that α is a valid synchronous execution. Let r ′ ∈ {1, . . . , r}. If process p i has not failed by the end of round r ′ , it follows from the definition of α that every process receives a message from p i in round r ′ . Suppose now that some process does not receive process p i 's message in round r ′ . Hence, p i / ∈ pj ∈G[r ′ ] rec r ′ j , and there exists a process p ℓ ∈ G[r ′ ] such that p i / ∈ rec r ′ ℓ . It then follows from Lemma 3 that every p j is such that p i / ∈ rec r ′ +1 j . In particular, no processes in G[r ′ +1] receive p i 's message during round r ′ +1, and no processes in

Π -G[r ′ +1] receive p i 's message since p i / ∈ pj ∈G[r ′ ] rec r ′ j .
Second, we count the number of failures in α. Clearly, process p i fails if and only if

p i / ∈ pj ∈G[r ′ ] rec r ′ j for some r ′ ≤ r. As per Lemma 10, G[r ′ + 1] ⊆ G[r ′ ], Π -pj ∈G[r] rec r j
is the set of faulty processes in α. Thus, p i fails implies that p i / ∈ rec r j for some processes p j in G[r]. Hence, by definition of S[r], p i ∈ S[r]. Therefore, at most t processes fail in execution α, since we assume that

|S[r]| ≤ t.
Finally, by definition of

G[r ′ ], ∀p i ∈ G[r ′ ], simulate( , r ′ ) returns rec r ′ i . A process p i / ∈ G[r ′
] may receive in round r ′ different sets of messages in the simulation and in round α. However, by Lemma 10, no processes p j in G[r ′′ ], ∀r ′′ ≥ r ′ are such that p i ∈ rec r ′′ j . Therefore, it then follows from the definition of α that every process in G[r ′ ] receives the same sets of messages in the simulation of round r ′ and in the r ′ th round of execution α.

Together with Lemma 14, the following Lemma establishes that the simulator solve k-set agreement in model AS n,k by simulating an execution of A in model S n,t .

Lemma 16. (Agreement) |{v | ∃i : DEC[i] = v ∧ v = ⊥}| ≤ k. (Validity) ∀i : DEC[i] = ⊥ ⇒ DEC[i] = v
where v is the initial value of some process.

Proof. Every decision value v written in the array DEC is computed during the simulation of some round r ≤ R D and v is the decision of some process p i in the simulated execution. When simulator sim i decides at round r, the simulated process p i has not failed in the simulated run, i.e, p i ∈ G[r].

Let r ′ ≤ R D the last round in the simulated execution in which a decision occurs. S[r ′ ] ⊆ S[RW C] and thus |S[R D ]| ≤ t by Lemma 13. Therefore, it follows from Lemma 15 that there exists a r ′ -rounds execution α of system S n,t executing A such that, for every r, 1 ≤ r ≤ r ′ and every p i ∈ G[r], simulate( , r) returns the set of messages received by p i in round r of α.

The values written out in DEC are a subset of the values decided in α. The correctness of A thus implies that decision values written in DEC satisfy validity and agreement.

A k-Set Agreement Algorithm for ES n,t

In this section, we present an algorithm named K4 which solves k-set agreement in a window of synchrony of size ⌊t/k⌋ + 4. This is the first algorithm, to the best of our knowledge, for kset agreement in ES n,t . The pseudocode can be found in Figure 2. The complete proof of the protocol is deferred to the Appendix.

Description

K4 is a round-based full-information protocol, and it assumes that t, the number of failures, is less than n/2. Each process maintains a local estimate est i , representing its preferred decision, and sets Active i and Failed i , which denote the processes that p i believes to be alive and failed, respectively. In every round, each process broadcasts its entire state (line 5), and receives all the messages for the current round (line 6), updating its view of which processes have failed and which rounds are synchronous (lines 7-10). A process decides if it receives a message from another process that has already decided (lines 11-13), or if it sees ⌊t/k⌋+4 consecutive synchronous rounds (line 15). If no decision is reached, then the estimate est i is updated in lines 17-20. There are two key components to K4: accurately determining whether rounds are synchronous (which is critical for ensuring liveness), and updating the estimate (which is critical for ensuring agreement).

Detecting Asynchrony. updateSynchDetector() merges information into the Active and Failed sets; if a process believes that p ℓ was active in round r (e.g., it receives a message from p ℓ ) , then p ℓ is added to Active[r]; if it believes that p ℓ was failed during round r (e.g., it did not receive a message from p ℓ ), then p ℓ is added to Failed [r] (see lines 23-26). It then determines based on Active[r] and Failed [r] sets whether round r seems synchronous (lines 27-30). A round r is deemed asynchronous if some process p ℓ is believed to have failed in round r (i.e., p ℓ ∈ Failed [r]), and yet is also believed to be alive at some later round k > r (i.e., p ℓ ∈ Active[k]). Finally, process p i sets a flag sF lag to true if it sees the previous ⌊t/k⌋+3 rounds as synchronous (line 34). Note that the sets Active i [r] and F ailed i [r] need not be disjoint: this can occur in rounds where process p receives a message from a process q, but another process does not receive the message from q, either because of q's failure or because of asynchrony.

Updating the estimate. Each process updates the estimate in every round. Estimates have two levels of priority: if a process has seen ⌊t/k⌋ + 3 synchronous rounds, i.e., if it is "ready to decide," then its estimate is awarded high priority; all other estimates are awarded normal priority. Process p i stores prioritized estimates in flagProcs i (line 17), and adopts the minimum prioritized estimate, if one exists (line 19). Otherwise, process p i adopts the minimum estimate received in the current round (line 20).

Analysis

We prove that the algorithm K4 solves k-set agreement in ES n,t . Validity and Termination are straightforward, so we focus on showing Agreement. The proof of agreement is based on the idea that in order for processes to maintain at least k + 1 distinct estimates, at least k failures have to occur in each round. This is obvious if the system is synchronous-and yet quite nontrivial when the system may be asynchronous for certain periods. We identify a trade-off between the number of processes that have a synchronous view of an execution suffix, and the number of distinct estimates that these processes can carry. In particular, we prove that processes which have a synchronous view of ⌊t/k⌋+3 consecutive rounds may hold at most k distinct estimates, which, after some consideration, implies that there is no execution of the algorithm in which processes decide on more than k values. The key lemma, whose proof is presented in full in Section 5.3, is the following.

Lemma 17 (Elimination). Let r m > 0 be a round and p 1 , p 2 , . . . , p k+1 be k + 1 processes that, at the end of round r m , perceive the previous ⌊t/k⌋ + 3 rounds as synchronous. Then at least two such processes have the same estimate.

Assuming that Lemma 17 holds, we can prove that the K4 algorithm preserves agreement.

Theorem 3 (Agreement). In every execution, processes decide on a set of at most k distinct values.

Proof. Consider an arbitrary execution of K4 and let r d be the first round in which a process decides. Let p d be a process that decides in round r d and let Supp d be the set of processes with sF lag = true at the beginning of round r d -we say that processes in Supp d support decision in round r d .

First, notice that, since process p d is the first process to decide, it must necessarily set the decided i variable to true on line 15 of the propose procedure. This implies that sCount i = ⌊t/k⌋ + 4. Therefore, each of the processes whose message p d receives in round r d must have perceived the previous ⌊t/k⌋ + 3 as synchronous at the end of round r d -1 (otherwise, p d also notices an asynchrony at line 30 of updateSynchDetector and cannot decide). Hence, each such procedure propose(vi)i On the other hand, Lemma 17 ensures that processes in Supp d have at most k distinct estimates at the beginning of round r d . Denote the set of these values by V k . We prove that decisions in round r d or in later rounds are necessarily made on a value in V k .

1 esti ← vi; ri ← 1; msgSeti ← ∅; sF lagi ← false 2 Activei ← [ ]; Failed i ← [ ]; AsynchRoundi ← [ ]
First, if a process decides at the end of round r d , then it maintains its previous estimate. The deciding process supported decision at the end of the previous round, therefore its estimate is in V k . Second, if the process does not decide at the end of r d , then, since |Supp d | ≥ nt > ⌊n/2⌋, the process necessarily receives a message from a process in Supp d in round r d . In this case, the process updates its estimate in line 19 of procedure propose(), thereby adopting the minimum estimate that it receives from a process in Supp d , which is in V k . This implies that any decisions made in later rounds also occur on elements of V k .

Since |V k | ≤ k, we conclude that all decisions in this execution occur on at most k distinct values, which is equivalent to k-agreement.

Proof of the Elimination Lemma

In this section, we prove the following result: Lemma 18 (Elimination). Let r m > 0 be a round and p 1 , p 2 , . . . , p k+1 be k + 1 processes that, at the end of round r m , perceive the previous ⌊t/k⌋ + 3 rounds as synchronous. Then at least two such processes have the same estimate.

Notation. We proceed by contradiction. Suppose there exists a round r m > 0 and processes p 1 , p 2 , . . . , p k+1 such that est 1 < est 2 < . . . < est k+1 and all these processes see the previous ⌊t/k⌋ + 3 rounds as synchronous at the end of round r m (i.e., the processes have sF lag = true at the end of round r m ). For clarity, let r m = r 0 + ⌊t/k⌋ + 3, with r 0 ≥ 0 and define the set P = {p 1 , p 2 , . . . , p k+1 }. Also, we use the notation [1, ℓ] for the set {1, 2, . . . , ℓ}. In the following, we use a superscript to denote the round from which a local variable is perceived. For example, Active r0+2 i [r 0 + 1] is the Active set of process p i for round r 0 + 1, as seen from the end of round r 0 + 2. We omit the superscript when we consider variables from the end of round r 0 + ⌊t/k⌋ + 3.

Proof Outline. We begin by establishing some basic properties of the processes' views, in Propositions 1-4. We then aim to show that, in order for k + 1 estimates to be maintaned in the system by the processes in P (i.e., the processes have sF lag = true at the end of round r m ), at least k failures have to occur in each round seen as synchronous by the processes in P. Proposition 5 makes this intuition precise. Next, Proposition 6 establishes that there exists a process q from which all processes in P received a message in round r 0 + ⌊t/k⌋ + 2, and Proposition 7 shows that this process has to perceive k distinct failures per round in rounds r 0 + 1, . . . , r 0 + ⌊t/k⌋. This implies that process q has already experienced t -(t mod k) failures by the end of round r 0 + ⌊t/k⌋ + 1. Since each process in P receives a message from q, this implies that each of these processes may see at most k -1 new failures in rounds r 0 + ⌊t/k⌋ + 2 and r 0 + ⌊t/k⌋ + 3. To conclude, we show that this number of failures is not enough to maintain k + 1 distinct values in the system through the end of round r 0 + ⌊t/k⌋ + 3, which contradicts our initial assumption on the existence of processes p 1 , . . . , p k+1 . We note that throughout the proof we assume the existence of processes in P.

We first analyze the synchronous views of processes p 1 , p 2 , . . . , p k+1 . Proposition 1 (Synchrony). Let r be a round and p be a process such that at the end of round r, p sees the previous ℓ > 0 rounds as synchronous, i.e. AsynchRound r [r ′ ] = false, ∀r ′ ∈

[r -ℓ + 1, r]. Then Active r p [r -ℓ + 1] ⊇ Active r p [r -ℓ + 2] ⊇ . . . ⊇ Active r p [r].
Proof. Assume there exists a round r-ℓ+1 ≤ r ′ ≤ r-1 such that Active r p [r ′ +1] Active r p [r ′ ]. Then there exists a process q ∈ Active r p [r ′ + 1] \ Active r p [r ′ ], which implies that q / ∈ Active r p [r ′ ], therefore, by the way the sets Active and F ailed are built, q ∈ F ailed r p [r ′ ]. It follows that q ∈ F ailed r p [r ′ ] ∩ Active r p [r ′ + 1], therefore r ′ is asynchronous from the point of view of p at round r : contradiction.

The second proposition formalizes the intuition that if process p receives process q's message sent in some round r (either directly or through a relay), then p has the entire information about q's state at the end of round r -1.

Proposition 2 (Information Gathering). Let p i and p j be two processes in Π and let r c ≥ r be two rounds. If p i ∈ Active rc j [r], then for any round r ′ < r, Active r-

1 i [r ′ ] ⊆ Active rc j [r ′ ] and F ailed r-1 i [r ′ ] ⊆ F ailed rc j [r ′ ].
Proof. Fix r > 0 and r ′ < r. We proceed by induction on r c ≥ r.

Base case: If r = r c , then p j has received p i 's message in round r c , and by lines 23-26 of the updateSynchDetector() procedure, Active rc-1

i [r ′ ] ⊆ Active rc j [r ′ ] and F ailed rc-1 i [r ′ ] ⊆ F ailed rc j [r ′
] for all r ′ < r. Induction step: Let r i be the first round ≥ r in which p i ∈ Active ri j [r]. If r i = r, then p j receives a message from p i in round r and the claim is true.

If r i > r, then p j receives a message in round r i from a process p m such that

p i ∈ Active ri-1 m [r]. Since p i ∈ Active ri-1 m
[r], we can apply the induction hypothesis with r c := r i -1 and r := r to obtain that Active r

i [r ′ ] ⊆ Active ri-1 m [r ′ ] and F ailed r i [r ′ ] ⊆ F ailed ri-1 m [r ′ ],
for all r ′ < r. Since p j receives a message from p m in round r i , the claim follows.

The idea behind the third proposition is that if an estimate is held by some process at round r, then there exists at least one process which "carries" it in every previous round.

Proposition 3 (Carriers). Let r > 0 and p ∈ Π. If p has estimate v at the end of round r, then for all rounds 0 ≤ r ′ ≤ r, there exists a process q r ′ ∈ Active r p [r ′ ] such that est r ′ -1

q r ′ = v.
Proof. Assume that process p has estimate v at the end of round r, yet there exists a round 0 ≤ r 0 ≤ r such that no process with est r0-1 = v exists in Active r p [r 0 ]. First, notice that there has to exist a process s in Active r p [r] such that est r-1 s = v -this follows since a process may only adopt an estimate that has been proposed in the current round.

Let r ′ < r be the minimum round such that there exists a process s in Active r p [r ′ + 1] such that est r ′ s = v-the observation above ensures that such a round exists. As s ∈ Active r p

[r ′ + 1], Proposition 2 ensures that Active r ′ s [r ′ ] ⊆ Active r p [r ′ ]. Since Active r p [r ′ ] contains no processes with est r ′ -1 = v, it follows that Active r ′ s [r ′
] contains no processes with est r ′ -1 = v, and hence s has adopted estimate v at the end of r ′ without receiving any messages with estimate v, which contradicts the structure of the estimate-update mechanism.

The next proposition proves that two processes with synchronous views see the same information, with a maximum delay of one round.

Proposition 4 (View Consistency). Given processes p and q that see rounds r 0 +1, . . . , r 0 +ℓ+1 as synchronous, for all r ∈ [r 0 + 1, r 0 + ℓ], Active r0+ℓ+1 p

[r + 1] ⊆ Active r0+ℓ+1 q [r].
Proof. In order to simplify notation, we omit the superscript for the state variables that are seen from the end of r 0 + ℓ + 1, e.g. Active p [r 0 + ℓ] = Active r0+ℓ+1 p [r 0 + ℓ]. We make the distinction when necessary.

Assume by contradiction that there exists a process s ∈ Active p

[r + 1] \ Active q [r]. Since s / ∈ Active q [r], no process x in Active q [r 0 + ℓ + 1] can have s ∈ Active r0+ℓ x [r]. Therefore, ∀π ∈ Active q [r 0 + ℓ + 1], s ∈ F ailed r0+ℓ s [r]. However, since |Active p [r 0 + ℓ + 1]| ≥ n -t, |Active q [r 0 + ℓ + 1]| ≥ n -t and n -t > n
2 , p receives at least one message from a process in Active q [r 0 + ℓ + 1] in round r 0 + ℓ + 1. Since F ailed p [r] is the union of all F ailed sets p i received, it follows that s ∈ F ailed p [r]. At the same time, s ∈ Active p [r + 1], and therefore p notices an asynchrony in round r ∈ {r 0 + 1, . . . r 0 + ℓ}: contradiction. The next step is to show that in order for k + 1 estimates to be maintained in the system in a round, at least k failures have to occur in that round (these failures may be either process crashes, or messages not delivered in a timely manner because of asynchrony). More precisely, we identify one carrier that does not receive k messages which are received by at least one of the other carriers. Proposition 5. Let r be a round and c 1 , . . . , c k+1 be processes such that est r i < est r i+1 , ∀i ∈ [1, k]. Then there exists a process c ℓ ∈ {c 1 , . . . , c k+1 } such that c ℓ fails k processes in round r, i.e.

|F ailed r

c ℓ [r] ∩ i∈[1,k+1] Active r ci [r]| ≥ k.
Proof. Processes c 1 , . . . , c k+1 are carriers for values v 1 , . . . , v k+1 , respectively, at the end of round r. Proposition 3 ensures that there exist processes q 1 , . . . , q k+1 that are carriers for these values at the end of the previous round r -1 and q i ∈ Active ci [r], for all i ∈ [1, k + 1]10 . We prove that there exists an index j such that process c j does not receive messages from any of the processes q i with i = j. Consider process c k+1 . Assuming that c k+1 receives a message from one of the processes q i with i = j, it follows that c k+1 "sees" an estimate less than est k+1 in round r. In this case, the only possibility for c k+1 to adopt estimate est k+1 at the end of round r is for it to receive est k+1 in a message with sF lag i = true. Without loss of generality, assume that the message comes from process q k+1 . At this point, we turn our attention to process c k . Again, there are two possibilities: process c k adopted estimate est k either because it received it in a message with sF lag = true (line 19), or adopts it in line 20, which means that it receives no messages with sF lag = true, and no message with estimate < est k . However, in the latter case we are done, since it means that c k does not receive messages from any of the processes in {q 1 , q 2 , . . . , q k-1 , q k+1 } which is enough to prove the claim.

Therefore, we still have to analyze the case when process c k receives estimate v k in a message with sF lag = true. Again, without loss of generality, we assume that this message comes from process q k . At this point, we are in the case where q k+1 has sF lag = true and q k has sF lag = true. Considering process c k-1 , we can apply the same rationale to obtain that process q k-1 necessarily has sF lag = true. We proceed in this fashion to obtain that processes q k-2 , . . . , q 1 must have sF lag = true as well. However, returning to process q k+1 , we obtain a contradiction, since if processes q 1 , q 2 , . . . , q k have sF lag = true, process q k+1 cannot receive a message from any one of them (otherwise it will adopt an estimate < est k+1 in line 19 of propose()).

Therefore, at least one process c j ∈ {c 1 , c 2 , . . . , c k+1 } has to fail all processes q i with i = j in round r. Since, by definition, q i ∈ Active ci [r], for all i ∈ [1, k + 1], this concludes the proof.

At this point, we have gathered enough information to proceed with the final argument. We show that the synchrony requirements on the views of p 1 , p 2 , . . . , p k+1 imply that there exists a process q which they all perceive as active in round r 0 + ⌊t/k⌋ + 2. This means that q's message in round r 0 +⌊t/k⌋+2 reaches all processes p 1 , p 2 , . . . , p k+1 , either directly or through a relay. This implies that the view of process q at the end of round r 0 +⌊t/k⌋+1 has to be consistent with that of processes p 1 , p 2 , . . . , p k+1 , i.e. upon receiving q's message, no process in P notices an asynchrony in rounds r 0 + 1, r 0 + 2, . . . , r 0 + ⌊t/k⌋ + 1. Since processes p 1 , p 2 , . . . , p k+1 all hold distinct estimates at the end of r 0 + ⌊t/k⌋ + 3, we show that q's view has to contain k new failures in each round r 0 + 1, . . . , r 0 + ⌊t/k⌋. This implies that processes in P have to see k • ⌊t/k⌋ = t -(t mod k) failures in rounds r 0 + 1, . . . , r 0 + ⌊t/k⌋ + 1, which means that processes p 1 , . . . , p k+1 have at most t mod k failures "left" at the end of round r 0 + ⌊t/k⌋ + 1. Finally, we apply Proposition 5 to obtain that at least one of the processes p i has to see k new failures in round r 0 + ⌊t/k⌋ + 3, which leads to a contradiction, since the model ensures that all processes in P receive at least nt messages in every round.

We first show that there exists a process from which all processes p i receive a message in round r 0 + ⌊t/k⌋ + 2, either directly or though a relay. Proposition 6 (The common process). Given processes p 1 , p 2 , . . . , p k+1 as above, there exists a process q such that q

∈ k+1 i=1 Active i [r 0 + ⌊t/k⌋ + 2].
Proof. Fix a process q ∈ {p 1 , . . . , p k+1 }. For all processes p i ∈ {p 1 , . . . , p k+1 }, Proposition 4 implies that Active q [r 0 +⌊t/k⌋+3] ⊆ Active i [r 0 +⌊t/k⌋+2]. Since q ∈ Active q [r 0 +⌊t/k⌋+3] (a process always receives messages from itself), we obtain that q ∈ k+1 i=1 Active i [r 0 +⌊t/k⌋+2].

Note that in the following, we omit the subscript when denoting q's view and assume the Active q and F ailed q sets are always seen from the end of round r 0 + ⌊t/k⌋ + 1. In other words, we are analyzing the view that process q broadcasts to processes in P at the beginning of round r 0 + ⌊t/k⌋ + 2.

The next proposition shows that process q defined above has to receive k less messages in each round r 0 + 2, . . . , r 0 + ⌊t/k⌋ + 1. Proposition 7. Given the process q as defined in Lemma 6, for all rounds r ∈ {r 0 + 1, . . . , r 0 + ⌊t/k⌋}, |Active q [r] \ Active q [r + 1]| ≥ k.

Proof. Proposition 3 ensures that at the beginning of round r+1 there exist carriers c 1 , c 2 , . . . , c k+1 for values v 1 , v 2 , . . . , v k+1 respectively, where est r i = v i and c i ∈ Active rm pi [r + 1]. The key to proving the claim is to look at which of these carriers process q receives a message from in round r + 1. If process q receives no message from these carriers in r + 1, then we are done, since there are k + 1 carriers. Otherwise, we show that if process q receives a message from m such carriers (for m ≥ 1), then it has to perceive at least m -1 failures in round r just because it sees m distinct values propagated in the following round. Next, we show that q has to perceive a failure in round r for each of the other k + 1m values whose carriers did not successfully send q a message in round r + 1. The final argument shows that the two sets of failures (the m -1 corresponding to the "seen" carriers and the k + 1m corresponding to the "unseen" ones) are necessarily distinct.

We start the formal argument by noting that processes c 1 , c 2 , . . . , c k+1 are necessarily in Active q [r]: if c i / ∈ Active q [r], since p i receives q's message in r 0 + ⌊t/k⌋ + 2, process p i perceives an asynchrony in round r. Next, denote by M the set of processes in the intersection {c 1 , . . . , c k+1 } ∩ Active q [r + 1]. Let m = |M |, the cardinal of M , and let {s 1 , . . . , s m } = M .

If m = 0, we have identified a set of at least k + 1 processes {c 1 , . . . , c k+1 } that are in Active q [r], but not in Active q [r + 1] and we are done.

If m > 0, we can apply Proposition 5 to the processes (or the process) in M to obtain that there exists a process s ∈ M such that |F ailed , that is the set of processes that carrier s missed in round r. Since s ∈ Active q [r + 1], by Proposition 2, F ailed r s [r] ⊆ F ailed q [r]. Also, F ∩ Active q [r + 1] = ∅ (otherwise, q notices an asynchrony in round r, which propagates to the processes p i ). On the other hand, since s j ∈ Active q [r + 1] for all s j ∈ M , by applying Proposition 2 again we obtain that F ⊂ Active q [r]. Therefore, the set F has at least m -1 processes and is in Active q [r] \ Active q [r + 1].

In order to find more processes in Active q [r] \ Active q [r + 1], we analyze the set of processes G = {c 1 , c 2 , . . . , c k+1 }\Active q [r+1], that is the set of carriers whose message process q did not receive. By the above considerations, these processes are elements of Active q [r] \ Active q [r + 1], and the cardinal of G is k + 1m. We show that G ∩ F = ∅.

Assume for the sake of contradiction that there exists a process c i ∈ F ∩ G. Since c i ∈ F , it follows that c i ∈ F ailed q [r]. On the other hand, since c i ∈ G, there exists a process p i ∈ P such that c ∈ Active rm i [r + 1], by the definition of c i . However, since p i receives a message from q in round r 0 +⌊t/k⌋+2 > r+1, it follows by Proposition 2 that c i ∈ Active rm i [r+1]∩F ailed rm i [r], so p i perceives an asynchrony in round r ∈ {r 0 + 1, . . . , r 0 + ⌊t/k⌋}, which contradicts the definition of process p i .

Therefore G ∩ F = ∅. The processes in G ∪ F have the property that they are in Active q [r], but not in Active q [r + 1]. The above claim ensures that |G ∪ F | ≥ (k + 1m + m -1) = k, therefore |Active q [r] \ Active q [r + 1]| ≥ k.

The last result implies that |Active q [r 0 + ⌊t/k⌋ + 1]| ≤ nk • ⌊t/k⌋ = nt + t mod k, therefore |F ailed q [r 0 + ⌊t/k⌋ + 1]| ≥ t -(t mod k). Note that since every process p i receives a message from q in round r 0 +⌊t/k⌋+2, no process p i can receive a message in round r 0 +⌊t/k⌋+2 from a process that q has failed in round r 0 +⌊t/k⌋+1. More precisely, for all i ∈ {1, . . . , k +1}, Active Next, we show that this number of active processes is not enough to maintain k + 1 distinct values in the system in the remaining rounds r 0 + ⌊t/k⌋ + 2 and r 0 + ⌊t/k⌋ + 3. One way to see this is to first notice that the total number of messages received by processes in P may only decrease or remain the same, i.e. Active i [r 0 +⌊t/k⌋+3]\F ailed j [r 0 +⌊t/k⌋+3]| ≤ (n-t+t mod k)-k < n-t, so process p j receives less than n-t messages in round r 0 +⌊t/k⌋+3, a contradiction with the assumption that each process receives at least nt messages in every round.

The contradiction arises from the initial assumption that there exist k + 1 processes with distinct estimates and synchronous views of rounds r 0 + 1, . . . , r 0 + ⌊t/k⌋ + 3 at the end of round r 0 + ⌊t/k⌋ + 3. We conclude that the Elimination Lemma holds.

Improving the Algorithm

In fact, in some cases, processes can decide after seeing only ⌊t/k⌋ + 3 consecutive synchronous rounds: a process sets sF lag = true after seeing ⌊t/k⌋ + 2 synchronous rounds, and decides one round later. In this case, however, we require that ⌊ n-t+1 k+1 ⌋ ≥ 3k, which translates approximately into t ≥ 3k 2 . In order to improve further, for example, to decide in ⌊t/k⌋ + 2 rounds, some new technique is needed. We believe that an approach similar to that of [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF] in which estimates are sometimes de-prioritized can be used to obtain a matching algorithm.

Conclusion

We have presented a novel technique for simulating synchronous and partially synchronous executions in asynchronous shared memory. Our technique allows us to characterize the complexity of set agreement in partially synchronous systems, as well as to refine earlier lower bounds for early-deciding synchronous set agreement by determining the cost of early decision in terms of worst-case round complexity. More generally, our simulation technique is applicable to any decision task, i.e. one in which a process can safely copy its decision from others. We believe that our technique can also be expressed in terms of the standard BG simulation [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF]. In particular, instead of employing n simulators that agree through adopt-commit objects, we can use k + 1 simulators that utilize BG-agreements to agree on the messages received in every round. Thus, one direction of future work is to extend our lower bound results to other families of tasks by encapsulating the Extended BG simulation [START_REF] Gafni | The Extended BG simulation and the characterization of t-resiliency[END_REF]. Another direction is to fill the gap between the lower bound and the upper bound in eventually synchronous systems.

Proving distributed impossibility results and lower bounds often requires analysis of distributed executions, which has proven quite challenging (e.g., techniques involving algebraic topology). Moreover, there are a plethora of different models, multiplying the number of times each result needs to be re-proved. By contrast, distributed simulations offer the hope of deriving these results by direct reduction, thus basing the edifice of distributed computing on a few fundamental results. We believe that our results are one step toward developing just such a unified framework for distributed computation.

Parameters: 1 Algorithm 2 Shared variables: 3 AC[ 1 . 4 DEC [ 1 . 6 Task T1: 7 (

 12314167 A, number of phases numP , round array [R1, . . . , RnumP+1 ] .RnumP+1][1..n], array of adopt-commit objects .n], VAL[1..RnumP + 1][1..n], array of SWMR registers. Each entry is initially ⊥. 5 procedure propose(vi): start Task T1; start Task T2; , mi) ← compute(0, vi, true) % messages for the first round

8 for ρ = 1 to numP do 9 % 13 (

 8913 Begin a new phase: 10 Si ← ∅ ; sFlag i ← true 11 for r = Rρ to Rρ+1 -1 do 12 reci ← simulate(mi, r) % Simulate send/receive of round r. di, mi) ← compute(r, reci, sFlag i ) % Compute message for the next round.

14 if

 14 di = ⊥ then DEC [i].write(di); stop T2; return di 15 Task T2: 16 repeat for j = 1 to n do deci[j] ← DEC [i] until (∃ℓ : deci[ℓ] = ⊥) 17 stop T1; return deci[ℓ]

18

 18

31 return reci 32 Fig. 1 .

 321 Fig. 1. Simulating A in AS n,k , code for simulator pi.

j

  and |RECR+1 j | ≥ n -(|S[R]| + |∆| -1). By Lemma 6 and as no processes are initially suspected, |S[R]| ≤ kR. Also, the same Lemma implies that |∆| ≤ k. We thus obtain |REC R+1 j

  Otherwise, we have |∆| = k and thus, as ∆ ⊆ CD, |CD| ≥ k. Therefore in both cases we have |CD| ≥ min(k, d). As algorithm A is in the class ED(R, d), at least min(|CD|, d) ≥ min(k, d) processes in CD decide by the end of round R+1. A simulator whose simulated processes decides departs from the simulation and decides unless it fails ( line 15). Hence, we have |F [R+1]∪D[R+1]| ≥ min(d, k).

3 while true do 4 send 10 % 16 %Fig. 2 .

 410162 Fig. 2. The K4 algorithm, at process pi.

  r s [r] ∩ m j=1 Active r sj [r]| ≥ m -1. Let F denote the set F ailed r s [r] ∩ m j=1 Active r sj [r]

  r0+⌊t/k⌋+3 i [r 0 + ⌊t/k⌋ + 2] ⊆ Active r0+⌊t/k⌋+1 q [r 0 + ⌊t/k⌋ + 1].This relation implies the following bound on the number of messages that processes in P may receive in round r 0 + ⌊t/k⌋ + 2:| k+1 i=1 Active i [r 0 + ⌊t/k⌋ + 2]| ≤ nt + t mod k.

k+1i=1

  Active i [r 0 + ⌊t/k⌋ + 2] ⊇ k+1 i=1 Active i [r 0 + ⌊t/k⌋ + 3] by Proposition 1. Then | k+1 i=1 Active i [r 0 + ⌊t/k⌋ + 3]| ≤ nt + t mod k.On the other hand, processes p 1 , p 2 , . . . , p k+1 have k + 1 distinct estimates at the end of round r 0 + ⌊t/k⌋ + 3, therefore we can apply Proposition 5 to obtain that there exists a process p j ∈ {p 1 , . . . , p k+1 } such that |F ailed j [r 0 + ⌊t/k⌋ + 3] ∩ k+1 i=1 Active i [r 0 + ⌊t/k⌋ + 3]| ≥ k. Then |Active j [r 0 +⌊t/k⌋+3]| ≤ | k+1 i=1

  then there is no algorithm in ED(R, d); 2. If d < k, then any algorithm in ED(R, d) has a run in which some process decides at round R D = (⌊t/k⌋ + 1 + E(t, k, d)) or later, where E(t, k

For two vectors v and v ′ , v ⊆ v ′ if ∀i, 1 ≤ i ≤ n : v[i] = ⊥ ⇒ v[i] = v ′ [i].

It is essential for the parameter k of the set agreement problem to be the same as the maximum number of failures k among the simulators, since we reduce from the impossibility of k-set agreement in AS n,k .

Any algorithm A can be easily modified to satisfy this property.

If some process pi does fail in β in some round r ′ , we can consider the execution β ′ in which no message sent by pi after round r ′ is received by any other process.

Recall that for two size n vectors v, v ′ , v ⊆ v ′ if and only if ∀i, 1 ≤ i ≤ n : v[i] = ⊥ ⇒ v[i] = v ′ [i].

Here, the size of a snapshot in the number of non-⊥ entries in the vector view.

Although, for technical reasons, the statements of the results are expressed differently, a careful analysis of the arguments reveals that the claims are equivalent.

To simplify notation, we omit the superscript for the local variables, assuming that all such variables are seen from the end of round r

Acknowledgements

We would like to thank Hagit Attiya, Keren Censor, and the anonymous reviewers for their feedback on drafts of this paper.