Y Moses
email: moses@ee.technion.ac.il

M Raynal
email: raynal@irisa.fr

NO DOUBLE DISCOUNT: CONDITION-BASED SIMULTANEITY YIELDS LIMITED GAIN

Keywords: Agreement problem, Condition-based agreement, Consensus, Distributed algorithm, Early decision, Lower bound, Modularity, Process crash failure, Round-based computation model, Simultaneity, Synchronous message-passing system Système synchrone, algorithme distribué, condition, consensus, crash de processus, décision simultaée, modèle de calcul fondé sur les rondes, système synchrone

Assuming each process proposes a value, the consensus problem requires the non-faulty processes to agree on the same value that has to be a proposed value. Solutions to the consensus problem in synchronous systems are based on the round-based model, namely, the progress of the processes is according to synchronous rounds. Simultaneous consensus requires that the non-faulty processes decide not only on the same value, but decide during the very same round. It has been shown by Dwork and Moses that, in a synchronous system prone to t process crashes, the earliest round at which a common decision can be simultaneously obtained is (t + 1) -D where D is a non-negative integer determined by the actual failure pattern F .

The condition-based approach to solve consensus assumes that the input vector belongs to a set C (a set of input vectors satisfying a property called legality). Interestingly, the conditions for synchronous consensus define a hierarchy of sets of conditions

where the set S t t contains the condition made up of all possible input vectors). It has been shown that d + 1 is a tight lower bound on the minimal number of rounds for synchronous condition-based consensus.

This paper considers the synchronous condition-based consensus problem with simultaneous decision. It first presents a simple algorithm that directs the processes to decide simultaneously at the end of the round RS t,d,F = min((t + 1) -D, d + 1) (i.e., RS t,d,F = (t + 1) -max(D, δ) with δ = t -d). The paper then shows that RS t,d,F is a lower bound for the condition-based simultaneous consensus problem. It thus follows that the algorithm designed is optimal in each and every run, and not just in the worst case: For every choice of failure pattern by the adversary (and every input configuration), the algorithm reaches simultaneous as fast as any correct algorithm could do under the same conditions. This shows that, contrary to what could be hoped, when considering condition-based consensus with simultaneous decision, we can benefit from the best of both actual worlds (either the failure world when RS t,d,F = (t + 1) -D, or the condition world when RS t,d,F = d + 1), but we cannot benefit from the sum of savings offered by both. Only one discount applies.

I R I S A 1 Introduction

The consensus problem Fault-tolerant systems often require a means by which processes or processors can arrive at an exact mutual agreement of some kind [START_REF] Pease | Reaching Agreement in Presence of Faults[END_REF]. If the processes defining a computation have never to agree, that computation is actually made up of a set of independent computations, and consequently is not an inherently distributed computation. The agreement requirement is captured by the consensus problem that is one of the most important problems of fault-tolerant distributed computing. It actually occurs every time entities (usually called agents, processes -the word we use in the following-, nodes, sensors, etc.) have to agree. The consensus problem is surprisingly simple to state: each process is assumed to propose a value, and all the processes that are not faulty have to agree/decide (termination), on the same value (agreement), that has to be one of the proposed values (validity). The failure model considered in this paper is the process crash model. While consensus is impossible to solve in pure asynchronous systems despite even a single process crash [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF] ("pure asynchronous systems" means systems in which there is no upper bound on process speed and message transfer delay), it can be solved in synchronous systems (i.e., systems where there are such upper bounds) whatever the number n of processes and the number t of process crashes (t < n).

An important measure for a consensus algorithm is the time it takes for the non-faulty processes to decide. As a computation in a synchronous system can be abstracted as a sequence of rounds, the time complexity of a synchronous consensus algorithm is measured as the minimal number of rounds (R t ) a process has to execute before deciding, in the worst case scenario. It has been shown (see, e.g., in [START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF][START_REF] Moses | A Layered Analysis of Consensus[END_REF]) that R t = t + 1. Moreover, that bound is tight: there exist algorithms (e.g., see [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations and Advanced Topics[END_REF][START_REF] Lynch | Distributed Algorithms[END_REF][START_REF] Raynal | Consensus in Synchronous Systems: a Concise Guided Tour[END_REF]) where no process ever executes more than R t rounds (these algorithms are thus optimal with respect to that bound).

Early decision While t + 1 rounds are needed in the worst case scenario, the major part of the executions have few failures or are even failure-free. So, an important issue is to be able to design early deciding algorithms, i.e., algorithms that direct the processes to decide "as early as possible" in good scenarios. Let f , 0 ≤ f ≤ t, be the number of actual process crashes in an execution. It has been shown that the lower bound on the number of rounds is then R t,f = min(f + 2, t + 1) (e.g., [START_REF] Dolev | Early Stopping in Byzantine Agreement[END_REF][START_REF] Moses | A Layered Analysis of Consensus[END_REF][START_REF] Wang | A Bivalency Proof of the Lower bound for Uniform Consensus[END_REF]). As before, this bound is tight: algorithms in which no process ever executes more than R t,f exist (e.g., see [START_REF] Dolev | Early Stopping in Byzantine Agreement[END_REF][START_REF] Garg | Elements of Distributed Computing[END_REF][START_REF] Raynal | Consensus in Synchronous Systems: a Concise Guided Tour[END_REF]).

The condition-based approach and the hierarchy of synchronous conditions

The condition-based approach has been initially introduced to circumvent the impossibility of solving consensus in an asynchronous system prone to crash failures [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]. It consists in restricting the set of input vectors that can be proposed (such a set is called a condition) in such a way that consensus becomes solvable in crash-prone asynchronous systems every time the input vector belongs to the condition. A main result associated with this approach is the following [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] : a condition C allows to solve consensus in an asynchronous system prone to up to x process crashes iff it is x-legal (a condition is x-legal if each of its input vectors contains more than x times the value decided from that vector, and the Hamming distance of two vectors from which different values can be decided is greater than x). As we can see, there is a strong connection between the condition-based approach and error-correcting codes [START_REF] Friedman | Asynchronous Agreement and its Relation with Error-Correcting Codes[END_REF].

The condition-based approach has then been extended from computability in asynchronous systems to efficiency in synchronous systems. More precisely, let us consider a synchronous system where up to t processes can crash, and let S d t be the set containing all the (t -d)-legal conditions (the parameter d is called the degree of the condition, and the quantity (t -d) measures the difficulty of the condition). The following hierarchy has been established in [START_REF] Mostéfaoui | Synchronous Condition-Based Consensus[END_REF]:

S 0 t ⊂ S 1 t ⊂ • • • ⊂ S d t ⊂ • • • ⊂ S t t . Considering a condition C ∈ S d
t and an input vector I ∈ C, it is shown in [START_REF] Mostéfaoui | Synchronous Condition-Based Consensus[END_REF] that synchronous consensus can be solved in two rounds when d = 0, and in d + 1 rounds when 1 ≤ d ≤ t. It is also shown that d + 1 is a tight lower bound, when the input vector belong to C (with C ∈ S d t and C / ∈ S d-1 t

). It is worthwhile looking at the "extreme" sets S 0 t and S t t . On one side, S t t includes the condition that contains all the possible input vectors. On the other side, the family of conditions S 0 t , that is the largest set of conditions that allow to solve the consensus problem in asynchronous systems prone to up to t crashes, is also the family of conditions that allows to solve the consensus problem optimally in a synchronous system prone to t crashes.

Simultaneous decision

Consensus agreement is a data agreement property, namely the processes have to agree on the same value. According to the actual failure pattern, and the way this pattern is perceived by the processes, it is possible for several processes to decide at distinct rounds. The only guarantee lies in the fact that this round can be bounded (by R t or R t,f if we consider an early-deciding algorithm, or d+1 if we consider a condition-based algorithm PI n ˚1898 instantiated with a condition C ∈ S d t and assume the input vector always belongs to C). This uncertainty on the set of round numbers at which the processes decide, can be a serious drawback for the real-time oriented applications where agreement is required, not only on the decided value, but also on the time the decision is taken. More precisely, these applications require that the processes decide on the same value (data agreement), during the very same round (time agreement). This property is also called simultaneous decision.

All the "classical" consensus algorithms where all the processes that do not crash decide systematically at the end of the round R t = t + 1 ensure simultaneous decision. It is shown in [START_REF] Dolev | Early Stopping in Byzantine Agreement[END_REF][START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF] that the earliest round number at the end of which a common decision can be simultaneously taken is RS t,F = (t + 1) -D where D is a non-negative integer whose value depends on the actual failure pattern F . 1 More precisely, let C[r] be the set of the processes that are seen as crashed by (at least) one of the processes that survive (i.e., do not crash before the end of) round r. For any r, let d r = max(0, |C[r]| -r). We have D = max r≥0 (d r ). So, when considering the bound (t + 1) -D, D represents the number of rounds that could be saved with respect to the worst case t + 1 bound, while guaranteeing simultaneous agreement. Algorithms that solve simultaneous consensus optimally are described in [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. It is interesting to notice that the greatest values of D are obtained when many processes crash early. If at most one process crashes at each round, we obtain D = 0 and the earliest round for simultaneous decision is then t + 1. At first glance, this can appear counter-intuitive. Actually it is not, it is only the consequence of the fact that crashes are stable while "not to be crashed" is not a stable property, and simultaneous decision requires a common knowledge that can be based only on stable facts.

Content of the paper

The paper investigates the simultaneous decision in the context of the condition-based approach. It addresses the following question: "Assuming a condition C ∈ S d t , an input vector I ∈ C, a failure pattern F , which is the earliest round at which a simultaneous decision can be obtained?"

Let δ = t -d (i.e., C is δ-legal). The paper shows that RS t,d,F = (t + 1) -max(D, δ) (or equivalently, min(t + 1 -D, d + 1)) is a tight lower bound. To show it, the paper first presents a simple condition-based algorithm where the processes simultaneously decide at the end of the round RS t,d,F . It then addresses the more difficult side, namely it shows that there is no condition-based algorithm for simultaneous agreement that, given a run with the failure pattern F , directs the processes to simultaneously decide at round r with r < RS t,d,F . Hence, the paper shows that there is no "double discount", one coming from the condition the input vector belongs to, the other one coming from the best gain (in terms of the number of rounds) due to early crashes. The best that can be done is only to benefit from the best world that occurs in the actual run, namely, (t + 1) -D or (t + 1) -δ. The benefits of both worlds cannot be "added" to provide a bound smaller than the smallest of them.

Roughly speaking, our algorithm is obtained by running a condition-based algorithm that is based on [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF], that runs for t + 1 -δ rounds in parallel with a simultaneous consensus algorithm based on [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF], that in turn decides in t + 1 -D rounds, where D depends on the failure pattern. If D ≥ δ then the latter algorithm halts first, and the decision value that it produces is adopted. Otherwise, consensus is reached in t + 1 -δ rounds, using the decision value produced by the first (condition-based) algorithm. Because decisions are simultaneous, the algorithms can be seamlessly combined in this way. The main technical contribution of the paper is in the lower bound proof, showing that this scheme cannot be improved on. It yields optimally fast agreement in all runs.

Computation model, conditions and problem specification 2.1 Computation model

Round-based synchronous system The system model consists of a finite set of processes, namely, Π = {p 1 , . . . , p n }, that communicate and synchronize by sending and receiving messages through channels. (Sometimes we also use p and q to denote processes.) Every pair of processes is connected by a bi-directional reliable channel (which means that there is no creation, alteration, loss or duplication of message).

The system is round-based synchronous. This means that each execution consists of a sequence of rounds. Those are identified by the successive integers 1, 2, etc. For the processes, the current round number appears as a global variable r that they can read, and whose progress is managed by the underlying system. A round is made up of three consecutive phases:

• A send phase in which each process sends the same message to all the processes (including itself).

• A receive phase in which each process receives messages. The fundamental property of the synchronous model lies in the fact that a message sent by a process p i to a process p j at round r, is received by p j at the very same round r. • A computation phase during which each process processes the messages it received during that round and executes local computation.

Process failure model A process is faulty during an execution if its behavior deviates from that prescribed by its algorithm, otherwise it is correct. We consider here the crash failure model, namely, a faulty process stops its execution prematurely. After it has crashed, a process does nothing. If a process crashes in the middle of a sending phase, only a subset of the messages it was supposed to send might actually be received.

As already indicated, the model parameter t (1 ≤ t < n) denotes an upper bound on the number of processes that can crash in a run. A failure pattern F is a list of at most t triples q, k q , B q . A triple q, k q , B q states that the process q crashes while executing the round k q (hence, it sends no messages after round k q ), while the set B q denotes the set of processes that do not receive the message sent by q during the round k q .

The simultaneous consensus problem

The problem has been informally stated in the introduction: every process p i proposes a value v i (called its initial value) and the processes have to decide, during the very same round, on the same value that has to be one of the proposed values. This can be stated as a set of four properties that any algorithm solving the problem has to satisfy.

• Decision. Every correct process decides.

• Validity. A decided value is a proposed value.

• Data agreement. No two processes decide different values.

• Simultaneous decision (or Time agreement). No two processes decide at distinct rounds.

The condition-based approach

Notation Let V be the set containing all the values that can be proposed, with |V| ≥ 2. An input configuration is an assignment I : Π → V of an initial value v i ∈ V to each process p i . An input vector is a size n vector corresponding to an input configuration. A condition is a set of input vectors. Let ⊥ denote a default value such that ⊥ / ∈ V and ∀a ∈ V, ⊥ < a. We usually denote by I an input vector (all its entries are in V), and with J a vector that may have some entries equal to ⊥. Such a vector J is called a view. The number of occurrences of a value a ∈ V ∪ {⊥} in the vector J is denoted # a (J). Given two vectors I1 and I2, dist(I1, I2) denotes their Hamming distance.

Legality Not all the conditions allow to solve consensus in an asynchronous distributed system prone to process crashes (due to the FLP impossibility result [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF]). So, to solve consensus in such a system, a condition C has to meet constraints. Those can be expressed with the legality notion defined as follows:

Definition 1 [START_REF] Friedman | Asynchronous Agreement and its Relation with Error-Correcting Codes[END_REF][START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] A condition C is x-legal if there exists a function H : C → V with the following properties: (1) ∀I ∈ C: # H(I) (I) > x, and (2) ∀I1, I2 ∈ C:

H(I1) = H(I2) ⇒ dist(I1, I2) > x.
This means that the value extracted from I by H() appears "often enough" in I (more than x times), and two vectors from which different values are extracted by H() are "far enough apart" from the Hamming distance point of view. A main result of [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] is the characterization of the largest set of conditions that allow to solve consensus in an asynchronous system: Theorem 1 [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] If C is x-legal then consensus can be solved under C in an asynchronous system prone to up to x process crashes. Conversely, there exists an (x -1)-legal condition C for which consensus is unsolvable in the presence of x process crashes.

Intuitively, a condition selects a proposed value to become the decided value, namely, the value decided from an input vector I is H(I). A general method to define conditions is described in [START_REF] Mostefaoui | Condition-based Consensus Solvability: a Hierarchy of Conditions and Efficient Protocols[END_REF]. As an example, let us consider the condition M x defined as follows from the function max() (where max(I) returns the greatest value in I): I ∈ M x ⇔ # max(I) (I) > x. It is shown in [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] that M x is x-legal, and consequently consensus can be solved despite up to x process crashes when the input vectors are such that each of them has at least x + 1 entries equal to its greatest entry.

Lemma 1 [START_REF] Mostéfaoui | Synchronous Condition-Based Consensus[END_REF] Let C be an x-legal condition. If I1, I2 ∈ C, # ⊥ (J) ≤ x, J ≤ I1 and J ≤ I2, we have H(I1) = H(I2).

Because of this lemma, H() can be extended to vectors J with at most x entries equal to ⊥ by choosing an arbitrary I ∈ C with J ≤ I.

Definition 2 Let C be an x-legal condition, I a vector in C, and J any vector such that J ≤ I and # ⊥ (J) ≤ x. The definition of H() is extended to such vectors J as follows: H(J) = H(I). Theorem 2 [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] Let C be an x-legal condition. It is also (x -1)-legal. Moreover, there exist conditions that are (x -1)-legal but not x-legal. The synchronous hierarchy of classes of conditions Let us consider a synchronous system prone to up to t process crashes, and let S d t be the set of all the (t -d)-legal conditions. Let us observe that d = t defines the class of 0-legal conditions which is the largest one and includes every condition (and in particular the "trivial" condition that contains all the possible input vectors). Due to Theorem 2 the classes (S d t ) 0≤d≤t define the following hierarchy [START_REF] Mostéfaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]:

S 0 t ⊂ • • • ⊂ S d t ⊂ S d+1 t ⊂ • • • ⊂ S t t .
As we shall see, this hierarchy of conditions allows solving synchronous consensus with protocols that take more and more rounds, as we go from d = 0 to d = t. And d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system.

The simultaneous condition-based consensus problem

Let us assume that the input vectors always belong to a condition C ∈ S d t . Let δ = t -d (i.e., C is δ-legal). In order to eliminate the trivial solution where the processes always decide at round d + 1 (= t + 1 -δ), the simultaneous condition-based consensus problem is defined by the four properties stated in Section 2.2, plus the following earlydeciding property:

• Early decision. No process decides after the round RS t,d,F = (t + 1) -max(D, δ) (where D is the value derived from failure pattern F as described in the introduction).

An optimal condition-based simultaneous consensus algorithm

This section presents a simple condition-based simultaneous consensus algorithm in which the processes decide at the end of the round RS t,d,F = (t + 1) -min(D, δ). It will be shown in Section 4 that RS t,d,F is the smallest number of rounds for simultaneous condition-based consensus. The proposed algorithm is built modularly. It combines two base algorithms. One is a condition-based algorithm that, when instantiated with a δ-legal condition C (i.e., C ∈ S d t , with δ = t -d, 1 ≤ d ≤ t, and the input vector I belongs to C) directs the processes to decide simultaneously at the end of round d + 1 = t + 1 -δ. The second is a simultaneous (non-condition-based) consensus algorithm that directs the processes to decide at the end of the round t + 1 -D. These base algorithms are first presented. Their combination in which the processes simultaneously decide at the end of the round round RS t,d,F = (t + 1) -min(D, δ) is then described.

A condition-based simultaneous consensus algorithm

Preliminary definitions

As the system model requires each process to send a message to all the processes at each round, process failures can be easily detected, and this detection is done as soon as possible.

Failure discovery

The failure of a process q is discovered (for the first time) in round r if r is the first round such that there is a process p that (1) does not receive a round r message from q, and (2) survives (i.e., completes without crashing) round r.

Irisa

Clean rounds A round r is clean if no process is discovered faulty for the first time in that round [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF]. This means that a process that crashes during a clean round r has sent its round r message to all the processes that proceed to the round r + 1.

The following property is an immediate consequence of the previous definitions. (In a precise sense, a clean round can be used to ensure that the knowledge of the various processes is identical. Once this happens the processes are in agreement about initial values. They then need to discover this and coordinate their decisions.) Property 1 If round r is clean, then all the processes that proceed to round r + 1 received, during the round r, messages from the same set of processes (including at least all of them).

Observe that a clean round is not necessarily a failure-free round. It is possible for a process p to crash in a clean round r in such a way that no process surviving round r notices its crash in round r (p crashes after sending its round r messages at least to all processes that survive round r and before the end of the round). Similarly, a failure-free round is not necessarily clean. For example, a failure-free round r + 1 that follows a clean round r during which a crash occurred is not clean.

A simple (non-optimal) condition-based algorithm

The first algorithm we present directs the processes to decide at the end of the round (t + 1) -δ. It is an adaptation of an algorithm described in [START_REF] Mostéfaoui | Synchronous Condition-Based Consensus[END_REF] that does not satisfy the simultaneous decision property2 . The algorithm is described in Figure 1. Each process p i uses three local variables.

• V i is an array whose aim is to contain p i 's local view of the input vector. Initialized to [⊥, . . . , ⊥], it contains at most t entries equal to ⊥ at the end of the first round (line 105). • v cond i (initialized to ⊥) is destined to contain the value H(I) that the condition C associates with the input vector I (line 106). As the condition C is δ-legal, H(I) can be computed from H(V i ) only when the local view V i of p i has at most δ entries equal to ⊥ (see Lemma 1 and Definition 2). • v nocond i (initialized to ⊥) is destined to contain the value to be decided when no value can be decided from the condition because there are too many failures during the first round (more than δ processes crash). When this occurs, a process will decide the greatest proposed value it has ever seen.

The behavior of a process p i is simple. During the first round (lines 102-108), p i determines its local view V i of the input vector I, computes v cond i if it sees not too many failures (i.e., at most δ crashes), and computes v nocond i in case the condition is useless because there are more than δ crashes. Then, from the second round until round t + 1 -δ = d + 1, the processes use the flood set strategy to exchange their current values v cond i and v nocond i , and keep the greatest ones of each. At the end of the round t + 1 -δ, a process p i decides the value in v cond i if that value is not ⊥; otherwise, it decides the value in v nocond i (that is then different from ⊥ as we will see in the proof).

Theorem 3

The algorithm described in Figure 1 solves the condition-based consensus problem. Moreover, the processes decide at the end of the round (t + 1) -δ.

The proof appears in Appendix A.

An optimal algorithm for simultaneous consensus

The second base algorithm solves optimally the simultaneous consensus problem, i.e., the processes decide at the end of the round (t + 1) -D (where the non-negative integer D -defined in the Introduction-depends on the failure pattern). This algorithm is from [START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. We describe it for self-containment of the paper.

The horizon notion

Given a process p i and a round r ≥ 1, let x be the number of process crashes that (1) occurred between the round 1 and the round r -1 (included) and (2) are known by p i by the end of r.

The horizon notion was introduced in [START_REF] Mizrahi | Continuous Consensus via Common Knowledge[END_REF]. A horizon value is associated with each round r, more precisely, the value h i (r) = r + t -x is the horizon of p i at round r. We have h i (1) = t + 1. If three crashes occurred by the end of the first round and are reported to p i during the second round, we have

h i (2) = t -1. operation propose(v i ): (101) V i ← [⊥, . . . , ⊥]; v cond i ← ⊥; v nocond i ← ⊥; (102) when r = 1 (103) begin round (104) send (v i ) to all; (105) for each v j received do V i [j] ← v j end for; (106) if (# ⊥ (V i ) ≤ δ) then v cond i ← H(V i ) end if; (107)
v nocond i ← max( all the v j received during r) (108) end round; (109) when r = 2, 3, . . . do (110) begin round (111) send (v cond i , v nocond i ) to all; (112) v cond i ← max( all the v cond j received during r); (113) v nocond i ← max( all the v tmf j received during r); As we will see, the horizon notion is a key notion to determine the smallest round at the end of which the same value can be simultaneously decided. The following simple theorem (that will be exploited in the presentation of the algorithm) explains why this notion is crucial.

(114) if r = (t + 1) -δ¡ then (115) if (v cond i = ⊥) then return (v cond i ) else return (v nocond i ) end if (116) end if (117) end round
Theorem 4 [START_REF] Mizrahi | Continuous Consensus via Common Knowledge[END_REF] Let x be defined as indicated above, and p i a process that survives round r. There is a clean round

y such that r ≤ y ≤ h i (r) = r + t -x.
Proof Let us first observe that, as at least x processes have been discovered as faulty between the round 0 and the round r -1 (included), at most t -x processes can be discovered as faulty between the round r (included) and the round r + t -x (included). But there are t -x + 1 rounds from r to r + t -x, from which we conclude that at least one of these rounds is clean.

2 T heorem 4

The algorithm Local variables

Each process p i manages the following local variables. Some variables are presented as belonging to an array. This is only for notational convenience, as such array variables can be implemented as simple variables.

• est i contains, at the end of r, p i 's current estimate of the decision value. Its initial value is v i , the value proposed by p i . • f i [r] denotes the set of processes from which p i has not received a message during the round r. (So, this variable is the best current estimate that p i can have of the processes that have crashed.)

Let f i [r] = Π \ f i [r] (i.e.
, the set of processes from which p i has received a round r message).

• f i [r -1]
is a value computed by p i during the round r, but that refers to crashes that occurred up to the round r -1 (included), hence the notation. It is the value

pj ∈fi[r] f j [r -1], which means that f i [r -1]
is the set of processes that were known as crashed at the end of the round r -1 by at least one of the processes from which p i has received a round r message. This value is computed by p i during the round r. As a process p i receives its own messages, we have

f i [r -1] ⊆ f i [r -1]. • bh i [r]
[0] = h i (0) = t + 1.
Process behavior Each process p i not crashed at the beginning of r sends to all the processes a message containing its current estimate of the decision value (est i ), and the set f i [r -1] of processes it currently knows as faulty. After it has received the round r messages, p i computes the new value of est i and the value of bh i [r]. The new value of est i is the smallest of the estimates values it has seen so far. As far as the value of bh i [r] is concerned, we have the following.

• The computation of bh i [r] has to take into account h i (r). This is required to benefit from Theorem 4 that states that there is a clean round y such that r ≤ y ≤ h i (r). When this clean round will be executed, any two processes p i and p j that execute it will have est i = est j , and (as they will receive messages from the same set Irisa of processes, see Property 1) will be such that

f i [r -1] = f j [r -1].
It follows that, we will have h i (y) = h j (y), thereby creating correct "seeds" for determining the smallest round for a simultaneous decision. This allows the processes to determine rounds at which they can simultaneously decide. • As we are looking for the first round where a simultaneous decision is possible, bh i [r] has to be set to min h i (0), h i (1), . . . , h i i.e., bh i

[r] = min bh i [r -1], h i (r) .
Finally, according to the previous discussion, the algorithm directs a process p i to decide at the end of the first round r that is equal to the best horizon currently known by p i , i.e., when r = bh i [r].

The resulting algorithm is presented in Figure 2, where h i (r) (see line 208) is expressed as a function of r -1 to emphasize the fact that it could be computed at the end of the round r -1 by an external omniscient observer. The local boolean variable decided i is used only to prove the optimality of the combined algorithm (see Section 4). Its suppression does not alter the algorithm. Let us observe that, as no process can be discovered faulty before the first round, we have C[0] = 0. More generally, we assume C[r] = 0 for all r ≤ 0 (the fictitious rounds -1 and 0 will be used in section 4 for ease of exposition). Notice also that D ≥ 0, since

algorithm PROPOSE(v i ): (201) est i ← v i ; bh i [0] ← t + 1; f i [0] ← ∅; decided i ← false; % initialization % (202) when r = 1,
let h i (r) = (r -1) + (t + 1 -|f i [r -1]|); (209) bh i [r] ← min bh i [r -1], h i (r)¡ ; (210) if r = bh i [r] then decided i ← true; return (est i ) end if (211) end round
C[0] = 0 and D ≥ d 0 = C[0] -0 = 0.
The following optimality results are shown in [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF]: the smallest number of rounds RS t,F that any simultaneous decision consensus algorithm can achieve is RS t,F = (t + 1) -D when t < n -1, and RS t,F = t -D when t = n -1. The following theorem is proved in [START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. For completeness, this proof is given in appendix B.

Theorem 5 Let t < n. The algorithm described in Figure 2 solves the consensus problem with simultaneous decision. In a run with failure pattern F , decision is reached in round t + 1 -D, where D = D(F ) is the waste inherent in F .

An optimal condition-based simultaneous consensus algorithm

As previously announced, an optimal condition-based simultaneous consensus algorithm can be obtained from the two base algorithms described in Figures 1 and2. Their combination consists in executing both algorithms in parallel as follows:

PI n ˚1898 1. The r-th round, 1 ≤ r ≤ t + 1 -δ, of the combined algorithm is a simple merge of the r-th round of both algorithms. This means that the message sent by p i at round r now piggybacks v cond i , v nocond i , est i and

f i [r -1]. 3 2.
The lines 114-116 of the algorithm in Figure 1, and the line 210 of the algorithm in Figure 2 are replaced by the following lines:

if (r = bh i [r]) ∨ (r = t + 1 -δ) then if (r = bh i [r]) then decided i ← true; return (est i ) else if (v cond i = ⊥) then return (v cond i ) else return (v nocond i ) end if end if
The following theorem is an immediate consequence of the combination of Theorem 3 and Theorem 5. More precisely, if the algorithm described in Figure 2 terminates first (case r = bh i [r] < t + 1 -δ), or both terminate at the same round (case r = bh i [r] = t + 1 -δ), that algorithm imposes the common early decision round, namely bh i [r]. Otherwise, the condition-based algorithm imposes t + 1 -δ as the common early decision round.

Theorem 6 Let t < n. The algorithm obtained by the combined execution (as described in the previous items) of the algorithms described in Figures 1 and2 solves the condition-based simultaneous consensus problem. In a run with failure pattern F , decision is reached in round t + 1 -max(D, δ).

On the optimality of the algorithm: t + 1 -min(D, δ) is a lower bound

This section proves that the algorithm described in Section 3.4 is optimal: In a synchronous system prone to up to t process crashes (with t < n -1), there is no deterministic algorithm that can ever solve the simultaneous conditionbased consensus problem in fewer than (t + 1) -max(D, δ) rounds. The proof relies on notions introduced in [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Mizrahi | Continuous Consensus via Common Knowledge[END_REF][START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. We are unable to present the definitions and the proof in the main text due to page limitation. A complete treatment is provided in Appendix C. In this section we sketch the main ideas of the proof, with precise definitions and proofs in the Appendix.

Consider a condition C = {0 n , 1 n } containing only two extreme initial configurations: All zeros and all ones. Clearly, consensus can be solved for C with no rounds of communication. Observe that C is x-legal for 1 ≤ x ≤ n. Thus, the property of being x-legal is useful mainly for establishing upper bounds on consensus as demonstrated in Theorems 1 and 3. For the purpose of proving a matching lower bound, we define a condition C to be x-coverable if, roughly speaking, for every v ∈ V and I ∈ C, an input configuration that does not contain v is reachable from I by a finite sequence of steps among elements of C where a step is allowed between configurations whose Hamming distance is at most x.

The lower bound is based on the well-known connection between simultaneous agreement and common knowledge [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Moses | Programming Simultaneous Actions Using Common Knowledge[END_REF]. This connection implies that it is possible to simultaneously decide on a value v ∈ V only once it becomes common knowledge that one of the initial values of I is v. This has a nice graph-theoretic interpretation: For a fixed protocol and a round r ≥ 0 we can define a graph G(r) whose nodes correspond to runs of the protocol. This graph has the property that the existence of an initial value of I is common knowledge in round r of a run σ if and only if every run in σ's connected component in G(r) contains at least one initial value of I. Let D be the waste inherent in a failure pattern F . The analysis of common knowledge in crash failures shows that common knowledge of initial values is attained at the end of round t + 1 -D [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Mizrahi | Continuous Consensus via Common Knowledge[END_REF]. However, before round t + 1 -D, it is not common knowledge that even one failure has occurred. The crux of the proof involves proving the following claim.

Claim Suppose that the condition C is x-coverable and that t+1-D ≤ t+1-x. Moreover, let σ and σ be two runs with input configurations I, I , respectively, where the waste in each of the runs does not exceed D. If the Hamming distance dist(I, I ) ≤ x then σ and σ are in the same connected component of G(r) for all rounds r < t + 1 -D.

Using this claim and the definition of x-coverable, it is then shown that no initial value becomes common knowledge (and thus simultaneous decision is impossible) before round RS t,d,F = (t + 1) -max(D, δ). This yields matching upper and lower bounds for each and every run.

Conclusion

This paper focused on simultaneous decision in the condition-based consensus setting. It has presented two results. The first is a condition-based consensus algorithm in which processes decide simultaneously at the end of the round RS t,d,F = (t + 1) -max(D, δ) where D ≥ 0 is a value that depends on the actual failure pattern, and δ = t -d depends on the position of the condition C (the algorithm is instantiated with) in the hierarchy of synchronous legal conditions, namely C ∈ S d t , where the hierarchy is

S 0 t ⊂ • • • ⊂ S d t ⊂ • • • ⊂ S t t
(the set S t t containing the condition made up of all possible input vectors).

The second result is a proof that RS t,d,F is a lower bound on the number of rounds of the simultaneous conditionbased consensus problem. This bound shows that we can benefit from the best world provided by the actual run (failure world when RS t,d,F = (t + 1) -D or condition world when RS t,d,F = (t + 1) -δ), but not from an "addition" of both. There is no double discount for simultaneous condition-based consensus.

A Proof of Theorem 3

Theorem 3 The algorithm described in Figure 1 solves the condition-based consensus problem. Moreover, the processes decide at the end of the round (t + 1) -δ.

Proof Let C be the δ-legal condition the algorithm is instantiated with, and I ∈ C the actual input vector. Validity. Let us observe that every process p i that terminates the first round is such that v nocond i = ⊥ and v nocond i contains a proposed value. Moreover, if v cond i = ⊥, we have v cond i = H(I) that (due to Lemma 1 and Definition 2) is a value belonging to I. Then, due to the exchanges of values during the next rounds, v nocond i always contains a proposed value, and the same is true for v cond i if v cond i = ⊥. It follows that the value decided by a process at line 114 is a proposed value.

Decision and simultaneous decision. The fact that the processes that decide (this set of processes trivially includes all the correct processes), decide during the round (t + 1) -δ follows directly from line 114. Data agreement. We consider two cases.

• Each process p i that executes the first round is such that # ⊥ (V i ) ≤ δ. In that case, each process computes v cond i = H(V i ) (line 106). It follows from Lemma 1 and Definition 2 that we have H(V i ) = H(I) = v for any process p i , from which we conclude that v cond i = v for any process p i that terminates the first round. Consequently, no process that executes line 115 decides a value different from v. • One process p i that executes the first round is such that # ⊥ (V i ) > δ. This means that at least δ + 1 = t -d + 1

processes crashed during the first round. This means that at most d -1 processes can crash between the end of the first round and the end of round r = (t + 1) -δ = d + 1, i.e. during a period of d rounds. It follows that there is a clean round r such that 2 ≤ r ≤ (t + 1) -δ = d + 1. Due to Property 1, all the processes that execute round r receive the same set of messages. Consequently, at the end of r , all these processes have the same value v (v can possibly be ⊥) in their local variable v cond i , and the same value v (with v = ⊥) in their local variable v nocond i , from which follows that, in that case, no two processes can decide different values.

2 T heorem 3

B Proof of Theorem 5

This appendix proves the (non-condition-based) simultaneous consensus algorithm described in Figure 2 (Section 3.2) is correct.

Lemma 2 Validity property. A decided value is a proposed value.

Proof The proof is an immediate consequence of the initialization of the est i local variables (line 201), the reliability of the channels, and the min() operation used at line 207.

2 Lemma 2 Lemma 3 Let p i be a correct process. ∀r ≥ 0 we have h i (r) ≥ r.

Proof Since the processes in the set f i [r -1] are processes that have crashed by the end of the round r -1, it follows that t

-|f i [r -1]| ≥ 0. Consequently, h i (r) = r + t -|f i [r -1]| ≥ r. 2 Lemma 3
Notation: Considering an arbitrary execution, let p i be a process that is correct in that execution.

• Let BH i = min r≥0 h i (r). BH i is the smallest value ever attained by the function h i (r), i.e., the smallest horizon value determined by p i .

• Let L i = max({r | h i (r) = BH i }). L i is the last round whose horizon value is BH i . It follows from these definitions that if L > L i then h i (L ) > h i (L i ).
Irisa Lemma 4 Let t < n. The round L i is a clean round (i.e., no process is discovered faulty for the first time in that round).

Proof Assume, by way of contradiction, that L i is not clean (recall that p i is a correct process). This means there is a process p z that is seen faulty for the first time in round L i by some process p y . Notice that p z / ∈ f i [L i -1] since p z was not discovered faulty in the previous rounds. There are two cases.

• Case 1: p i receives a message from p y in round L i + 1.

(This case includes the case where p i and p y are the same process). As p y does not receive a message from p z during L i , and a crash is stable, we have

p z ∈ f y [L i ].
Moreover, due to the case assumption, and the fact that the round

L i + 1 message from p y to p i carries f y [L i ], it follows that f i [L i ] contains f i [L i -1] ∪ {p z }. Consequently, |f i [L i ]| > |f i [L i -1]|. It follows that h i (L i + 1) ≤ h i (L i )
, contradicting the definition of L i . • Case 2: p i does not receive a message from p y in round L i + 1.

In that case, both p z and p y are seen faulty for the first time by p i during the round

L i + 1. So, f i [L i + 1] contains f i [L i -1] ∪ {p y , p z }. Since f i [L i + 1] (computed by p i during the round L i + 2) contains f i [L i + 1], we have |f i [L i + 1]| ≥ |f i [L i -1]| + 2
. Thus, we have

h i (L i + 2) = (L i + 2) + t -|f i [L i + 1]|, ≤ (L i + 2) + t -(|f i [L i -1]| + 2), = L i + t -|f i [L i -1]|, = h i (L i ),
BH i = bh i [ ] = min(bh i [ -1], h i ( )) = h i ( ) ≥ , i.
e., BH i ≥ , which establishes the result. It follows that p i decides no later than round t + 1.

Simultaneous decision for the correct processes. We first show that no two correct processes p i and p j decide at distinct rounds. Due to the algorithm, if p i and p j decide, they decide at round BH i and BH j , respectively. We show that BH i = BH j . Due to Lemma 4, the round L i is clean. Hence, during the round L i , p j receives the same messages that p i receives (Property 1). Thus

f i [L i -1] = f j [L i -1] and consequently, h i (L i ) = h j (L i ). Since bh j [L i ] ≤ h j (L i ) by line 09, it follows that bh j [L i ] ≤ bh i [L i ] = BH i ,
and thus BH j ≤ BH i . By symmetry the same reasoning yields BH i ≤ BH j , from which it follows that BH i = BH j . This proves that no two correct processes decide at distinct rounds. 4Simultaneous decision for the faulty processes. BH being the round at which the correct processes decide, let us now consider the case of a faulty process p j . As p j behaves as a correct process until it crashes, and as the correct processes decide in the same round BH , it follows that no faulty process decides before BH , and if p j executes line 210 of round BH , it does decide as if it was a correct process.

Data agreement property. The fact that no two processes decide different values comes from the existence of the clean round L i that appears before a process decision. During that round, all the processes that are alive at the end of this round have received the same set of estimate values (Property 1), and selected the smallest of them. It follows that, from the end of that round, there is a single estimate value in the system, which proves the data agreement property.

2 Lemma 5

Theorem 5 Let t < n. The algorithm described in Figure 2 solves the consensus problem with simultaneous decision. In a run with failure pattern F , decision is reached in round t + 1 -D where D = D(F ) is the waste inherent in F .

Proof

The proof of the validity, decision, simultaneous decision and data agreement properties follow from the Lemmas 2 and 5. We now show that the decision is obtained in round t + 1 -D. Let us consider an arbitrary run of the algorithm. It follows from Lemma 5 that BH i = BH j for any pair of processes p i and p j that decide. Let BH denote this round. The proof of the claim amounts to showing that BH ≤ t + 1 -D and BH ≥ t + 1 -D.

Let p i be a process that decides and R the last round such that

|C[R]| -R = D (i.e., |C[R + x]| -(R + x) < D = |C[R]| -R, for any x > 0)
. Let us observe that, due to the lines 208-210 of the algorithm, BH is attained at the round numbers that make the function h i () minimal. Moreover, it follows from the definition of D and R that

|C[R + 1]| ≤ |C[R]|. Since C[R] ⊆ C[R + 1], it follows that C[R] = C[R + 1], i.e., no new process failure is discovered in round R + 1, so the round R + 1 is clean and we have |f i [R]| = |C[R]|. Due to line 208 of the round R + 1, we have h i (R + 1) = R + t + 1 -|f i [R]| = (t + 1) -(|f i [R]| -R) = t + 1 -D, from which we conclude BH ≤ t + 1 -D.
For the other direction, let us recall that, due to Lemma 4, the round

L i > 0 is clean. It follows that f i [L i -1] = C[L i -1], since any p i hears in round L i from all processes that survived round L i -1. Therefore, BH = t + 1 - (|f i [L i -1]| -(L i -1)) = t + 1 -(|C[L i -1]| -(L i -1)) = t + 1 -d (Li-1) ≥ t + 1 -D, which completes the proof of the theorem. 2 T heorem 5
C On the optimality of the algorithm:

t + 1 -min(D, δ) is a

lower bound

This part is an essential part of the paper: it proves that the algorithm described in Section 3.4 (called PROPOSE in the following) is optimal, namely, in a synchronous system prone to up to t process crashes (with t < n -1), there is no deterministic algorithm that can ever solve the simultaneous condition-based consensus problem in fewer than (t + 1) -max(D, δ) rounds. The proof relies on notions introduced in [START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Mizrahi | Continuous Consensus via Common Knowledge[END_REF][START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. It also uses notations introduced in Section 3.3. The problem of simultaneous consensus is closely related to the knowledge-theoretic notion of similarity among runs at a given time. This notion is captured by the following definitions. For later use, these definitions are made with respect to an arbitrary round-based synchronous deterministic algorithm P (they consequently apply in particular to the PROPOSE algorithm).

C.1 Preliminary definitions and lemmas

For ease of exposition, the runs of an arbitrary deterministic algorithm P are denoted by σ, σ , etc. S[r, σ] denotes the set of processes that survive round r of σ, while ls(p, r, σ) denotes the local state of p at the end of r in the run σ (i.e., its set of local variables and their current values). Definition 4 Given a deterministic algorithm P , a process p, and a round r, the runs σ and σ of P are indistinguishable to p after round r (denoted

σ r ∼ p σ ) if both (i) p ∈ S[r, σ] ∩ S[r,
σ ] (i.e., p has survived round r in both runs), and (ii) ls(p, r, σ) = ls(p, r, σ ).

Definition 5

The runs σ and σ are connected at the end of round r, denoted σ r ≈ σ , if there is a sequence of runs and processes such that

σ = σ 0 r ∼ p0 σ 1 r ∼ p1 • • • r ∼ p k-1 σ k = σ .
In other words, an undirected graph G(P, r) (in short G(r)) can be associated with each round r of a protocol P . This graph is called P 's similarity graph for round r. Its vertices are the runs of P and there is an edge connecting Irisa Observe that a deterministic algorithm P , an initial configuration I (set of initial values), and a failure pattern F determine a run σ = P (I, F ) of P . Definition 6 A run σ of P corresponds to a run ρ of an algorithm P if, for some initial configuration I and failure pattern F , it is the case that σ = P (I, F ) and ρ = P (I, F ).

The next lemma captures, in a precise sense, the fact that the connected components of the similarity graph for FIP refine those of any other deterministic algorithm. 6 This lemma is from [START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. For completeness, its proof is given in appendix D.

Lemma 7

Let P be a deterministic algorithm for simultaneous consensus. Let us assume that the runs σ and σ of P correspond to the runs ρ and ρ of FIP, respectively. Then (i) if ρ r ∼ q ρ then σ r ∼ q σ , and

(ii) if ρ r ≈ ρ then σ r ≈ σ .
On failure patterns and full-information algorithms Observe that in both the FIP and PROPOSE algorithms, a correct process is required to send a message to each process in every round. As a result, in runs of both FIP and PROPOSE, a process p knows by the end of round r that q has crashed if the failure pattern F is such that q has crashed before it sent its round r message to p.

The set f i [r] of the processes that r has not heard from in round r can be directly computed from the local state in FIP as {p j | Inp i [j] = ⊥}. Since p i sends Inp i to all other processes, the set f i [r -1] of processes that p i knows at r to have been discovered as crashed by round r -1 is thus easily computed from the messages it receives in round r. Since for corresponding runs of FIP and PROPOSE these sets coincide (in fact, their values depend only on the failure pattern), we find it convenient to talk about the values of

f i [r, F ], f i [r, F ], C[r, F ], D[F ],
etc. for runs of FIP as well.

Since the Validity property states that it is illegal to decide v in a run that does not contain v as one of its initial values, Corollary 1 implies that it is impossible to decide on v as long as there is a connected run that does not contain v as one of its initial values. In light of this, we can now show that the algorithm FIP reaches a decision as soon as it possibly can.

C.3 Premature rounds

It has been shown in Theorem 5 that the algorithm PROPOSE decides on a value in round BH = t + 1 -D. Let BH (ρ) denote the value of the round number BH of the the run ρ = PROPOSE(I, F ). Recall that the value of BH is solely a function of ρ's failure pattern F (and not of the initial configuration).

Definition 7 A round is premature 7 in F if < t + 1 -D = BH (ρ) for every run ρ = PROPOSE(I, F ).

As h i (r + 1) = r + (t + 1 -|f i [r]|), and h i (r + 1) ≥ BH (ρ), this means that, for every r such that r + 1 ≤ , the property r + t + 1 -|C[r, F ]| > holds. Notice that the failure pattern F that occurs during the run ρ determines whether or not is premature: In all runs of PROPOSE with the same F the sets f i [r, F ] and C[r, F ] are the same for every i and r, and so are D and BH . Lemma 8 Let t < n -1, ≥ 0, ρ = FIP(I, F ) and ρ = FIP(I, F ). If ρ ≈ ρ then is premature in F iff is premature in F .

Proof Let ρ = FIP(I, F ) and ρ = FIP(I , F ). As in the proof of item (ii) of Lemma 7, it suffices to show that, for all q, if ρ ∼ q ρ then is premature in F iff is premature in F . Thus, let us assume that ρ ∼ q ρ . Let σ = PROPOSE(I, F ) and σ = PROPOSE(I , F ) be the runs of PROPOSE corresponding to the runs ρ = FIP(I, F ) and ρ = FIP(I , F ), respectively. By item (ii) of Lemma 7, it follows that σ ∼ q σ . Round is premature in F iff BH (σ) > , which by Theorem 5 implies that q does not decide in σ by the end of round . Thus, since the if test on line 114* of PROPOSE fails, decided q = false continues to hold in σ. The fact that σ ∼ q σ implies that decided q = false holds at the end of the 6 In the sequel, we interpret r ∼ and r ≈ among runs of an algorithm P in terms of the similarity graph G(r, P ) defined on the runs of P . Thus, the interpretation of r ∼ and r ≈ in statements such as that of Lemma 7 is always with respect to the algorithm generating the related runs. 7 This is short for premature for simultaneous consensus, a term that will be justified by the technical analysis in this section. Irisa rounds where no process crashes in round k + 1. We then use the inductive assumption again to show that ρ ≈ ρ q,k , and obtain by transitivity that ρ ≈ ρ q,k , as desired.

Let ρ be a run that coincides with ρ for the first k rounds where no process crashes in round k + 1, and process p n is silent from round k + 2 on. We show that ρ ≈ ρ . Define ρ 1 , . . . , ρ n where n = |Π| to be runs such that in ρ j the first k rounds are identical to ρ, process p j is silent from round k + 2 on, no process other than (possibly) p j fails in rounds k + 2, . . . , , and no new failure in round k + 1 is seen by processes p 1 , . . . , p j . Denoting ρ = ρ 0 , we prove by induction on j that ρ ≈ ρ j . The case j = 0 is immediate, since ρ 0 = ρ. Let j > 0 and assume inductively that ρ ≈ ρ j-1 . Since is premature in F = F (ρ), it follows from Lemma 8 that is premature in ρ j-1 . By the inductive assumption for k + 1 we have that ρ j-1 ≈ ρ, where ρ = (ρ j-1 ) pj ,k+1 . In particular, Lemma 9 implies that there are at most t failures in ρ. Observe that (i) p j is silent from round k + 2 in ρ, (ii) every process other than p j has the same local state at the end of round k in both ρ and ρ j , (iii) the same messages are sent in both runs from round k + 2 on, and (iv) since no more processes fail in ρ j than do in ρ, there are at most t failures in ρ j . It thus follows that ρ ≈ ρ j .

Moreover, since ρ ≈ ρ j-1 ≈ ρ ≈ ρ j , we have by transitivity of ≈ that ρ ≈ ρ j , completing the inductive step. We conclude that ρ ≈ ρ n = ρ , as claimed. Notice that since ρ ≈ ρ and is premature in ρ it follows that is also premature in ρ . Our goal now is to "silence" process q from round k + 1 on. Let ρ = FIP(I, F ) where F agrees with the pattern F of ρ on everything, except that in F process q is silent from round k + 2 on. Thus, in ρ the first k rounds are identical to ρ, no process fails in round k + 1, and processes p n and q are silent from round k + 2 on. We first claim that at most t processes fail in F . Since is premature in ρ we have that t + 1 -D(F ) > and hence t -D ≥ . Let h be the number of process failures up to round k, inclusive, in ρ (and hence also in ρ ). Since no failures are detected in round k + 1 of ρ we have that

d k = h -k. As D ≥ d k we have that t -(h -k) ≥ . It follows that t -h ≥ -k = s ≥ 2.
We conclude that t ≥ h + 2. The claim now follows since, by definition, F contains at most h + 2 failures, and we have just shown that h + 2 ≤ t.

The values of d 1 , . . . , d k , d k+1 (defined in Definition 3) are the same in ρ and in ρ . Since no failure is detected in round k + 1 of either, we have that

d k+1 = d k -1. In ρ we have that d k+2 = d k and d k < d k+2 for all rounds k > k+2. It follows that D(F ) = D(F ). Since is premature in ρ we have that t+1-D(F ) = t+1-D(F ) > ,
and is premature in ρ as well. Observe that ρ = ρ pn,k+1 . By the inductive hypothesis for k+1 we have that ρ ≈ ρ . Let ρ = FIP(I, F ), where F differs from F only in that p n does not receive a message from q in round k + 1. Let p ∈ S[ , F ] = S[ , F ]. Since p n is silenced from round k + 2 ≤ in ρ and in F , we have that ρ ∼ p ρ and thus ρ ≈ ρ ≈ ρ. Now define runs σ 1 , . . . , σ n-1 , σ n where σ j coincides with ρ on the first k rounds, no process other than q fails in round k + 1, in round k + 1 processes p j , . . . , p n do not receive a message from q, (p 1 , . . . , p j-1 receive round k + 1 messages from q iff they do so in ρ), and process p j is silent from round k + 2 on. Notice that ρ = σ n . An inductive proof identical to the one for ρ 1 , . . . , ρ n above (this time moving down from σ n to σ 1 ) shows that ρ ≈ σ 1 . In σ 1 process q is silenced from round k + 1 on, since no process receives a message from it in this round. Moreover, it is easy to check that σ 1 q,k = ρ q,k . Since is premature inσ 1 we obtain that ρ ≈ σ 1 ≈ σ 1 q,k = ρ q,k , and we are done. Irisa Proof Denote by s the distance between I and I in G x (C, E x ). Notice that 0 ≤ s < ∞ (because by assumption I is connected to I in G x (C, E x ), and so there is a finite path connecting I to I ). We prove the claim by induction on s.

The base case is s = 0, for which the claim trivially holds for the choice ρ = ρ since we have then I = I , F = F , and because t < n guarantees that ρ ≈ ρ for all runs.

For the inductive step, let s > 0 and assume that the claim holds for all runs with shortest G x (C, E x ) distance s -1 to I . Since the distance between I and I is s > 0, there is an initial vector I whose distance from I in G x (C, E x ) is 1 and whose distance from I is s -1. We first claim that ρ ≈ ρ for a run of the form ρ = FIP( I, F ). Let T = {q 1 , . . . , q x } be a set of processes such that process p's initial value is the same in I and in I for all p ∈ Π \ T . Denote by ρ 1 the run ρ 1 = FIP(I, F q1,0 ), which has initial vector I and in which q 1 crashes in round 0, , and no other process fails.

Since, by assumption, is premature in ρ = ρ 0 , we have by Lemma 10 that ρ ≈ FIP(I, F q1 ,0 ) = ρ 1 . Let F x be the failure pattern, and ρ x the associated run, in which the x processes in T are silent from the start, and no other process fails. It is easy to check that D(ρ x ) = x -1 since d r (ρ x ≤ x -1 for all rounds r ≥ 0. Thus, t + 1 -D = t + 2 -x in ρ x . Since, by assumption, ≤ t + 1 -x, we have that is premature in ρ x . Notice that F x q1,0 = F q1 ,0 . Thus, using again Lemma 10, we have that ρ x ≈ FIP(I, F q1,0 ) = ρ 1 . By symmetry and transitivity of ≈ it follows that ρ ≈ ρ x . Define ρ = FIP( I, F x ). By assumption, I ∈ C, and so ρ is a run of FIP under condition C. Since t < n we have that F x contains at least one correct process, which we denote w.l.o.g by p. Because ρ x and ρ differ only in the initial values of processes in T that are silent throughout F x , and since p ∈ S[ρ x , ] ∩ S[ ρ, ], we have that ρ x ∼ p ρ. It follows that ρ x ≈ ρ. Since ρ ≈ ρ x we have by transitivity of ≈ that ρ ≈ ρ.

Finally, since the distance between I and I in G x is s -1, we have by the inductive hypothesis that ρ ≈ ρ for some run ρ of the form ρ = FIP(I , F ). As we have shown, ρ ≈ ρ, and it follows by transitivity of ≈ that ρ ≈ ρ , which completes the inductive step. This completes the inductive step for s, and the lemma follows.

2 Lemma 11

The next corollary follows directly from Lemma 11.

Corollary 2 Let t < n -1 and let C be a legal x-coverable condition. Let ρ = FIP(I, F ), where I ∈ C, is premature in F , and ≤ t + 1 -x. Assume that I is connected in G x to both the input vector I v = (v, . . . , v) and the input vector vector I w = (w, . . . , w). Then, ρ v ≈ ρ ≈ ρ w , where ρ v and ρ w are runs of FIP with input vectors I v and I w , respectively.

Finally, the next theorem follows from the previous corollary.

Theorem [START_REF] Garg | Elements of Distributed Computing[END_REF] Let P be a deterministic algorithm solving simultaneous condition-based consensus for condition C. Assume that C is x-coverable. Then, in no run of P can decision be reached before round RS t,d,F = min(t + 1 -D, t + 1 -x).

D Proof of Lemma 7

Lemma 7 Let P be a deterministic algorithm for simultaneous consensus. Let us assume that the runs σ and σ of P correspond to the runs ρ and ρ of FIP, respectively. Then (i) if ρ r ∼ q ρ then σ r ∼ q σ , and

(ii) if ρ r ≈ ρ then σ r ≈ σ .
Proof Let us consider the runs σ and σ of P and the corresponding runs ρ and ρ of FIP. Since r ≈ is the transitive closure of the relations { r ∼ p } p∈Π , claim (ii) follows from (i). Consequently, it suffices to prove claim (i). Let us observe that, due to the definition of "corresponds to", the fact that σ corresponds to ρ implies that S[r, σ] = S[r, ρ] for all rounds r. The proof that ρ r ∼ q ρ ⇒ σ r ∼ q σ , is by induction on r.

Base case. For the base case, let us consider the initial configuration that corresponds to the fictitious round r = 0. Since the initial state of each process (under P as well as under FIP) is fully determined by its initial value, the fact that ρ 0 ∼ q ρ implies that q has the same initial state in both. Since σ corresponds to ρ and σ corresponds to ρ , it PI n ˚1898 20 Y. Moses & M. Raynal follows that q has the same initial value in σ and σ , and so σ 0 ∼ q σ . Induction case: r > 0. Let us assume that item (i) holds for every process at round r -1 (induction assumption). Moreover, let us assume that ρ r ∼ q ρ . As before, σ and σ correspond to ρ and ρ , respectively. We need to show that σ r ∼ q σ . Since q survives round r in both the runs ρ and ρ , and as this depends only on their failure patterns F and F , which are also the failure patterns in σ and σ , respectively, we have q ∈ S[r, σ] ∩ S[r, σ ]. Let us recall that the local state of a process q at the end of a round r of a run σ of a deterministic algorithm such as P (namely, the local state ls(q, r, σ)) is a function of its local state in round r -1 (ls(q, r -1, σ)) and the messages that it receives in round r. We have to show that the local states ls(q, r, σ) and ls(q, r, σ ) are the same.

Since ρ r ∼ q ρ , it follows that the arrays Inp q are the same in both the runs ρ and ρ at the end of round r. So, Inp q [q] in both runs have the same value at the end of r; let X be that value.

The fact that q survives round r in both ρ and ρ means, in particular, that it receives its own round r message sent at line 04 of FIP in both ρ and ρ . The value of this message in ρ is ls(q, r -1, ρ) which is the value of Inp q [q] at the end of r, i.e., ls(q, r -1, ρ) = X. A similar reasoning shows that ls(q, r -1, ρ ) = X. It follows from ls(q, r -1, ρ) = ls(q, r -1, ρ ) = X that ρ r-1 ∼ q ρ and by the inductive hypothesis we obtain σ r-1 ∼ q σ . Consequently, q has the same local state at the end of round r-1 in both σ and σ , i.e., ls(q, r-1, σ) = ls(q, r-1, σ ).

It remains to show that q receives exactly the same messages during round r in both σ and σ . Suppose that q receives message µ from process q in round r of σ. It follows from the failure pattern F that the message sent by q to q during round r is received by q. Since ρ corresponds to σ and in FIP process q sends messages to all processes in every round, we have that q receives a message from q in round r of ρ as well. As above (case of the message that, at each round, a process sends to itself), this message in ρ contains ls( q, r -1, ρ) (the local state of q at round r -1 of the run ρ). From ρ r ∼ q ρ we have that q receives the same message from q in ρ . As a result, we have that ρ r-1 ∼ q ρ , and by the inductive assumption for r -1 and q we obtain that σ r-1 ∼ q σ . Since the message µ is determined by P as a function of the local state of q at r -1 in σ, we have that the same message µ is also sent by q to q in round r of σ . As the round r message sent by q to q in ρ is received by q, and σ corresponds to ρ , we obtain that q receives µ from q in σ as well. It follows that every message received by q in round r of σ is received by it in the same round of σ . By symmetry, the messages received in σ are also received in σ. Finally, since q has the same local state in round r -1 of σ and σ (namely, ls(q, r -1, σ) = ls(q, r -1, σ )), and receives the same messages in round r of both σ and σ , we obtain that σ r ∼ q σ , which concludes the proof of the lemma.

2 Lemma 7

Irisa

Figure 1 :

 1 Figure 1: A synchronous condition-based simultaneous consensus algorithm (code for p i )

Figure 2 : 3 . 3 Definition 3

 2333 Figure 2: Optimal simultaneous consensus despite up to t crash failures (code for p i )

2 10 C. 4 Definition 12 Lemma 11

 21041211 Lemma Optimality of the proposed algorithm Definition 11 C being a legal condition, let the x-graph over C be the graph G x = (C, E x ) where E x = {(I, I ) : dist(I, I ) ≤x. The condition C is x-coverable if for every vector I ∈ C there are at least two values v, w ∈ V such that there are paths in G x from I to both the input vector I v = (v, v, • • • , v) and the input vector I w = (w, . . . , w). Let t < n -1 and let ρ = FIP(I, F ). Let C be a legal condition such that I, I ∈ C, where I is connected in G x (C) to I . If is a premature round in F and ≤ t + 1 -x, then there is a run ρ = FIP(I , F ), such that ρ ≈ ρ .

  represents the best (smallest) horizon value known by p i at round r. It is p i 's best estimate of the smallest round for a simultaneous decision. Initially, bh i

Let us recall that the actual number of failures f (0 ≤ f ≤ t) is only a digest of the failure pattern. It does not state at which rounds the failures do occur, and which are the processes that received the round r message from a process that crashed during round r.Irisa

PI n ˚1898

The algorithm described in[START_REF] Mostéfaoui | Synchronous Condition-Based Consensus[END_REF] works be the input vector in the condition or not. When the input vector I belongs to the condition C, a process decides in two rounds if f ≤ td, and in at most d + 1 rounds when f > td. When the input vector is not in the condition a process decides in at most t + 1 rounds.PI n ˚1898

A close look at the base algorithms shows that their variables v nocond i and est i play the same role. Consequently, only of them has to be kept in the combined algorithm.Irisa

In[START_REF] Dwork | Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[END_REF][START_REF] Halpern | Knowledge and Common Knowledge in a Distributed Environment[END_REF] it is shown that before performing such a simultaneous action the processes must attain common knowledge that they are doing so. In particular, they must have common knowledge that the decided value v is one of the initial values in the run.PI n ˚1898

The proof of some lemmas that follow uses the fictitious round r = 0. This motivates the definition C[-1, F ] = C[r, F ] = 0 introduced in connection with Definition 3. This allows us to define failure patterns and associated runs in which "we crash" a priori a given process q, without being bothered by the processes that crash in the first round of F before they send their round 1 messages.PI n ˚1898

σ and σ if there is a process q such that σ r ∼ q σ . It is easy to see that σ r ≈ σ holds if σ and σ belong to the same connected component in G(r). Because G(r) is undirected, being connected ( r ≈) is an equivalence relation. 5 Moreover, observe that if we can show that some property A is maintained under r ∼ q for all q ∈ Π, then whenever σ has property A and σ r ≈ σ , we are guaranteed that σ has property A as well.

Lemma 6 Let σ and σ be runs of a deterministic algorithm P that solves simultaneous consensus. If some process decides on value v in round r of σ and σ r ≈ σ, then the processes in S[r, σ ] decide the same value v in the same round r of σ .

Proof It suffices to show the claim for any two runs σ, σ such that σ r ∼ q σ for some q ∈ S[r, σ] ∩ S[r, σ ]. In this case, q decides v in round r of σ. Because P is deterministic and q has the same local state at the end of round r of σ and σ , q decides v at the end of round r in σ . Finally, as P solves simultaneous consensus (lemma assumption) it follows that all processes in S[r, σ ] decide v in round r (and no other process decides a different value in a different round).

2 Lemma 6

An immediate consequence of Lemma 6 is captured by the following corollary.

C.2 A full-information algorithm

For the purpose of proving optimality, we make use of a full-information algorithm, denoted FIP and described in Figure 3.

The algorithm In the first round, each process sends its initial value v i to all processes (including to itself). The algorithm then constructs an array Inp i [1.

.n] containing the incoming message from each of the processes (itself included). If p i does not receive a message from p j then it sets Inp i [j] to the default value ⊥. In each of the later rounds, every process p i first sends Inp i to all others, and then uses the incoming messages of the current round to construct an updated array Inp i in the same way as in the first round. The local state of the process at the end of round r is identified simply with the contents of its array Inp i . This algorithm is introduced in order to establish, for each failure pattern F , times at which simultaneous consensus cannot be attained by any algorithm whatsoever. Optimality will then be established by showing that the PROPOSE algorithm decides as soon as possible, for each and every possible failure pattern (and initial configuration). Figure 3: The full-information algorithm FIP (code for p i ) 5 In the knowledge terminology, process q knows a fact A at the end of round r in σ if it is true of all runs σ satisfying σ r ∼q σ; it is common knowledge there if A holds at all runs σ r ≈ σ. Thus, the set of runs connected to σ determines what is common knowledge in σ at the end of round r.

PI n ˚1898

round of σ as well. It follows that BH (σ ) > , and consequently is premature at F , as desired. The 'only-if' direction of the lemma is obtained by a symmetric argument.

2 Lemma 8

Definition 8 A process is silent in a round r of a run ρ if it has crashed before sending its round r messages.

Definition 9 Given a failure pattern F , a process q and a round r, let F q,r be the failure pattern that satisfies the following four conditions: (i) F q,r coincides with F for the first r -1 rounds, (ii) in round r exactly the failures detected in C[r, F ] occur in F q,r , (iii) process q is silent from round r + 1 on, and (iv) no process other than q fails after round r.

Let us remark that if the first k rounds of both F and F are the same, then F q,k = F q,k . Since the rounds r ≤ 0 of all failure patterns are the same, we have that F q,0 = F q,0 for all F and F . 8 Indeed, F q,0 is the failure pattern in which process q is silent and sends no messages whatsoever, while no other process crashes. In runs with such a pattern, the execution cannot depend on q's initial value.

Lemma 9

If is premature in F and k < , then no more than t processes crash in F q,k .

Definition 10 Given a run ρ = FIP(I, F ), let ρ q,k be the run ρ q,k = FIP(I, F q,k ).

Let us notice that, due to Lemma 9, if ρ is a run of FIP in which at most t processes fail, then so is ρ q,k .

The following lemma is from [START_REF] Moses | Revisiting Simultaneous Consensus with Crash Failures[END_REF]. Its states an equivalence on classes of runs that is used to prove optimality (see Lemma 11 in the next section).

Lemma 10 Let t < n -1 and fix > 0. Moreover, let ρ = FIP(I, F ) and let q ∈ Π. If is premature in F , then ρ ≈ ρ q,k for all k satisfying 0 ≤ k ≤ -1.

Proof Let > 0. We prove the lemma for all runs ρ, by induction on s = -k. For the base case, assume that s = 1, and so k = -1. Choose q ∈ Π, and let p ∈ S[ , ρ]. Since is premature in ρ, we have h p ( ) = ( -

\ {p} (such a process p is guaranteed to exist since by assumption t ≤ n -2).

Let ρ be the run that is identical to ρ up to and including round -1, where in round process p receives the same messages as in ρ, but process p (who is non-faulty in ρ too) receives messages from all processes in Π \ f p [ -1, F ]. Finally, no process other than those in f p [ -1, F ] fails in ρ . There are exactly |f p [ -1, F ]| < t failures in ρ and p ∈ S[ , ρ ] has the same local state at the end of round in both ρ and ρ . Hence, we have ρ ∼ p ρ .

If q is silent in round in ρ then we are done. Otherwise, let ρ be a run that is the same as ρ except that q crashes in round by not sending a round message to p. At most |f p [ -1, F ]| + 1 ≤ t -1 + 1 = t processes fail in ρ , and p has the same state in ρ as in ρ . Hence, ρ ∼ p ρ . Finally, observe that ρ q, -1 is identical to ρ except that q is silent in round . Process p does not distinguish ρ from ρ q, -1 since in both it receives the same messages in round . Thus, ρ ∼ p ρ q, -1 , and by definition of ≈ we have that ρ ≈ ρ q, -1 , completing the base case. Induction step. Let s = -k > 1 and assume that the claim holds for round s -1 (i.e., round k + 1) in all runs in which is premature. We prove the claim for round k. Let ρ be a run in which is premature, and choose an arbitrary process q ∈ Π. We will use the inductive assumption to find a connected run ρ that coincides with ρ for the first k