F Bonnet

M Raynal
email: raynal@irisa.fr

CONDITIONS FOR SET AGREEMENT WITH AN APPLICATION TO SYNCHRONOUS SYSTEMS

Keywords: Agreement problem, Condition, Crash failure, Distributed algorithm, Efficiency, Fault-tolerance, Input vector, Lower bound, Round-based computation, Set agreement, Synchronous system Accord ensembliste, condition

The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. While this problem cannot be solved in an asynchronous system prone to t process crashes when t k, it can always be solved in a synchronous system; b t k c + 1 is then a lower bound on the number of rounds (consecutive communication steps) for the non-faulty processes to decide. The condition-based approach has been introduced in the consensus context. Its aim was to both circumvent the consensus impossibility in asynchronous systems, and allow for more efficient consensus algorithms in synchronous systems. This paper addresses the condition-based approach in the context of the k-set agreement problem. It has two main contributions.

The first is the definition of a framework that allows defining conditions suited to the `-set agreement problem.

More precisely, a condition is defined as a set of input vectors such that each of its input vectors can be seen as "encoding" `values, namely, the values that can be decided from that vector. A condition is characterized by the parameters t, `, and a parameter denoted d such that the greater d + `, the least constraining the condition (i.e., it includes more and more input vectors when d + `increases, and there is a condition that includes all the input vectors when d + `> t ). The conditions characterized by the triple of parameters t, d and `define the class of conditions denoted S d t , 0 d t, 1 ` n ; 1. The properties of the sets S d t are investigated, and it is shown that they have a lattice structure.

The second contribution is a generic synchronous k-set agreement algorithm based on a condition C 2 S d t , i.e., a condition suited to the `-set agreement problem, for ` k. This algorithm requires at most d;1+k + 1 rounds when the input vector belongs to C, and t k + 1 rounds otherwise. (Interestingly, this algorithm includes as particular cases the classical synchronous k-set agreement algorithm that requires t k + 1 rounds (case d = t and `= 1 ), and the synchronous consensus condition-based algorithm that terminates in d + 1 rounds when the input vector belongs to the condition, and in t + 1 rounds otherwise (case k = `= 1 ).)

I R I S A

Context of the paper

The consensus problem and the condition-based approach The condition-based approach has been introduced to circumvent the impossibility of solving the consensus problem in asynchronous systems prone to process crashes. That problem can be stated as follows. Each process proposes a value, and the processes have to cooperate in such a way that each non-faulty process decides a value (termination), a decided value is a proposed value (validity), and no two processes decide different values (agreement). Consensus is a fundamental problem that lies at the core of nearly all the distributed coordination or consistency problems encountered in fault-tolerant distributed computing. Despite its very simple definition, it is surprising that this problem cannot be solved in asynchronous systems prone to process crashes (even in presence of a single crash), be the underlying communication medium a reliable message passing system [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF] or a shared memory made up of read/write registers [START_REF] Loui | Memory Requirements for Agreement Among Unreliable Asynchronous Processes[END_REF].

Given a problem, the condition-based approach analyzes restrictions of the problem to subsets of its inputs [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]. Each restriction defines a new problem that is a particular instance of the original problem. Conditions have given rise to two lines of research, one focused on decidability, the other on efficiency. More precisely, it addresses the two following questions.

• Given an unsolvable problem (e.g., asynchronous consensus), for what restrictions on its inputs does the problem become solvable? • Given a solvable problem (e.g., synchronous consensus), for what restrictions on its inputs does the problem become easier to solve (i.e., solvable in a more efficient way)?

Up to now, nearly all the results of the condition-based approach concerns the consensus problem (see e.g., [START_REF] Friedman | Asynchronous Agreement and its Relation with Error-Correcting Codes[END_REF][START_REF] Izumi | Condition Adaptation in Synchronous Consensus[END_REF][START_REF] Izumi | A Weakly Adaptive Condition-based Consensus Algorithm in Asynchronous Distributed Systems[END_REF][START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF][START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF][START_REF] Mostefaoui | Condition-based Consensus Solvability: a Hierarchy of Conditions and Efficient Protocols[END_REF][START_REF] Zibin | Condition-Based Consensus in Synchronous Systems[END_REF]). Let an input vector be a vector with one entry per process, the entry associated with a given process containing the value proposed by that process. Each input vector can be seen as a codeword encoding one of its values, namely, the value decided by the non-faulty processes [START_REF] Friedman | Asynchronous Agreement and its Relation with Error-Correcting Codes[END_REF]. A condition is a set of input vectors (codewords). In this context, the asynchronous consensus impossibility can be restated as follows: no condition can contain all the possible input vectors. So, one of the most fundamental question of the condition-based approach is the characterization of the largest set of conditions that allows to solve the consensus problem in a crash-prone asynchronous system. This question has been answered in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] where is introduced the notion of x-legal condition and is proved the following characterization: a condition C allows to solve consensus in an asynchronous system prone to up to x process crashes iff it is x-legal [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] (a condition is x-legal if each of its input vectors contains the same value more than x times, and the Hamming distance of two vectors from which different values can be decided is greater than x).

Condition-based synchronous consensus

The consensus problem can be solved in a synchronous system prone to any number of process crashes. In such systems, the time efficiency of an algorithm is measured in terms of the number R of rounds (consecutive communication steps) needed for the non-faulty processes to decide. It has been shown that t + 1 is a lower bound for R where t is an upper bound on the number of faulty processes [START_REF] Aguilera | A Simple Bivalency Proof that t-Resilient Consensus Requires t + 1 Rounds[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF].

As shown in [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF][START_REF] Zibin | Condition-Based Consensus in Synchronous Systems[END_REF], the condition-based approach allows bypassing that lower bound each time the input vector belongs to the condition. Families of conditions, denoted ; S d t 0 d t , are introduced in [22]; the parameter d is called the degree of the condition (and the quantity (t;d) measures the difficulty of the condition). A condition C belongs to

S d t if it is (t ; d)-legal.
The following hierarchy of sets of conditions for synchronous consensus has been established in [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF]:

S 0 t S 1 t S d t S t t :
Let us consider a synchronous system where up to t processes can crash, a condition C 2 S d t and an input vector I.

The main result of [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF] is the following. if I 2 C, consensus can be solved in two rounds when d = 0 , and in d + 1

rounds when 1 d t. When I = 2 C, the number of rounds is t + 1 rounds (as already known). That paper also proves that d + 1 is a tight lower bound for R, when the input vector belong to C (with C 2 S d

t and C = 2 S d;1 t ).
It is worthwhile looking at the "extreme" sets S 0 t and S t t . One 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. As far as consensus is concerned, this establishes a simple and well-defined borderline relating efficiency in synchronous systems and computability in asynchronous systems.

PI n ˚1870

Set agreement The k-set agreement problem has been introduced to investigate how the number of choices (k) allowed to the processes is related to the maximum number (t) of processes that can crash [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF]. More precisely, the processes are allowed to decide up to k different values (consensus is 1-set agreement). While that problem can be trivially solved in asynchronous systems where k > t , it has no solution in these systems as soon as k t [START_REF] Borowsky | Generalized FLP Impossibility Results 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]. The situation is different in synchronous systems where the k-set agreement problem can always be solved, whatever the values of t and k. In these systems, the lower bound on the number of rounds is R = b t k c + 1 [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF].

Few works have considered the condition-based approach for solving the k-set agreement problem. A topologybased characterization of the conditions that allow to wait-free solve the (n ; 1)-set agreement problem is presented in [START_REF] Attiya | Wait-Free n-Set Consensus when Inputs are Restricted[END_REF] (wait-free means that the only value of t that is considered is t = n ; 1). Condition-based asynchronous shared memory k-set agreement algorithms are presented in [START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF] (without characterizing conditions suited to k-set agreement). An asynchronous shared memory algorithm is presented in [START_REF] Mostefaoui | The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement[END_REF] 1 . Assuming that the input vector I belongs to a condition C 2 S d t , that algorithm solves the k-set agreement problem for k = d + 1 . That algorithm can trivially be transformed in a one-round synchronous algorithm. (It is also shown in [START_REF] Mostefaoui | The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement[END_REF] that, for k d, there is no k-set agreement algorithm when C 2 S d t and C = 2 S d;1 t .)

Motivation and content of the paper

This paper is on the condition-based approach for solving the k-set agreement problem. It originates from the following observations and associated questions. This issue was the initial question this paper originated from. The paper answers it by presenting a condition-based algorithm for the generic pair (k b d k c + 1 ) . This means that if the algorithm stops after r rounds, the processes decide on at most k values where k is the smallest integer such that b d k c + 1 r.

A question on the dividing power of conditions in synchronous systems

Interestingly, this generalizes to conditions the fact that, when we go from synchronous consensus to synchronous k-set agreement, the time complexity is always divided by k. This was not a priori evident, as the bound b t k c + 1 is purely "syntactic" (it is only based on the worst failure pattern), while the condition-based approach is more "semantic" (it is based on the actual input values).

From smaller conditions for consensus to larger conditions for set agreement The set of conditions ; S d t 0 d t have been designed with the consensus problem in mind. This means that, for any C 2 S d t , each input vector I 2 C is seen as "encoding" a single value, namely, the value decided when the input vector is I. As we have just seen [START_REF] Mostefaoui | The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement[END_REF][START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF], such a consensus condition C can be used to solve the k-set agreement with a round complexity (b d k c+ 1 ) smaller than the one required for solving consensus (d + 1 ). This can be seen as a simple "side effect" of the fact that the conditions of S d t are defined for solving the consensus problem. It is not at all counter-intuitive that using a condition designed for a stronger problem (consensus) can allow for more efficient solutions when used to solve weaker problems (k-set agreement for k > 1). This observation suggests the following question. Considering the `-set agreement problem (` 1) in a synchronous system prone to t process crashes, is it possible to design conditions directly suited to that problem, i.e., devise families of conditions S d t , 0 d t, such that there are conditions C 2 S d t that allow to solve efficiently the `-set agreement problem while they do not necessarily allow to solve efficiently (`; 1)-set agreement? 2 Said 1 That algorithm actually combines a condition C 2 S d t and a failure detector of a class denoted y t . It solves k-set agreement with k = 1 + m a x (0 d ; y). Here we consider the case where the failure detector offers no additional power, i.e., y = 0 . 2 As a simple example, the condition C that contains all the vectors whose entries contain exactly two different values allows to solve very efficiently the 2-set agreement problem despite any number of process crashes, while it does not allow to solve efficiently consensus in the same failure context. Irisa differently, can an input vector be seen as encoding up to `different values? (Taking `= 1 boils down to a condition

in C 2 S d t = S d 1 t .)
The paper presents and investigates such a family of conditions S d t , 0 d t. As we will see in the paper, when > t ; d, S d t contains the trivial condition including all the possible input vectors. More generally, the paper establishes the following hierarchy for the synchronous `-set agreement problem: S 0 t S 1 t S d t S t+1;` t = S t+2;` t = = S t t :

Given such a hierarchy, an important question is the following one. Considering a condition C 2 S d t and assuming ` k (otherwise, a condition C 2 S d t is useless to solve k-set agreement), how can C help solve the k-set agreement problem in a synchronous system prone to t crashes? The paper answers this question by presenting an algorithm that, when the input vector belongs to the condition C 2 S d t the algorithm is instantiated with, realizes the pair (k R) where

R = d ; 1 + k + 1 :
When the input vector does not belong to C, the algorithm requires at most t k + 1 rounds. Given t and `, this means that, when we consider the previous hierarchy ; S d t 0 d t+1;`, there are less and less conditions when d decreases (and these conditions contain less and less vectors), but these conditions always allow for a faster decision each time the input vector belongs to the condition. This noteworthy formula pieces together all the relevant parameters. It involves, on one side, the coordination degree k associated with the set agreement problem we want to solve (i.e., the difficulty of the problem instance we want to solve, which increases when k decreases), and, on the other side, the pair (d `) characterizing the condition the input vector belongs to (i.e., the help we receive to solve the problem, which increases when d or `decreases).

As a simple example, let us consider the case where d = t + 1 ; `, i.e., the set S t+1;` t . As previously indicated, that set includes the condition containing all the possible input vectors. We consequently obtain R = b t k c + 1 , the classical lower bound when no condition is used [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF].

Roadmap

The paper is made up of 8 sections. Section 2 defines the notion of (x `)-legality (the conditions in S d t are (t ;d `)legal). Section 3 investigates the structure of the sets of (x `)-legal conditions for 0 x < n and 0 < ` n.

More precisely, for each pair of pairs, (x 1 1) and (x 2 2), that section states if an (x 1 1)-legal condition is also an (x 2 2)-legal condition or not. Interestingly, this structure shows also the following: the condition including all the input vectors is (x `)-legal only if `> x, and, for `> x, the set of (x `)-legal conditions contains the condition including all input vectors 3 . Section 4 briefly considers (x `)-legality in asynchronous systems, while Section 5 presents hierarchies of sets of conditions suited to synchronous `-set agreement. Then, Section 6 presents a synchronous k-set agreement algorithm whose properties have been previously described. Section 7 proves its correction. Finally, Section 8 provides concluding remarks and presents open problems.

Conditions for set agreement

This section and the following (on the structure of the set of conditions) are independent of the underlying synchrony assumption and the way processes communicate (message-passing vs shared memory).

Preliminaries Process Model

The system consists of a finite set of n processes denoted = fp 1 : : : p n g. A process is faulty during an execution if it prematurely stops its execution (crash). After it has crashed, a process does nothing. A correct process is a process that is not faulty. As already mentioned, t denotes the upper bound on the number of faulty processes (1 t < n ).

The set agreement problem The k-set agreement problem has been informally stated in the Introduction: every process p i proposes a value v i and all correct processes have to decide on a value v, in relation to the set of proposed values. More precisely, the problem is defined by the following three properties:

• Termination. Every correct process eventually decides.

• Validity. If a process decides v, then v was proposed by some process.

• Agreement. At most k different values are decided.

Notation

In the following V denotes the set of values that can be proposed by the processes, and ? denotes a default value that cannot be proposed by the processes.

An input vector I is a vector of size n (denoted jIj = n), whose i-th entry contains the value proposed by p i , or ? if p i did not take any step in the execution, where ? denotes a default value such that ? = 2 V and 8a 2 V , ? < a . We usually denote by I a vector with all entries in V, and with J a vector that may have some entries equal to ?; such a vector J is called a view.

The values of V that are present in I defines a subset of V denoted val(I); jval(I)j denotes its cardinality. Let J1 J 2 with some entries are possibly equal to ?. W e say "J2 contains J1"

(denoted J1 J2) if 8k : J1 k] 6 = ? ) J1 k] = J2 k].
The number of occurrences of a value a in the vector J, with a 2 V f?g is denoted # a (J). d H (J 1 J 2 ) denotes the Hamming distance separating J 1 and J 2 , i.e., the number of entries in which J 1 and J 2 differ. Moreover, given a non-empty set of vectors fJ 1 : : : J z g, d G (J 1 : : : J z ) denotes the number of distinct entries for which at least two vectors in J 1 : : : J z differ. We call d G (J 1 : : : J z ) the generalized distance of the set of vectors J 1 J 2 : : : J z . As an example, d G ( a ? a e b b ] a ? a e c c ] a ? f e b c ]) = 3. As we can see, when d G () is on two vectors, it boils down to the Hamming distance.

Let I 1 : : : I z be a set of vectors. \ 1 j z I j denotes the vector containing the n ; d G (I 1 : : : I z ) entries that belong to all the vectors I 1 : : : I z . It is called the intersecting vector of I 1 : : : I z . When clear from the context, the notation \ 1 j z I j is also used to denote the set of values in that intersecting vector.

The notion of (x `)-legality

Definition 1 A condition is a set of input vectors.

Definition 2 Let 0 < ` n. A condition C is (x `)-legal if there is a function h `() that satisfies the following properties:

1. (x `)-Validity. 8I 2 C : h `(I) val(I) and jh `(I)j = min(` jval(I)j). 2. (x `)-Density. 8I 2 C : v2h `(I ) # v (I) > x , 3. (x `)-Distance. 8 : 0 < x , 8I 1 : : : I z 2 C: d G (I 1 : : : I z ) = x ; ) v2 T 1 j z h `(Ij ) # v (\1 j z I j ) > . As already indicated, intuitively, an input vector I of an (x `)-legal condition can be seen as a codeword encoding an "abstract" value. That "abstract" value can be instantiated by any value of a set of `"concrete" values, namely, the values defined by h `(I). The aim of the validity, density and distance properties is to ensure that the function h `() provides a correct "decoding".

The validity property states that at most `values can be decided and those are values that belong to the input vector. The density property guarantees that a decided value can be extracted from an input vector, despite up to x crashes (from an operational point of view, the corresponding entries in the input vector can possibly remain forever equal to ?).

Finally, the distance property guarantees that if a set of input vectors differ in some number of entries (namely,

x ; ), then they must contain values that (1) can be decided from each of them, and (2) are present enough in each of them (namely, more than times): the intersecting vector \ 1 j z I j must contain "enough" values of T Definition 3 A function h `() that makes (x `)-legal a condition C is called an (x `)-recognizing function for C. If additionally the addition to C of any new vector I is such that the condition C f Ig is not (x `)-legal, the function h `() is called an (x `)-generating function for C.

Remark When we consider `= 1 , the previous definition of (x `)-legality boils down to notion of x-legality introduced in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]. The distance property simplifies and becomes h 1 (I 1 ) 6 = h 2 (I 2 ) ) d H (I 1 I 2 ) > x . It follows that a condition C allows to solve the consensus problem in an asynchronous system prone to x process crashes if and only if it is (x 1)-legal.

Theorem 1 Let C be an (x `)-legal condition, J a vector such that # ? (J) x, and I 1 : : : I z input vectors in C such that J I 1 : : : J I z . 0 < j T 1 j z h `(I j )

T val(J)j `.

Proof Let us first observe that, due to the validity property, we have 8 I 1 : : : I z : jh `(I j )j `, from which it follows that j T 1 j z h `(I j ) T val(J)j `.

Let us now show that the set T 1 j z h `(I j )

T val(J) is not empty. Let # ? (J) = x ; with 0

x. Let d G (I 1 : : : I z ) = x ; . As J I 1 : : : J I z , we also have d G (I 1 : : : I z ) = # ? (J) ; with 0. Finally, as # ? (J) ; = ( x ; ) ; , we have x ; = ( x ; ) ; , i.e., + = with 0.

Due either to the density property (case = x) or the distance property (case 0 < x), if follows that we have v2 T 1 j z h `(Ij ) # v (\ 1 j z I j ) > . As + 1 = + + 1 > , more than entries of this intersecting vector \ 1 j z I j contain values of T 1 j z h `(I j ). As each entry of T 1 j z h `(I j ) is an entry of J and no entry of T 1 j z h `(I j ) is equal to ?, it follows that at least one value in T 1 j z h `(I j ) belongs to J.

2 Theorem 1

Thanks to the previous lemma, the function h `() can be extended to vectors J with at most x entries equal to ?.

Definition 4 Let C be an (x `)-legal condition, and J a vector such that # ? (J) x. Let I 1 : : : I z be the inputs vectors in C (if any) such that J I 1 : : : J I z . The definition of h `() is extended to such vectors J as follows: h `(J) = T 1 j z h `(I j ) T val(J). (If there is no input vector I such that J I, h `(J) is left undefined.)

(x `)-legality with h `() = max `()

This section investigates the case where h `(I) returns the `greatest values of I. This function is denoted max `()

(max 1 () is denoted max()).
Let us observe that all the theorems in this section remain true when the function max `() is replaced by the function min `().

Theorem 2 Let C be the condition the vectors of which satisfy the (x `)-validity and (x `)-density properties when considering the function h `() = max `(). The condition C is (x `) legal.

Proof Let us consider the condition C that contains all the vectors I that satisfy the (x `)-size property and the (x `)density property, i.e., I 2 C ) v2max `(I) # v (I) > x . Let us observe that C is not empty. So, to prove the theorem, we have to show that any set of vectors fI 1 : : : I z g C such that d G (I 1 : : : I z ) = x ; (with 0 < x) satisfies the (x `)-distance property, i.e., we have v2 T 1 j z h `(Ij ) # v (\ 1 j z I j ) > .

Let D = d G (I 1 : : : I z ). Let us consider any vector I j 2 f I 1 : : : I z g. As I j 2 C, we have v2max `(Ij ) # v (I j )

x + 1 = D + + 1 . In the worst case, (1) the same D entries of the vectors I 1 : : : I z contain only values among their `greatest values, and (2) these entries contain different values. As, for each I j , v2max `(Ij ) # v (I j ) D+ + 1 , it follows that the vectors I 1 : : : I z share + 1 entries that contain values belonging to their `greatest values.

2 Theorem 2

Size of the condition defined by h 1 () = max() This section computes the number of distinct input vectors that are in the (x 1)-legal condition defined by the function max().

Let m denote the number of different values that can be proposed. Without loss of generality let f1 : : : m g be this set of values. Moreover, let n denote the number of processes, and Comb(n ) denote the number of subsets of elements in a set of n elements (binomial -or Pascal-coefficient).

Let NB(x 1) be the number of input vectors in the (x 1)-legal condition defined from max() (we trivially have NB(0 1) = m n ).

PI n ˚1870

Theorem 3 NB(x 1) = P m =1 P n =x+1 Comb(n ) ( ; 1) n; :

Proof Let us first determine the value of NB(1 1). As x = 1 , a value has to appear at least twice in a vector in order to be decided. We have the following cases.

• If m is the greatest value in the vector, there are Comb(n 2) (m;1) n;2 vectors in which the value m appears exactly twice, and more generally, there are Comb(n ) (m ; 1) n; vectors in which m appears exactly times, for 2 n.

• If m ; 1 is the greatest value in the vector, there are C o m b (n ) (m ; 2) n; vectors in which the value m ; 1 appears exactly times for 2 n.

• And similarly, for the cases where m ; 2, m ; 3, ..., 2 1 is the greatest value in the vector. (Let us notice that when = 1 , i.e., the case of the smallest value, we have a single vector.)

• Summing up all the possible cases, we obtain the following formula 5 :

NB(1 1) = m X =1 n X =2
Comb(n ) ( ; 1) n; :

More explicitly, denotes the greatest value in a vector, its cardinality in that vector, Comb(n ) the number of vectors with entries equal to , and ( ; 1) n; the number of possibilities for placing the values smaller than in the vector.

When x = 2 , a simple observation shows that has to vary from 3 to n, instead of from 2 to n. More generally, a straightforward generalization gives the following formula:

NB(x 1) = m X =1 n X =x+1 C o m b (n ) ( ; 1) n; : 2 Theorem 3
The computation of NB(x `) (the size of the maximal condition generated by h `() = max `()) is more involved.

It is determined in Appendix A.

3 The structure of the sets of (x `)-legal conditions

This section investigates the structure of the sets of (x `)-legal conditions, for 0 x < n and 0 < ` n. The whole picture relating these sets of conditions is described in Figure 1.

Theorem 4 Let 0 x < n ; 1 and 0 < ` n. If a condition C is (x + 1 )-legal, it is also (x `)-legal. Proof As C is (x + 1 )-legal we have 8I 2 C : v2h `(I) # v (I) > x + 1 > x, from which the (x `)-density property of C trivially follows. As far as the (x `)-distance property is concerned, let us observe that the domain of the parameter used in the statement of the (x + 1 )-distance property is f0 : : : x g. Hence, the (x + 1 )-distance property is the addition of the (x `)-distance property (that addresses the cases 0 < x ), plus the particular case = x, which completes the proof.

2 Theorem 4

Theorem 5 Let 0 x < n ; 1 and 0 < ` n. There are conditions that are (x `)-legal, but not (x + 1 )-legal.

Proof Given a vector I, let S `(I) denote a set of `values appearing in I. Let C be the (x `)-legal condition, recognized by the function max `(), that contains only the vectors I such that 8 S `(I) : v2S `(I ) # v (I) x + 1 .

It is easy to see that C is not empty. Moreover, it follows from the additional constraint on the vectors I that, whatever the function g `(), we cannot have v2g `(I) # v (I) > x + 1 . So, no (x + 1 )-recognizing function g `() can be associated with C. It follows that C is not (x + 1 )-legal.

2 Theorem 5

Theorems 4 and 5 are associated with the vertical arrow in the figure at the right. In that figure (as in Figure 1), a pair (x `) represents the set of all the (x `)-legal conditions, and an arrow from a pair (a b) to a pair (a 0 b 0 ) means "the set of (a b)-legal conditions is included in the set of (a 0 b 0 )-legal conditions". Theorems 6 an 7 (that follow) are associated with the horizontal arrow.

(x + 1 ) (x + 1 + 1) (x `)
Theorem 6 Let 0 x < n and 0 < < n . If a condition C is (x `)-legal, it is also (x `+ 1 ) -legal. Proof Let h `() be an (x `)-recognizing function for the condition C. The proof consists in defining a function g `+1 () that is (x `+ 1 ) -recognizing for C. Let g `+1 () be defined as follows (g `+1 () is an appropriate extension of h `()). Let I 2 C.

• If h `(I) = val(I) (i.e., h `(I) contains all the values in I), then g `+1 (I) = h `(I).

• If h `(I) val(I), then g `+1 (I) = h `(I) f ag, where the value a is defined as follows.

Let I R be the vector I whose all entries containing a value of h `(I) have been suppressed. (As h `(I) val(I), I R is a vector with at least one entry). Let a = f(I R ), where f is a deterministic function that extracts a value from a vector.

It directly follows from its definition that g `+1 () satisfies the (x `+ 1 ) -size property for any vector I 2 C. Let us consider the (x `+ 1 ) -density property. Let I 2 C. We consider two cases.

• g `+1 (I) = h `(I). As, in that case, we have h `(I) = val(I), we conclude that v2g `+1 (I) # v (I) = v2h `(I) # v (I) = n. It follows trivially that v2g `+1 (I) # v (I) > x .

• g `+1 (I) = h `(I) f ag. As v2h `(I) # v (I) > x , v2g `+1 (I) # v (I) = v2h `(I) # v (I) + # a (I), and # a (I) 1,

we conclude that v2g `+1 (I) # v (I) > x + 1 > x .

To show that g `+1 () satisfies the (x `+ 1 ) -distance property, let us consider a set of vectors fI 1 : : : I z g C such that d G (I 1 : : : I z ) = x ; , with 0 < x . We have to show that v2 T 1 j z g `+1 (Ij) # v (\ 1 j z I j ) > .

According to its definition, we have g `+1 (I j ) = h `(I j ) A j , with A j = fa j g or A j = . So, T 1 j z g `+1 (I j ) = T 1 j z ; h `(I j ) A j =

; T 1 j z h `(I j ) S S ; T 1 j z A j , and consequently v2 T 1 j z g `+1 (Ij) # v (\ 1 j z I j ) v2 T 1 j z h `(Ij ) l(\ 1 j z I j ). Finally, as d G (I 1 : : : I z ) = x ; ) v2 T 1 j z h `(Ij ) l(\ 1 j z I j ) > , we can conclude that v2 T 1 j z g `+1 (Ij) # v (\ 1 j z I j ) > , which completes the proof of the (x `+ 1 ) -distance property for the function g `+1 ().

2 Theorem 6

Theorem 7 Let 0 x < n and 0 < < n . There are conditions that (x `+ 1 ) -legal, but not (x `)-legal.

Proof The proof is similar to the proof of Theorem 5. Given a vector I, let S `(I) denote a set of `values appearing in I. Let C be the (x `+ 1 ) -legal condition, recognized by the function max `+1 (), that contains only the vectors I such that 8S `(I) : v2S `(I ) # v (I) x. It is easy to see that C is not empty. Let us observe that the additional constraint states that no vector of C has a set of `values that appear in it more than x times. It follows from that observation that no function g `() can be (x `)-recognizing for C (i.e., there is no function g `() such that, for any I 2 C, v2g `(I) : # v (I) > x ).

Theorem 7

Theorem 8 Let > x . The set of (x `)-legal conditions contains the condition including all input vectors.

Proof Let C all be the condition including all input vectors. Let us consider any vector I 2 C all . As `> x, its greatest values appear at least ` x + 1 times in I. Consequently, when considering the function h `() = max `(), the vectors of C all satisfy the (x `)-validity and (x `)-density properties. It then follows from Theorem 2 that C all is (x `)-legal.

2 Theorem 8 Here, each pair (x `) contains the Figure 1: The global inclusion picture, 0 x < n , 0 < ` n Theorems 4, 5, 6, 7, 8 and 9 are summarized, for all the values of x and `, in the lattice described in Figure 1. It is shown in Appendix B that there are conditions that are (x `)-legal and not (x+ 1 + 1 ) -legal, and there are conditions that are (x + 1 + 1 ) -legal and not (x `)-legal.

Theorems 8 and 9 relate the (x `)-legality of the condition made up of all input vectors with the property > x .

As already suggested (footnote 3, Introduction), this is the condition-based way to express the impossibility to solve the `-set agreement in an asynchronous system prone to x process crashes when ` x [START_REF] Borowsky | Generalized FLP Impossibility Results 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].

(x `)-Legality in asynchronous systems

As indicated in the introduction, when `= 1, the notion of (x `)-legality boils down to the notion of x-legality introduced in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF], where it is shown that a condition C allows solving the consensus problem in asynchronous systems prone to x process crashes if and only if C is x-legal.

The asynchronous condition-based algorithm decried in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] can easily be generalized to solve the `-set agreement problem in asynchronous systems prone to x process crashes, when the input vector belongs to an (x `)-legal condition. Proving (or disproving), for > 1, that (x `)-legality is necessary for any condition-based solution to the `-set agreement problem remains an open problem.

Irisa 5 Synchronous hierarchies

A hierarchy on the sets of conditions that allow solving the consensus problem in synchronous systems prone to t process crashes has been established in [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF], namely, S 0 t S 1 t S d t S t t , where S d t includes all the conditions that allows solving consensus in asynchronous systems prone to x = t ; d crashes [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]. (Let us remind that S t t contain the condition that includes all input vectors, and S 0 t contains all the conditions that allow solving asynchronous consensus despite t process crashes.)

This hierarchy is such that, when the input vector belongs to a condition C 2 S d t , it is possible to solve optimally synchronous consensus in d + 1 rounds. The degree d of a condition is related to its size. There are conditions with more and more vectors when d increases, showing an inherent tradeoff relating the size of a condition and the number of rounds required for the processes to decide.

Considering the (x `)-legality (instead of x-legality, that corresponds to the case `= 1 ), let us define S d t as the set of all (t ; d `)-legal conditions. Replacing x by t ; d in Figure 1, we obtain the following two hierarchies for the `-set agreement problem in synchronous systems prone to up to t process crashes:

• `fixed: S 0 t S 1 t S d t S t+1;` t = S t+2;` t = = S t t :

• d fixed: S d

A synchronous condition-based set agreement algorithm

This section presents a k-set agreement algorithm for synchronous message-passing systems in which up to t processes can crash. The algorithm is instantiated with a condition C 2 S d t .

Requirements and properties of the algorithm

Requirements on the values of d and `The values of k and t being fixed, the algorithm considers a condition C 2 S d t such that ` t;d. This requirement is motivated by the following observation. On one side, (as announced in the introduction and proved below), the maximal number of rounds required for a process to decide is b d;1+k c + 1 when the input vector belongs to the condition. On another side, as (`+ d) > t )

; b d;1+k c + 1 b t k c + 1 , it follows that a synchronous k-set agreement algorithm cannot benefit from a condition such that `+ d > t (6 ).

The algorithm considers also that k `. This is because, when k < , a condition C 2 S d t provides no additional power a k-set algorithm could benefit from in order to expedite decision. (When k < , a condition C 2 S d t does not restrict enough the set of input vectors in order to obtain a more efficient k-set agreement algorithm.) Properties of the algorithm Let I be the current input vector, C 2 S d t be the condition the algorithm is instantiated with, and f be the number of processes that crash in the current run. As far the number of rounds is concerned, the algorithm guarantees the following properties:

• If I 2 C:

-If f t ; d: no process executes more than two rounds.

-If t ; d < f : no process executes more than b d;1+k c + 1 rounds.

• I = 2 C: no process executes more than b t k c + 1 rounds. Moreover, if more than t ; d processes have crashed before the algorithm starts, no process decides after b d;1+k c + 1 rounds.

Remark Let us observe that, up to now, no k-set agreement synchronous algorithm based on consensus conditions C 2 S d t has been proposed, that requires at most b d k c+1 rounds. This case (that we have considered in the introduction) appears as a particular instance of the proposed algorithm when considering `= 1, i.e., when the proposed k-set algorithm is instantiated with a condition that allows solving consensus in an asynchronous system prone to t ; d crashes.

  Let us assume that the input vector I belongs to a condition C 2 S d t (i.e., C allows to solve consensus in an asynchronous system in which up to (t ; d) processes may crash). Moreover, let us consider the pair (k R) where R is the number of rounds to solve synchronous k-set agreement despite up to t crashes. This observation gives rise to the following questions: Are there algorithms for other (k R) pairs? If yes, what is the generic formulation of the (k R) pair, i.e., what is the relation linking R, k and d?

	When looking at the results described in [21, 22], we have two synchronous algorithms: (i) one solves consensus in d + 1 rounds [22], i.e., it realizes the pair (1 d + 1 ) ; (ii) the other solves (d + 1 ) -set agreement in one round [21], i.e., it realizes the pair (d+ 1 1).

Theorem 9

 9 The condition made up of all the input vectors is (x `)-legal only if > x .

		x	(n ; 1 1): wait-free consensus
	Wait-free line	n ; 1
		n ; 2
	x + 1
	x-resilience line	x
		; 1			`> x
		2
		1		condition made up of all the vectors
	Reliable line	0			ǹ
		1	2	`; 1	x n ; 1 `+ 1
		From the strongest to the weakest agreement
	PI n ˚1870

Intuitively, this seems to be related to the impossibility to solve the `-set agreement problem in an asynchronous system prone to x process crashes when ` x. Impossibility means here that there is no asynchronous algorithm when the actual input vector can be any input vector.PI n ˚1870

j z h `(I j ).( 4 .)[START_REF] Attiya | Distributed Computing: Fundamentals, Simulations and Advanced Topics[END_REF] It could be possible to integrate the density property inside the distance property by considering the case = x. We have not done it, because in some proofs, the case = x has to be treated separately.Irisa

The case of the single vector that contains only the smallest value (case = 1 ) appears implicitly in the formula. As 0 n; = 0 for 2 < n , and 0 n; = 1 for = n, when = 1 we have P n =2 Comb(n ) ( ; 1) n; = 1 .Irisa

This is not at all counter-intuitive. As we have seen in Theorem 8, when > t ; d the set S d t contains the condition C all including all the input vectors. As the algorithm depends on the parameters t, `and d only (it does not depend on other parameters of the condition, such as the number of input vectors it is made up), it implicitly assumes that it is instantiated with C all , and the number of rounds is then upper bounded by b t k c + 1 .PI n ˚1870

Proof Let C all be the condition all input vectors. We claim that all cannot be (x x)-legal. Assuming that claim, show that C all is not (x `)-legal for ` x. The proof is by contradiction. Let us assume that C all is (x `)legal for ` x. It then follows by successive applications of Theorem 6 that C all is (x `+ 1 ) -legal, (x `+ 2 ) -legal, ..., (x x)-legal, contradicting the claim, and proving the theorem.

Proof of the claim. Taking x = `, Theorem 7 states that there are conditions that are (x x + 1 ) -legal but not (x x)-legal. Let C be such a condition. We trivially have C C all . As C is not (x x)-legal, it follows that C is not (x x)-legal either (adding vectors to a condition that is not (x x)-legal cannot make it (x x)-legal).

2 Theorem 9 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000

Synchronous computation model

Round-based synchronous computation The synchronous model is the same as in [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF]. The processes p 1 : : : p n communicate and synchronize by sending and receiving messages through channels. Every pair of processes p i and p j is connected by a channel. The underlying communication system is assumed to be failure-free: there is no creation, alteration, loss or duplication of message.

The system is round-based synchronous, i.e., its executions consists of a sequence of rounds 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 during which each process sends messages. We assume that there is a predetermined order in the sending of messages. More precisely each process sends a message first to p 1 , then to p 2 , etc., until p n . Thus, if a process crashes during a send phase, only a (possibly empty) prefix of these messages is delivered. • A receive phase during 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 same round r.

• A computation phase during which each process processes the messages it received during that round and executes local computation.

A note on the synchronous model of this paper

In the standard synchronous model [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], a process p i sends messages to other processes in each round, and if p i fails during a round r, any subset of the messages it has sent during r can be lost. In the model used in this paper, each process sends messages to other processes in a predetermined order.

This allows the processes to obtain views of the input vector that ordered by containment (this containment is denoted J1 J2 in Section 2.1), similarly to what can be obtained when using snapshots in read/write shared memory systems [START_REF] Afek | Atomic Snapshots of Shared Memory[END_REF]. Actually, only the first round of the algorithm requires this this sending order property. (Let us notice that some lower bound results on synchronous agreement use a similar model where the "adversary" can drop messages in a predetermined order only [START_REF] Dolev | Early Stopping in Byzantine Agreement[END_REF][START_REF] Keidar | A Simple Proof of the Uniform Consensus Synchronous Lower Bound[END_REF][START_REF] Moses | A Layered Analysis of Consensus[END_REF]].)

A synchronous condition-based set agreement algorithm

The synchronous round-based algorithm is described in Figure 2. As indicated, the round number appears as a common variable r whose progress is ensured by the underlying system (lines 2 and 11). The value proposed by the process p i is denoted v i .

Given a vector J such that # ? (J) t, the predicate P(J) returns true, if 9I 2 C such that J I. Let us recall that it is possible that several input vectors I 1 : : : I z 2 C can exist such that J I 1 : : : J I z . In that case, due to Theorem 1 and Definition 4, we have h `(J) = T 1 j z h `(I j )

T val(J) with 0 < jh `(J)j `.

The algorithm uses the default value ?, that is assumed to be smaller than any value proposed by a process. The notation a = b 6 = ? (resp., a = b = ?) is used as a shortcut for a = b ^a 6 = ? (resp., a = b ^a = ?).

Local variables and their meaning Each process p i manages the following local variables.

• V i 1 : n] is a local array, initialized to ? : : : ?]. This array is used only during the first round, namely, if during that round p i receives the value v j proposed by p j , it updates accordingly V i j] to v j (line 5). V i is the view of the input vector obtained by p i . max(V i ) denotes the greatest (non-?) value in V i .

• v cond i , v tmf i and v out i are three local variables (initialized to ?) whose aim is to contain a proposed value.

Their meaning is the following. (In all the cases, p j is possibly p i .) -When v cond i = v 6 = ?, p i knows that there is a process p j that, during the first round, obtained a local view V j such that 9I 2 C with V j I. Consequently, it is possible that the actual input vector belongs to the condition C. So, p j has computed a value v from h `(V j ) that could be decided (line 6), and that value is currently known by p i (line 15).

-When v tmf i = v 6 = ?, p i knows that there is a process p j that, during the first, round obtained a local view V j whose number of ? witnesses too many failures (hence the name tmf ). That process has consequently computed a value v that could be decided from its view (line 8), and that value is currently known by p i (line 16).

Irisa

-When v out i = v 6 = ?, p i knows that there is a process p j that, during the first, round obtained a local view V j that allows it to conclude that the input vector does not belong to the condition (line 7). That process p j has consequently computed a value v that could be decided from its view V j , and that value is currently known by p i (line 17).

V i ? : : : ?]; V i i] v i ; v cond i ? ; v out i ? ; v tmf i ? ;

(2) when r = 1

(3) begin round [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations and Advanced Topics[END_REF] send (v i ) to p 1 p 2 : : : p n in that order; [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF] for each v j received do V i j] v j end do; [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF] case (# ? (V i ) t ; d) ^P (V i ) then v cond i max(h `(V i ))

end case [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF] end round;

(11) when r = 2 : : : b t k c + 1 do (12) begin round [START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF] send (v cond i v out i v tmf i ) to p 1 p 2 : : : p n (in any order);

v cond i max(v cond j received); % 8v j : ? < v j % ( 16)

v out i max(v out j received);

if (r = b d;1+k c + 1 ) ^v tmf i 6 = ? v out i = ?) _ (r = b t k c + 1 ) then [START_REF] Moses | A Layered Analysis of Consensus[END_REF] if (v cond i 6 = ?) then return (v cond i )

elseif (v tmf i 6 = ?) then return (v tmf i )

else return (v out i ) end if [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF] end if [START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF] end round Process state Let UP r be the set of the processes that have not crashed by the end of the round r, and var r i be the value of the local variable var i of p i at the end of the round r (if p i 2 UP r ). Moreover, for each p i 2 UP r , let state r i be the triple (v cond i v tmf i v out i ). This triple represents the state of p i from the agreement point of view. Let (state r i = state r j ) def = 8 < : ; v cond r i = v cond r j 6 = ? W ; v cond r i = v cond r j = ? ^v tmf i r = v tmf j r 6 = ? W ; v cond r i = v cond r j = v tmf i r = v tmf j r = ? ^v out i = v out j 6 = ? 9 =

:

Underlying principle and process behavior The aim of the algorithm is to ensure that there are no more than k different states when it terminates. To that end, the processes execute consecutive rounds. During each round, they (1) use a classical flood-set technique to disseminate their states, and (2) reduce the number of values in each "class" (the class of v cond i variables, the class of v tmf i variables, and the class of v out i variables) with the help of a deterministic function (namely, max()).

The behavior of a process p i is fully described in Figure 2. To complete the presentation, let us look at the way a process decides. A process p i decides when it executes return (v) at line 14, 19, 20, or 21.

As suggested in the definition of the equality of two process states, the algorithm establishes a priority on the values defining a process state. If v cond i 6 = ?, that value has priority to be decided. If v cond i = ? and v tmf j 6 = ?, v tmf j has priority with respect to v out i .

When v cond i becomes equal to some value v 6 = ?, p i learns that v can be decided from the condition point of view. So, when this occurs, p i first sent v to all the processes (line 13) and then decides v [START_REF] Izumi | Condition Adaptation in Synchronous Consensus[END_REF].

PI n ˚1870

In the other cases, a process decides during the round r = b d;1+k c + 1 or during the last round r = b t k c + 1 . In both cases, it decides a value in its state according to the priority mentioned above. In order for p i to decide during the round r = b d;1+k c + 1 , some local predicate has to be satisfied (line 18). This predicate states that, to p i knowledge, (1) there is a process that has seen more than t ; d crashes when it executed the first round (this is witnessed by v tmf i 6 = ?), and (2) no process can conclude that the input vector is outside the condition (witnessed v out i = ?). This predicate is used to force the decision at round b d;1+k c + 1 , when, while p i has not yet decided, there is no evidence that the input vector does not belong to the condition. Let us finally observe that the algorithm possesses an additional first class property, namely, design simplicity.

Proof of the algorithm

In the following, we consider that the algorithm is instantiated with a condition C 2 S d t . Moreover, we assume k > ànd ` t ; d. The constraint k > ìs to allow the algorithm to benefit from the condition. The constraint ` t ; d is to eliminate the case where the condition could include all input vectors. As it has been seen in the previous sections, in both cases, the condition-based approach does not allow bypassing the bound b t k c + 1 .

Proof of the termination property

Lemma 1 Let us assume that the input vector belongs to the condition. The protocol described in Figure 2 terminates in (i) 2 rounds when no more than (t ; d) processes crash by the end of the first round, and (ii) at most b d;1+k c + 1 rounds otherwise.

Proof

If the input vector belongs to the condition, no process executes line 7, and consequently all local variables v out i remain forever equal to ?. Let us partition the set of processes (denoted UP 1 ) that terminate the first round in two sets: A = fp i j v cond 1 i 6 = ?g and B = fp i j v tmf i 1 6 = ?g. We consider two cases.

• Case jUP 1 j t ; d. As the input vector belongs to the condition, every process that does not crash by the end of the first round belongs to A. Thus, every such process that does not crash proceeds to the second round and decides in line 5, which proves the case (i).

Lemma 1

Lemma 2 Let us assume that the input vector does not belong to the condition. The protocol described in Figure 2 terminates in (i) b d;1+k c+ 1 rounds when more than (t;d) processes have initially crashed, (ii) and at most b t k c+ 1 rounds otherwise.

Proof The fact that the protocol always terminates by round b t k c + 1 follows directly from the protocol code (line 18) and the fact that the system is synchronous). So, let us consider the runs where more than (t ; d) processes have initially crashed. In that case, each process p i 2 UP 1 gets a view V 1 i with more than (t ; d) entries equal to ?, and consequently v tmf i is set to a non-? value (line 8), while v cond i and v out i remain forever equal to ?. Hence, for any process p i that executes the round b d;1+k c + 1 , we have v tmf i 6 = ? and v out i = ?. It follows that no process executes more than b d;1+k c + 1 rounds.

2 Lemma 2 Theorem 10 The algorithm described in Figure 2 guarantees that no process executes more than b t k c + 1 rounds. Moreover, if the input vector belongs to the condition, no process executes more than b d;1+k c + 1 rounds, and if additionally no more than (t ; d) processes crash, any process executes at most two rounds.

Proof The proof follows from the Lemmas 1 and 2.

Theorem 10

Irisa

Proof of the validity property

Theorem [START_REF] Friedman | Asynchronous Agreement and its Relation with Error-Correcting Codes[END_REF] The algorithm described in Figure 2 guarantees that a decided value is a proposed value.

Proof Let us first observe that, for any process p i that terminates the first round, one of the local variable v cond i , v tmf i or v out i is different from?. Moreover, due to the lines 15-17, this property remains satisfied at any round r 2.

When they are not equal to ?, the local variables v tmf i and v out i can contain only a proposed value (this follows from the lines 7, 8, 16, and 17). On another side, when v cond i is updated at line 6 during the first round, its new value is a value from the set h `(V i ) that contains only values of V i (this follows from Theorem 1 and Definition 4).

The validity property follows then directly from the fact that a process decides a non-? value from a variable v cond i , v tmf i or v out i .

2 Theorem 11

Proof of the agreement property

Theorem [START_REF] Gafni | From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement[END_REF] The algorithm described in Figure 2 guarantees that at most k values are decided.

Proof Let a process p i belong to the set cond winner if (1) v cond 1 i 6 = ? and (2) p i executes line 13 of the second round (i.e., it sends v cond 1 i to all the processes). The sets tmf winner and out winner are defined similarly;

p i 2 tmf winner (resp., p i 2 out winner) if v tmf i 1 6 = ? (resp., v out 1 i 6 = ?) and and it executes line 13 of the second round. Let us observe that a process that executes line 13 of the second round belongs to either cond winner, or tmf winner, or out winner). The proof considers three cases.

Case 1: cond winner 6 = . Let p i , p j , etc., be the processes of the set cond winner. Due to the sending order during the first round (line 4), the vectors V i , V j , ..., are ordered by containment, e.g., V i V j

. It follows from that containment property and Theorem 1 that h `(V i ) h `(V j )

. Consequently, as 0 < jh `(V i )j `and ` k, no more than k values (1) are deposited in the v cond i variables during the first round, and (2) can be decided during the second round.

Let p m be a process that does not decide during the second round. During that round, p m receives at least one v cond i value that is different from ?. Hence, if it executes the third round, p m decides one of the (at least one and most `) non-? values v cond i it has received during the second round, from which it follows that at most ` k different values can be decided when cond winner6 = .

Case 2: cond winner = ^out winner 6 = . We consider two cases.

• A process p m decides at line 14. Let us observe that this can appear only at a round r > 2 (otherwise, we would have cond winner 6 = ).

In that case, p m has sent v cond m 6 = ? to all the processes during r, from which it follows that, from r, only non-? v cond i values can be decided (they are decided at line 14 or at line 19). It follows from the the previous case discussion (Case 1: cond winner 6 = ) that there are at most `such v cond m 6 = ? values. The result follows then from ` k.

• No process decides at line 14.

In that case, the variables v out i of all the processes that execute line 17 during the second round are such that v out r i 6 = ?, for r 2. Proof of the claim. The proof is by contradiction. Let us assume that there are k + 1 different states at the end of round R. This means that there are k processes that crash during R and there were at least k + 1 different states at the end of round R ; 1, which in turn means that k processes crashed during R ; 1 and there were at least k + 1 different states at the end of round R ; 1, etc. until round r = 1 .

Let us consider the number of crashes that have to occur during the first round, in order to have k + 1 different states at the end of that round. In the worst case, as the vectors are ordered by containment, and as each vector

gives rise to a single value (this is due to the use of the function max() at lines 6-8), k+ 1 different vectors (local views) are needed in order to obtain k + 1 different states (some vectors providing values c out i 6 = ?, others providing values c cond i 6 = ?, and others providing values v tmf i 6 = ?) 7 . To obtain k + 1 different vectors, we need to have k crashes during the first round.

When we sum up the number of crashes needed to have k + 1 different states at the end of round R = b t k c + 1 , we obtain k(b t k c + 1 ) process crashes. Let t = k + with 0 < k . We have k (b t k c + 1 ) = k + k = t ; + k > t , a contradiction with the fact that there are at most t crashes. Case 3: cond winner = ^out winner = . As previously, there are two cases. If a process p m decides at line 14, the proof is the same as the first item of Case 2. So, in the following we consider that no process decides at line 14.

(cond winner = ^out winner = ) ) (tmf winner 6 = ), from which follows that any process p i that terminates the second round is such that v tmf r i 6 = ? for r 2. Consequently (due the priority among the values of the variables v cond i , v tmf i and v out i as defined by the equality on the process states and used in the predicates of lines [START_REF] Moses | A Layered Analysis of Consensus[END_REF][START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF][START_REF] Mostefaoui | The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement[END_REF], from the second round, the non-? values kept in v out i (if any) become irrelevant. This means that a process can decide only at line 19 or at line 20.

The rest of the proof consists in showing that at most k values can be decided by these processes. To that end, we show that there are no more than k different states at end of round R = b d;1+k c + 1 .

Let us assume by contradiction that there are k + 1 different states (or more) at the end of the round R. This means that there are k crashes during R, and there were at least k + 1 different states at the end of the round R ; 1. Etc. until the end of the first round.

Let us compute the minimal number of crashes that have to occur during the first round in order to have k + 1 different states at the end of that round. First, there are at most `distinct values obtained by the processes p m such that P(V m ) is satisfied. Second, as, from the second round, v tmf i 6 = ? for all the processes p i , we conclude that there were more than t ; d process crashes during the first round. Different vectors V i such that (# ? (V i ) > t ; d) can give rise to different values v tmf i 6 = ?.

In order to have k + 1 different states at the end of r = 1 , we need to have at least (k + 1 ) ; `different vectors V i such that # ? (V i ) > t ; d. As, the vectors are ordered by containment, this means that, in the worst case, we need to have a vector V i1 such that # ? (V i1 ) = ( t ; d) + 1 , a second vector V i2 such that # ? (V i2 ) = ( t ; d) + 2 , etc., until a vector V ia such that # ? (V ia ) = ( t ; d) + ( k ; `+ 1 ) , i.e., at least (t ; d) + ( k ; `+ 1 ) processes have to crash by the end of the first round.

Let us sum up the number of crashes needed to have at least k + 1 different states at the end of the round R. There are k crashes from the second round until the round R = b d;1+k c + 1 , and (t ; d) + ( k ; `+ 1 ) crashes during the first round. We obtain S = ( t ; d + k ; `+ 1 ) + k (b d;1+k c). Let d ; 1 + `= k + with 0 < k . S = ( t ; d + k ; `+ 1 ) + k = ( t ; d + k ; `+ 1 ) + ( d ; 1 + `; ) = t + k ; . A contradiction as t + k ; > t .

2 Theorem 12

Concluding remarks

Early decision Early decision and early termination address the fact that, while b t k c + 1 rounds are necessary in the worst case (when conditions are not used or when the input vector does not belong to the condition), less rounds can be necessary when less than t processes crash. let f, 0 f t, be the number of processes that crash in the current run. It has been shown that the early deciding lower bound is R = min(b f k c + 2 b t k c + 1 ) [START_REF] Gafni | From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement[END_REF]. Synchronous early-deciding k-set 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 k-set Agreement in Synchronous Systems with General Omission Failures[END_REF][START_REF] Raynal | Synchronous Set Agreement: a Concise Guided Tour (Including a New Algorithm and a List of Open Problems)[END_REF]. By using the technique introduced in [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF], it is possible to extend the proposed synchronous k-set agreement algorithm in order that, in addition to its previous properties, it never requires more than b f k c + 2 rounds.

The main challenge

The paper leaves open the following great challenge: show (or disprove) that, when we consider the condition-based approach in the context of asynchronous systems prone to x process crashes, the `-set agreement problem can be solved iff the condition is (x `)-legal. The "if" part is easy (as already noticed, the consensus algorithm 7 k + 1 different vectors can give rise to less than k + 1 different states, but we are interested in the worst case.

Irisa

described in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] designed for x-legal conditions (i.e., the (x 1)-legal in the proposed framework), can easily be generalized to solve the `-set agreement problem when the condition it is instantiated with is (x `)-legal). The other part is the really difficult side. We spent time and efforts to take up that challenge, but have not yet succeeded.

A Size of the condition generated by the function max `()

This appendix provides a formula for NB(x `), the size of the (x `)-legal condition generated by h `() = max `().

Notation Considering an input vector I, let i denote its ith greatest value, and i its occurrence number, i.e., i = # i (I). let us recall that m is the number of different values that can be proposed, and that these values are denoted 1 : : : m . Moreover, let B i = P i j=1 j (the number of occurrences of the i greatest values in a vector; by definition, B 0 = 0 ). Theorem 13 NB(x `) = A + B where A = `;1 X j=1 m j X 1 1 n;(j;1) 1 2 n;B1;(j;2) 1 j;1 n;Bj;2;1

Proof We show that A is the number of vectors that have less than `distinct values (let us notice that all these vectors trivially satisfy the (x `)-density property), and B is the number of (x `)-dense vectors generated by the function max `(), that have `or more distinct values.

Irisa

Determination of A Let A j , 1 j < , denote the number of vectors that have exactly j distinct values. We have the following.

• A 1 = m. This trivially follows from the fact that there are m different values.

• A 2 = Comb(m 2) P 1 1 n;1 Comb(n 1 ): C o m b (m 2) is the number of sets of two values, taken from the set of m possible values. The greatest of these two values can be placed into one, two, ..., or n ; 1 entries of the vector (hence, 1 1 n ; 1). Moreover, for each value of 1 , there are C o m b (n 1 ) possibilities to select 1 entries in the vector of size n. As soon as these 1 entries have been filled with the greatest value, the entries for the other value are fully determined.

Hence, the formula for A 2 .

• A 3 = Comb(m 3) P 1 1 n;2 Comb(n 1 ) P 1 2 n; 1;1 C o m b (n ; 1 2 ).

Similarly to the previous case, C o m b (m 3) is the number of distinct sets of three values, and, as we consider the case of a vector containing three distinct values, 1 varies from 1 to n ; 2 (hence P 1 1 n;2 ). There are C o m b (n 1 ) possibilities to place this value in the vector.

The number of occurrences 2 of the second greatest value (out of three) can vary from 1 to n ; 1 ; 1 (hence P 1 2 n; 1;1 ). Finally, there are Comb(n ; 1 2 ) different ways to select entries for that value in the vector. Once the two greatest values (out of three) have been placed in a vector, the entries for the third value are fully determined.

• Similarly we have: As in the previous cases, as soon as `; 3 values have been placed in a vector, the entries for the last value (the smallest value in the set of (`; 2) values to be placed) are fully determined.

• And finally

A `;1 = Comb(m `; 1) P 1 1 n;(`;2) C o m b (n 1 ) P 1 2 n; 1;(`;3) C o m b (n ; 1 2 ) P 1 `;2 n; 1; 2; ; `;3 ;1 Comb(n ; 1 ; ; `;3 `;2 ): Summing up A 1 + +A `;1 , using classical commutativity and associativity rules, and factoring terms, we obtain the formula A stated in the theorem 8 .

Determination of B

Let us now consider the number of vectors, generated by the function max `(), that have `or more distinct values. As before, let i denote the ith greatest value in the vector. As the vectors we consider now have at least `distinct values, we have the following possibilities for the `greatest values values 1 : : : `and their occurrence numbers 1 : : : `: 8 In the case of the vectors that contain exactly `; 1 distinct values, the formula A uses the fact that 1 + + `;2 + `;1 = n, i.e., `;1 = n ; ( 1 + + `;2 ), and then C o m b (n ; 1 ; ; `;2 `;1 ) = C o m b ( `;1 `;1 ) = 1 . This appears in the formula A in the case j = `; 1.

PI n ˚1870

Input vectors of C h 1 () I 1 = a a c d] h 1 (I 1 ) = fag I 2 = b b c d] h 1 (I 2 ) = fbg I 3 = a b c c] h 1 (I 3 ) = fcg I 4 = a b d d] h 1 (I 4 ) = fdg `; 1 2 `;1 `;2 ; 1 1 `;1 n ; 1 ; 2 ; ; `;2 ; 1 `1 ` `;1 ; 1 max(1 x + 1 ; 1 ; ; `;1 ) ` n ; 1 ; 2 ; ; `;1 Let us observe that 1 `is due to the fact that the vectors considered here contain at least `different values. Similarly, 2 `; 1 is due to the fact that the vectors whose greatest value is `contain `; 1 values different from `.

Etc. for 3 until `.

The value of 1 has not to bypass n ; (`; 1) in order to leave available enough entries of the vector for the other values (there are at least `; 1 such values). The same observation applies to each other value i , i `( 2 has not to bypass n ; 1 ; (`; 2), etc.)

On another side, `(the smallest of the `greatest values) has to be present enough in order these `values appear at least x + 1 times in a vector (this is required by the (x `)-density property). So, when x + 1 > ( 1 + + `;1 ), we need to have ` x+1;( 1 + + `;1 ). Hence, the lowest value that `can have is max(1 x +1; 1 ; ; `;1 ).

According to these observations on the values of i and i , 1 i `, the number of vectors with at least `distinct values is equal to the following "sigma of sigmas" quantity: P ` 1 m P 1 1 n;(`;1) Comb(n 1 ) P `;1 2 1;1 P 1 2 n; 1;(`;2) Comb(n ; 1 2 ) P `;2 3 2;1 P 1 3 n; 1; 2;(`;3) Comb(n ; 1 ; 2 3 ) P 1 `;1 `;2 ;1 P 1 `;1 n; 1; ; `;2 ;1 C o m b (n ; 1 ; ; `;2 `;1 ) P 1 ` `;1 ;1 P max(1 x+1; 1; ; `;1 ) ` n; 1; 2; ; `;1 C o m b (n ; 1 ; ; `;1 `) ( `; 1) n; 1; ; `:

The `greatest values used in a vector are 1 : : : `. So, given such a set of `values, the last term (namely, ( `; 1) n; 1; ; `) represents the number of different vectors that are due to the `; 1 remaining values (these values are smaller than or equal to `; 1). After rewriting this sum, we obtain the quantity denoted B in the statement of the theorem.

Theorem 13

Given a pair (x `), the value of NB(x `) can easily be computed using a mathematical software.

B (x `)-Legality vs (x + 1 + 1 ) -legality

Theorem 14 There are conditions that are (x `)-legal and not (x + 1 + 1 ) -legal.

Proof The proof consists in exhibiting a counter-example. Let us consider a system made up of n = 4 processes, and x = `= 1 .

Let C be the condition composed of the four vectors described in Table 1 and h 1 () the function defined in the second column of that table. It is easy to see that this function h 1 () is a recognizing function for C for the pair of parameters x = `= 1 , and consequently C is (1 1)-legal.

We show that C is not (2 2)-legal. To that end let us try to define an appropriate function h 2 ().

Irisa

• Definition of h 2 (I 1 ). As h 2 (I 1 ) has to include no more than two elements, we have a 2 h 2 (I 1 ) (otherwise the density property could not be satisfied). For the second element of h 2 (I 1 ), we have the choice between c or d.

We take arbitrarily h 2 (I 1 ) = fa cg. (Due to the symmetry relating I 1 and I 2 on one side, and I 3 and I 4 on the other side, if we had chosen h 2 (I 1 ) = fa dg, we should exchange the vectors I 3 and I 4 in the reasoning that follows.)

• Definition of h 2 (I 2 ). Trivially, h 2 (I 2 ) has to include b. To select the second element of h 2 (I 2 ), we have to take into account the fact d G (I 1 I 2 ) = 2 , in order the (2 2)-distance property be satisfied. As d G (I 1 I 2 ) = x; = 2 ) = 0 , we must have v2h `(I1 )\h `(I2) # v (I 1 \ I 2 ) > 0. It follows that c has to be selected, and we have consequently h 2 (I 2 ) = fb cg.

• Definition of h 2 (I 4 ). Similarly to the previous cases, h 2 (I 4 ) has to include d.

Moreover, as d G (I 1 I 4 ) = x ; = 2 (i.e., = 0 ), we must have v2h `(I1)\h `(I4 ) # v (I 1 \ I 4 ) > 0. It follows that h 2 (I 4 ) = fa dg.

But as d G (I 2 I 4 ) = x ; = 2 (i.e., = 0 ), we must also have v2h `(I2 )\h `(I4 ) # v (I 2 \ I 4 ) > 0, with means that h 2 (I 4 ) = fd cg. So, h 2 (I 4 ) has to equal to both fa dg and fd cg: an impossibility.

It follows that no recognizing function can be associated with C for x = `= 2 . The condition C is not (2 2)-legal.

2 Theorem 14

Theorem 15 Let 0 x < n ;1 and 0 < ` x. There are conditions that are (x+ 1 + 1 ) -legal and not (x `)-legal.

Proof As x and `are such that 0 < ` x < n ; • Different part: 1 j x ; `+ 1 ) I 1 j] = v 1 ^I2 j] = v 2 ^ ^I`+1 j] = v `+1 .

• Common part: 1 j n ; x + `; 1 ) I 1 x ; `+ 1 + j] = I `+1 x ; `+ 1 + j] = v j . It is easy to verify that C is (x + 1 + 1 ) -recognized by the function h `+1 () defined as follows: 8 j : h `+1 (I j ) = fv 1 v 2 : : : v `+1 g.

We now show that C is not (x `)-legal. The proof is by contradiction. Let us assume that there is an (x `)recognizing function g `() for C. For each vector I j 2 C (1 j `+ 1 ) we have v j 2 g `(I j ) (this follows from the fact that ` x and v j is the only value that appears more than once in I j ).

When we apply the (x `)-distance property to the whole set of vectors defining the condition, we have d G (I 1 : : : I `+1 ) = x;`+1 = x; . Consequently, the (x `)-recognizing function g `() is such that v2 T 1 j `+1 g `(Ij ) # v (\ 1 j `+1 I j ) > = `; 1 (Observation O). We have also the following.

• Due to (x `)-size property, each g `(I j ) has at most `values. Moroever, in order to have j T 1 j `+1 g `(I j )j = `, we need to have g `(I 1 ) = g `(I 2 ) = = g `(I `+1 ). But, these sets are not all equal because S 1 j `+1 g `(I j ) contains `+ 1 different values. It follows that the set T 1 j `+1 g `(I j ) contains at most `; 1 values.

• On another side, as (from the definition of the vectors) T 1 j `+1 I j = v 1 v 2 v n;x+`;1 ], that intersecting vector contains only distinct values.

It follows that v2 T 1 j `+1 h `(Ij ) # v (\ 1 j `+1 I j ) `; 1, which contradicts Observation O, and completes the proof.

Theorem 15

PI n ˚1870