<figure><img src="image_1.png" /></figure>

HAL
open science

# Optimal algorithms for synchronous Byzantine k-set agreement

Carole Delporte-Gallet, Hugues Fauconnier, Michel Raynal, Mouna Safir

► To cite this version:

Carole Delporte-Gallet, Hugues Fauconnier, Michel Raynal, Mouna Safir. Optimal algorithms for synchronous Byzantine k-set agreement. Theoretical Computer Science, 2023, 973, pp.114098. 10.1016/J.TCS.2023.114098. hal-04395355

HAL Id: hal-04395355

https://inria.hal.science/hal-04395355v1

Submitted on 1 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Algorithms for Synchronous Byzantine k-Set Agreement

Carole Delporte-Galletª, Hugues Fauconnierᵇ, Michel Raynalᶜ, Mouna Safirᵈ,ᵉ

ªIRIF, Université Paris Cité, Paris, France

ᵇIRIF, Université Paris Cité, Paris, France

ᶜIRISA, CNRS, Inria, Univ Rennes, 35042 Rennes, France

ᵈIRIF, Université Paris Cité, Paris, France

ᵉUM6P-CS, Université Mohammed VI Polytechnique, Ben Guerir, Maroc

## Abstract

This article is on k-set agreement (kSA) in an n-process synchronous message-passing system in which up to *t* processes can commit Byzantine failures. kSA is a decision problem in which at least each correct (i.e., non-Byzantine) process is assumed to propose and decide a value such that at most *k* different values are decided by the correct processes, in such a way that, if all the correct processes propose the same value *v*, they will decide *v*. This article investigates the possibility/impossibility domain of kSA in the presence of Byzantine processes. To this end it first extends a previous result and shows that kSA cannot be solved when ($n < 2t + \frac{t}{k}$) ∧ ($n - t \ge k + 1$). On the positive side, it presents two synchronous round-based algorithms that solve Byzantine kSA. These algorithms are optimal with respect to the value of *k* and the number of rounds. The first algorithm is a one-round algorithm that has two instances. The first assumes $n > 2t + 1$ and solves kSA for $k \ge \lfloor \frac{n-t}{n-2t} \rfloor + 1$, while the second assumes $n \le 2t + 1$ and solves kSA for $k \ge t + 1$ (so this second case does not require a majority of correct processes). The second algorithm is based on two new notions denoted Square and Regions that allow each correct process to locally build a global knowledge on which processes proposed which values. This algorithm has also two instances. The first assumes $n = 3t$ and solves 2SA. The second assumes $2t + 1 < n \le 3t$ and solves kSA where $k = \frac{n-t}{n-2t}$ is an integer. It is worth noticing that the results presented in this article "almost" complete the possibility/impossibility cartography of kSA in synchronous Byzantine systems. The only case that remains open is when $\frac{n-t}{n-2t}$ is not an integer.

**Keywords:** Agreement problem, Byzantine processes, Distributed algorithm,
6

7

Distributed computability, *k*-set agreement, Message-passing, Round-based algorithm, Synchronous system.

8

# 1. Introduction

9

10

11

12

13

14

The *k*-set agreement (*k*SA) problem was introduced in [5]. It is a natural generalization of the consensus problem (which corresponds to the case *k* = 1), namely, each process proposes a value, and the processes have to cooperate so that each non-faulty process decides a value in such a way that no more than *k* different values are decided. Moreover, the decided values have to ensure some validity property that depends on the failure process model.

15

16

17

18

19

20

21

22

23

24

25

26

27

28

*k*SA in different failure and communication models. In the crash failure model<fnref n="1" />, agreement problems are fundamental from both a practical and theoretical points of view. For *k* = 1 it has been proved to be *universal* [13, 14, 22] in the sense that, with the help of consensus, any service modeled by a sequential state machine [21, 24] can be replicated in such a way that despite process failures, we get a fault-tolerant distributed shared service. For *k* ≥ 1, where processes may decide up to *k* different values, that universality result may be extended: *k*SA enables us to implement *k* state machines with the guarantee that at least one of these machines progress forever [13, 22]. Moreover, it has been proved that the ability to solve *k*SA is related to *t*-resiliency in the sense that in asynchronous systems *k*SA is possible if and only if *k* is strictly greater than *t*, the maximal number of faulty processes (e.g. [7]). With some restrictions, these results apply to more severe failure models as Byzantine failure (with Byzantine failures a faulty process can do anything and acts as an unlimited adversary).

29

30

31

32

33

Depending on the failure model, variations on *k*SA lead to different definitions of the *validity* property that defines what are the values that can be decided. Several validity properties have been discussed (e.g. [18]). Considering crash failures, validity states that a decided value must be the value proposed by a process and the previously mentioned universality results hold for that definition.

34

35

36

Differently, for Byzantine failures, a value proposed by a Byzantine process can be meaningless and correct processes cannot distinguish between values proposed by faulty or correct processes. So the validity property considered in the

<footnote n="1">¹In the crash failure model a faulty process is a process that prematurely stops executing and a correct process is a process that does not stop executing before the end of its algorithm.</footnote>
Byzantine failure model is that the set of correct processes may choose at most *k* values with the constraint that, if all the correct processes propose the same value *v*, they can decide only only that value *v*. Note that, this validity property enables to implement a broadcast that ensures that, if the sender is correct, all the correct processes deliver that message, and if the sender is Byzantine, at most *k* different messages can be delivered by the correct processes.

The kSA problem has been studied in different failure models (crash, Byzantine) and communication models (synchronous, asynchronous). This article considers the Byzantine synchronous message passing model. More precisely, it is on the possibility and impossibility results depending on the value *k* and the number of processes *n*.

*Known results.* Let us first recall some known results. In the context of the asynchronous computing model with process crashes, it has been shown in [12] that consensus cannot be solved even if a single process may crash, and in [3, 15, 23] that kSA cannot be solved if *k* or more processes may crash.

The results are different in synchronous systems with process crashes. In synchronous systems with crash failures, consensus and the kSA become solvable. Hence the main issue does not concern computability but complexity, namely the lower bound on the number of synchronous rounds to achieve kSA. It is proved in [6] that ⌊*t*/*k*⌋ + 1 rounds are needed to solve kSA in synchronous systems.

With Byzantine failures, even in synchronous models, the kSA is not always solvable. The main purpose of this article is to discuss the kSA with Byzantine process failures in the classical fully connected synchronous message-passing computing model with authenticated reliable links [1, 21] and Byzantine failures. It is known from [19] that it is possible to solve 1SA (consensus) as long as $n \ge 3t + 1$. Being able to solve 1SA guarantees to solve kSA agreement for any *k*. It is shown in [4] that, in the synchronous Byzantine failure model, there is no algorithm solving kSA when $n \le 2t + \frac{t}{k}$. The present article refines this bound and shows that this is true only when $n - t \ge k + 1$, which completes the impossibility result for the case where $n - t < k + 1$.

*The results of this article made visual with three figures.* To explain the computability results presented in the article, let us consider $n = 18$ processes, $1 \le k, t < n$. Figure 1 presents the possibility result due to [19] (crosses), the impossibility result established in [4] (circles), and the cases that were unknown (?) before this article.

In fact that the impossibility proof presented in [4] is restricted to the case $n - t \ge k + 1$, as proved in [8] and in the current paper, which implies Figure 2.
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 1: Possibility result due to [19] and partial impossibility result for $n - t \ge k + 1$ due to [4]</figcaption></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /><figcaption>Figure 2: Refined impossibility results</figcaption></figure>

74

Finally, Figure 3 pieces together the new results of this paper with the results of [8] and [9].

75

As already mentioned the aim of this article is to reduce “as much as possible”

76
the area made up of "?". To this end, it presents two algorithms (green square full or hollow) to fill the "?" area, except for only one case, namely $2t + 1 < n \le 3t$ (this despite the fact that we show that ($\lfloor \frac{n-t}{n-2t} \rfloor + 1$)SA is achievable in one round and ($\lfloor \frac{n-t}{n-2t} \rfloor - 1$)SA is impossible to achieve). So only the case where $\frac{n-t}{n-2t}$ is not an integer remains an open problem. It is also shown that there is no algorithm in one round that can solve $\lfloor \frac{n-t}{n-2t} \rfloor$SA.

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>Figure 3: Summary of the possibility/impossibility results</figcaption></figure>

*Organization of the article.* The present article (which is an extended version of articles presented at the conferences SSS 2022 [9] and NETYS 2020 [8]) is organized as follows. Section 2 presents the computing model and the definitions of kSA. Section 3 presents a one-round algorithm that solves kSA in two different contexts: for $\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k$ when $n > 2t + 1$ and for $t + 1 \le k$ when $n \le 2t$. Section 4 presents a two-round algorithm that solves kSA in two different contexts: it solves 2SA when $n = 3t$, and solves kSA where $k = \frac{n-t}{n-2t}$ is an integer when instantiated in the failure context $2t + 1 < n \le 3t$. Section 5 completes the results of [4] concerning the impossibility of achieving kSA. Section 6 shows that the two proposed algorithms are optimal with respect to the number of rounds. It is worth noticing that the proposed algorithms introduce new notions (Square and Regions on matrices of values) which could be used in other Byzantine contexts. Roughly speaking Squares and Region capture a “second order” global knowledge
in which Squares allow a direct decision impose by the specification, and Regions allow to detect byzantine processes. Last but not least, it is worth noticing that, while the algorithms are very simple, some parts of their proofs are pretty technical. Finally, Section 7 concludes the article. Table 1 presented below summarizes the results from an algorithmic point of view.

<table><thead><tr><th>Algorithm</th><th>Constraint on n</th><th>Constraint on k</th></tr></thead><tbody><tr><td>One-round<br>(Section 3)</td><td>n &gt; 2t + 1<br>n &le; 2t + 1</td><td>&lfloor;n-t/n-2t&rceil; + 1 &le; k<br>t + 1 &le; k</td></tr><tr><td>Two-round<br>(Section 4)</td><td>n = 3t, t &gt; 1<br>n &le; 2t + 1 &lt; n &le; 3t</td><td>k = 2<br>k = n-t/(n-2t) is an integer</td></tr></tbody></table>

<table><caption>Table 1: Summary of the results</caption><tbody><tr><td>Impossibility<br>when</td><td>[(n - t ≥ k + 1) ∧ (n ≤ 2t + t/k)]<br>or [(n - t &lt; k + 1) ∧ (n ≤ 2t + 1) ∧ (k ≤ t)]</td></tr><tr><td>Open problem</td><td>when n ≤ 2t + 1 &lt; n ≤ 3t and n-t/(n-2t) is not an integer</td></tr></tbody></table>

## 2. Model and kSA

### 2.1. Computation Model

We consider a distributed synchronous, message-passing system with Byzantine failures. In this system, we have n sequential processes $\Pi = \{p_1, p_2, ..., p_n\}$ that communicate by message exchanges over a completely connected network. We assume at least 2 processes in the system ($n \ge 2$).

The system is synchronous, which means that the rate of the processes and the time to deliver a message are bounded by known bounds. We model the computation in this synchronous message passing system by a sequence of rounds.

Each round is composed of three consecutive steps, such that

1. Each (correct) process sends a message to all the processes,

2. Each (correct) process receives the messages sent to it during the current round,

3. Each (correct) process executes the same local computation (involving its current local state and the set of messages it received).
The fundamental property of the synchronous model lies in the fact that a message sent by a correct process to a correct process during a round is received and processed by its receiver during the very same round. This property provides the seed exploited by the correct processes in order to ensure termination.

A process that takes steps without deviating from its code, as defined by its algorithm, is said to be correct. A process that deviates from its code or stops taking steps is said to be faulty or Byzantine. The bad behavior of a Byzantine process can be intentional or not. As examples of Byzantine behaviors, a process may crash, fail to communicate, communicate fake values, communicate correctly with some processes and incorrectly with others, etc. Several Byzantine processes can also collude to "pollute" the computation. The letter $t$ denotes the maximum number of processes which may be Byzantine [17]. Let us notice that, at every round, a Byzantine process can send different messages –or no message at all– to different correct processes. We assume that there is at least one correct process i.e. $t < n$.

## 2.2. k-Set Agreement (kSA)

### 2.2.1. Definition

Let $V$ be a finite set of at least $k + 1$ values. Each process has an initial value $v$ in $V$ and *proposes* it to $k$SA. Each process has to irrevocably *decide* on a value. The decided values must satisfy the following properties.

* Validity. If all the correct processes propose the same value $v$, no correct process decides a value different from $v$.

* Agreement. At most $k$ different values are decided by the correct processes.

* Termination. Eventually, all the correct processes decide.

We say that an algorithm solves $k$SA in a system of $n$ processes in which at most $t < n$ processes can be Byzantine, if all its executions in this system satisfy the previous properties.

### 2.2.2. kSA solvability (wrt the value of $k$)

In a synchronous system prone to $t < n$ Byzantine failures, consensus (i.e., 1SA) is solvable only if $n > 3t$. So allowing multiple decided values makes it possible to tolerate more faults.
### 2.2.3. kSA and validity

The validity property has a profound impact on the solvability of kSA, as there exist variations of the validity property ([18]).

* Validity 1. The value decided by a correct process has been proposed by a process.

* Validity 2. The value decided by a correct process has been proposed by a correct process.

* Validity 3. If all the correct processes propose the same value $v$, no correct process decides a value different from $v$.

First of all notice that Validity 2 $\Rightarrow$ Validity 1 and Validity 2 $\Rightarrow$ Validity 3. Validity 1 is the validity of the kSA in the crash failure model. It is this validity that is considered in [5, 6]. But this validity is not achievable in the Byzantine failure model. Let us assume we have an algorithm that solves kSA ($k < n$ to avoid the trivial case). Consider a failure free run where all processes have different initial values. As $k < n$, there is a process $q$ that decides a value $v$ different from its initial value. By Validity 1, $v$ is the initial value of some process, say $p$. Let $w \in V$ be a value different from any initial value proposed in this run. Let us now consider a new run in which $p$ has $w$ as initial value, all the other processes have the same initial values as in the previous run. Process $p$ is Byzantine and pretends it has $v$ as initial value. All the processes send and receive the same messages as in the failure free run. So, the correct process $q$ decides $v$ that is not an initial proposed value.

We could strengthen this validity property and consider Validity 2. But this validity remains not achievable in Byzantine failure model. The argument is the same as for Validity 1 (in which a process $q$ can decide a value $v$ that is not the value of a correct process. So we consider a weaker validity than Validity 2 that is Validity 3 (which is also the validity property considered in [4]).

Note that Validity 3 (with Agreement and Termination) enables to implement a (terminating) k-broadcast primitive for which at most $k$ values may be delivered if the sender is not correct [16] and the proposed value if the sender is correct.

### 2.2.4. Validity property of kSA: crash model vs Byzantine model

Considering the synchronous crash failure model, it is shown in [6] that there is no kSA algorithm that would allow the processes to terminate in less than $\lfloor \frac{k}{t} \rfloor + 1$ rounds. While this could seem contradictory to our result, it is not. The answer lies
in the nature of the validity property in the crash failure model and the Byzantine failure model. The validity specifies which values can be decided by processes. In the case of crash failures, it states that the value output by a process is a value that has been proposed by a process. Differently, in the case of Byzantine failures, the validity property is weaker: it states that the value decided by the correct processes must be the same value $v$ if they all proposed value $v$. In the other cases, the value decided by a correct process is not required to be a proposed value (e.g., it can be a default value denoted $\perp$).

### 2.2.5. kSA efficiency (number of rounds)

A fundamental question associated with kSA concerns the minimal number of rounds that any algorithm has to execute in the worst case scenario where up to $t$ processes that may experiment failures (the time complexity of a synchronous algorithm usually measured as the maximal number of rounds it requires).

It has been shown, in the synchronous system with crash failures, that $\lfloor \frac{t}{k} \rfloor + 1$ is a lower bound on the number of rounds [6]. This means that, whatever the kSA algorithm, it is always possible to have a run of that algorithm that requires at least $\lfloor \frac{t}{k} \rfloor + 1$ rounds for the processes to decide. We show in this article that only one or two rounds are required to solve kSA in a synchronous system with Byzantine failures (this is made possible thanks to the validity property).

## 3. A One-round kSA Algorithm

This section presents a one-round synchronous algorithm which solves kSA in the presence of up to $t$ Byzantine processes when

$$ [(n > 2t + 1) \land (\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k)] \text{ or } [(n \le 2t + 1) \land (t < k)]. $$

### 3.1. Local data structures

Each process $p_i \in \Pi$ manages a local array $S_i[1..n]$ such that $S_i[i]$ is initialized to $p_i$'s initial value $v_i$ and, for any $j \ne i$, $S_i[j]$ is initialized to $\perp$. In the first round, $p_i$ sends $S_i[i]$, and updates $S_i[j]$ with the value received from $p_j$.

### 3.2. Algorithm of a process $p_i$

The code executed by each process $p_i$ is described in Algorithm 1. Each process $p_i$ executes only one round. It sends its input value $v_i$ and collects in $S_i$ all the values it receives from the other processes. Trivially, $p_i$ receives at least $n - t$ values (including its own value). If $n - t - 1$ received values are equal to $v_i$, $p_i$
210 decides $v_i$. When this previous condition is not fulfilled, by the Validity property, $p_i$ can decide any value. To avoid that many values are decided, $p_i$ a predefined default value $\perp \in V$.

(1) $S_i[i] \leftarrow v_i; \forall j \neq i \ S_i[j] \leftarrow \perp$; 
__________ round 1 __________

(2) send the value $S_i[i]$ to all the processes;

(3) **when** $p_i$ receives value $v$ from $p_j$ **do** $S_i[j] \leftarrow v$; 
__________ at the end of round 1 __________

(4) **if** $p_i$ finds $n-t$ values identical to $v_i$ in $S_i$

(5) **then** $\text{return}(v_i)$

(6) **else** $\text{return}(\perp)$

(7) **end if**.

<caption>Algorithm 1: One-round kSA algorithm executed by $p_i$</caption>

213 **3.3.** *Proof of Algorithm 1*

214 The following lemma follows directly from the code of the algorithm.

215 **Lemma 1.** *Algorithm 1 satisfies the termination and validity of kSA for any k.*

216 *Proof.* Termination: All the correct processes execute one synchronous round and decide at the end of that round.

217 Validity: If all correct processes propose the same value, say $v$, at the end of the (unique) round, a correct process $p_i$ has more than $n-t$ values identical to $v$, its initial value, in its local array $S_i$ and it decides $v$. $\square$

220 The number of values that are decided depend on how $n$ and $t$ are related.

221 **Lemma 2.** *If $n \le 2t+1$, Algorithm 1 solves kSA for $t+1 \le k$.*

222 *Proof.* We have the termination and the validity properties from Lemma 1. Let $e$ be any execution of the algorithm and $f$ the actual number of Byzantine processes in $e$ ($0 \le f \le t$). We show that, if $n \le 2t+1$, the correct processes in $e$ decide at most $t+1$ values. There are $n-f$ correct processes in $e$, there are two cases.

223 1. Case $n-f \le t+1$: there are at most $t+1$ correct processes and so at most $t+1$ value decided by correct processes.

228
2. Case $n - f > t + 1$: then $n - t \ge f + 2$. A correct process (Line 4) considers $n - t$ values, at least 2 of them come from correct processes. If it decides a non-$\perp$ value, there are at least two correct processes that proposed the same value. Consequently there are at most $\lfloor \frac{n-f}{2} \rfloor$ values different from $\perp$ decided by the correct processes. As $\perp$ may also be decided, there are at most $\lfloor \frac{n-f}{2} \rfloor + 1$ decided values. As $f \ge 0$, $\lfloor \frac{n-f}{2} \rfloor + 1 \le \lfloor \frac{n}{2} \rfloor + 1 \le t + 1$, proving that at most $t$ values different from $\perp$ are decided in $e$ by correct processes. $\square$

**Lemma 3.** If $n > 2t + 1$, Algorithm 1 solves kSA for $\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k$.

*Proof.* We have the termination and the validity from Lemma 1. Let $e$ be any execution of the algorithm. In $e$, there are at most $t$ Byzantine failures. Let $0 \le f \le t$ the actual number of Byzantine processes in $e$. We prove that if $n > 2t + 1$, the correct processes in $e$ decide at most $\lfloor \frac{n-t}{n-2t} \rfloor + 1$ values.

If a correct process $p$ decides a value $v$ different from $\perp$, then there are at least $n - t - f$ correct processes, including $p$, that have this value as input. Then at most $\lfloor \frac{n-t}{n-t-f} \rfloor$ values are decided by correct processes in $e$. The function $\lfloor \frac{n-f}{n-t-f} \rfloor$ of $f$ is growing, as $f \le t$ its maximum is for $f = t$, consequently at most $\lfloor \frac{n-t}{n-2t} \rfloor$ values different from $\perp$ are decided by correct processes in $e$. Moreover $\perp$ may be decided. $\square$

The following theorem follows from the previous lemmas.

**Theorem 1.** Algorithm 1 solves kSA in one round

* if $n > 2t + 1$, for $\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k$, or

* if $n \le 2t + 1$, for $t + 1 \le k$.

Let us observe that, whatever the value of $n$ and $t$, Algorithm 1 decides at least two values.

## 4. A Two-Round Algorithm

This section improves the result stated in Theorem 1 when

$$2t + 1 < n \le 3t \land k = \frac{n-t}{n-2t}.$$

To this end, it presents a two-round synchronous algorithm that solves kSA in the presence of up to $t$ Byzantine processes. This algorithm is presented in two steps.
• First step (simple case): assuming $n = 3t$ and $t > 1$, the algorithm solves 2SA,

• Second step (generalization): assuming $2t + 1 < n \le 3t$ and that $\frac{n-t}{n-2t}$ is an integer, the algorithm solves kSA for $k = \frac{n-t}{n-2t}$.

4.1. kSA for $n = 3t$, $k = 2$, and $t > 1$ (simple case)

4.1.1. Local data structures

Each process manages a local matrix $M_i[1..n][1..n]$, such that $M_i[i][i]$ is initialized to the value proposed by $p_i$ and all the other entries are initialized to $\perp$. In the first round each $p_i$ sends $M_i[i][i]$ to all the processes and assigns to $M_i[i][j]$ the value it receives from $p_j$. Then at the second round, each process $p_i$ broadcasts its $M_i[i][*]$ vector, and the received vectors from other processes are used to update the matrix $M_i$ as follows: $p_i$ receives from $p_j$ the vector $M$ that it stores it in $M_i[j][*]$. An example of $p_i$'s matrix $M_i$ is represented in Figure 4.

<figure><img src="image_9.png" /><figcaption>Figure 4: Matrix $M_i$</figcaption></figure>
### 4.1.2. Algorithm of a process $p_i$

A process $p_i$ first builds its local matrix (in two synchronous rounds) and then exploits its content to decide a value. The code executed by $p_i$ is described in Algorithm 2. It is self-explanatory as far as the rounds are concerned. The statement at the end of the second round (based on Squares and Regions) is developed in Section 4.1.4.

(1) $M_i[i][i] \leftarrow v_i$; **for all** $k, l \neq i$ **do** $M_i[j][k] \leftarrow \perp$ **end for**;
  __round 1__

(2) send the value $M_i[i][i]$ to all the processes;

(3) **when** $p_i$ receives value $v$ from $p_j$ **do** $M_i[i][j] \leftarrow v$;
  __round 2__

(4) send the vector $V_i = M_i[i][*]$ to all the processes;

(5) **when** $p_i$ receives a vector $V$ from $p_j$ **do** $M_i[j] \leftarrow V$;
  __at the end of round 2__

(6) **if** $p_i$ finds a Square or Regions in $M_i$

(7) **then** $\text{return}(v_i)$

(8) **else** $\text{return}(\perp)$

(9) **end if**.

<caption>Algorithm 2: Two-round kSA algorithm executed by $p_i$</caption>

### 4.1.3. Properties of a Matrix $M_i$

**Claim 1.** If $p_i$ and $p_j$ are two correct processes then, the row corresponding to process $p_j$ in $M_i$ and the one corresponding to $p_j$ in $M_j$ are equal: $M_i[j][*] = M_j[j][*]$.

*Proof.* Since $p_j$ is a correct process, it sends $M_j[j][*]$ to $p_i$ in the second round, and as $p_i$ is also a correct process, then it receives this vector and writes it in $M_i[j][*]$. Then: $M_i[j][*] = M_j[j][*]$. □

**Claim 2.** Let $p_i$, $p_j$ and $p_k$ be three correct processes. We have $M_i[k][*] = M_j[k][*]$.

*Proof.* Let $p_i$, $p_j$ and $p_k$ be three correct processes, then from the previous Claim we have: $M_i[k][*] = M_k[k][*]$ and $M_j[k][*] = M_k[k][*]$. This implies that $M_i[k][*] = M_j[k][*]$. Which means that $p_j$ and $p_i$ have the same vision on $p_k$. □
<figure><img src="image_10.png" /><figcaption>Figure 5: Matrix $M_3$ (Square example)</figcaption></figure>

<caption>Figure 6: Matrix $M_2$ (Regions example)</caption>

### 4.1.4. Basic Patterns: Squares and Regions

During the second round each process $p_i$ will analyze its matrix $M_i$ in order to decide. This analysis is based on patterns appearing in $M_i$, that we name *Square* and *Regions*. When a process finds one of the patterns, it will decide its own proposed value, otherwise, it will decide the default value $\perp$.

### 4.1.5. Finding a Square

We say that $p_i$ finds a Square $S$, when (1) there exists a subset $S$ of processes of size $n-t$ containing $p_i$, such that (2) for every two processes $p_j$ and $p_k$ of $S$, the value of $M_i[j][k]$ is equal to $M_i[i][i]$, i.e.,

$$1. |S| = n - t \text{ and } p_i \in S,$$

$$2. \forall p_j, p_k \in S, M_i[j][k] = M_i[i][i].$$

**Example:** Let us take $n = 6$, $t = 2$ and $k = 3$. $p_3$ is a correct process with proposed value $v_3$ and $M_3$ is its corresponding matrix as presented in Fig. 5. In this example $p_3$ finds the Square $S = \{p_1, p_2, p_3, p_6\}$.

### 4.1.6. Finding Regions ($R_1, R_2$)

We say that $p_i$ finds Regions ($R_1, R_2$), if it has not found a Square and there exist two subsets of $\Pi$, $R_1$ and $R_2$ such that:

$$1. p_i \in R_1,$$

$$2. |R_1| = |R_2| = t,$$

$$3. R_1 \cap R_2 = \emptyset,$$
$$313 \qquad 4. \forall k \in R_1, \forall \ell \in \Pi - R_2 : M_i[k][\ell] = v,$$

Since $p_i$ does not find a Square, one of the $M_i[k][\ell]$ values for $k \in R_1$ and $\ell \in R_2$ is different from $v$, let $w$ be that value.

$$316 \qquad 5. \forall k \in R_1, \ell \in R_2 : M_i[k][\ell] = w,$$

$$317 \qquad 6. \forall k \in R_2, \ell \in \Pi - R_1 : M_i[k][\ell] = w,$$

$$318 \qquad 7. \forall k \in R_2, \ell \in R_1 : M_i[k][\ell] = v.$$

If for every $k$ and $l$, $M_i[k][l]$ is equal to $v$, then $p_i$ finds a Square as it is not the case by hypothesis, there exists another value. Property (5) says that this value is unique. Properties (4) and (5) mean that all the lines corresponding to $R_1$ are equals between them. Properties (6) and (7) mean the same thing for $R_2$. From the properties (4) to (7), as soon as the lines corresponding to $R_1$ and $R_2$ are concerned, a column contains the same value but there is a disagreement regarding the column corresponding to $\Pi - R_2 - R_1$. These properties do not impose any conditions on the lines corresponding to $\Pi - R_2 - R_1$.

**Example:** Let us take $n = 6, t = 2$ and $k = 3$, suppose that $p_2$ is a correct process with initial value $v$ and that $M_2$ is its corresponding matrix, with the values represented in Fig. 6. In this example $p_2$ finds Regions $(R_1, R_2)$, with $R_1 = \{p_1, p_2\}$, and $R_2 = \{p_5, p_6\}$.

### 4.1.7. *Proof of Algorithm 2 for the simple case ($n = 3t, t > 1$ and $k = 2$)*

After the construction of its matrix, a process $p_i$ checks if its matrix contains a Square $S$. If it is the case, $p_i$ might be in an execution of the algorithm where all the processes of $S$, including itself, are correct and have the same initial value. As the size of $S$ is $n-t$, the $t$ remaining may be Byzantine. By validity, it has to decide its initial value. Consequently, if a process finds a Square it has to decide its initial value.

It may happen that in fact, we can have an execution, where some processes of $S$ are Byzantine and send a different vector at round two to another correct process $p_j$. In this case, even if $p_j$ has the same initial values as $p_i$, it does not find a Square. Since this execution is no longer compatible with an execution where all correct processes have the same initial value, the validity does not imply that it has to decide a particular value.

Let us now present an example of execution in the case where there are three sets of processes $A1, A2$, and $Byz$ of size $t$ (see the examples in Fig. 7, 8 and
9). The processes of A1 (processes $p_1$ and $p_2$) are correct and have $a_1$ as an initial value. The processes of A2 (processes $p_3$ and $p_4$) are correct and have $a_2$ as an initial value. The processes of *Byz* (processes $p_5$ and $p_6$) are Byzantine, they send $a1$ to processes of A1 pretending to have $a1$ as initial value and send $a2$ to processes of A2 pretending to have $a2$ as initial value. The processes of *Byz* sends to a process of A1, say $p_1$, that they received $a1$ from processes in A1 and *Byz*, and to a process of A2, say $p_2$, that they received $a2$ from processes in A2 and *Byz*. One process of *Byz* sends to another process of A1 (this is possible as $t > 1$), say $p_j$, that it has received from at least one process in A1 and *Byz* a value different from $a_1$. Process $p_1$ finds a Square and decides $a_1$ (Fig. 7), $p_2$ finds a Square and decides $a_2$ (Fig. 8), while $p_j$ does not find a Square. To achieve 2-set agreement it has to decide either $a_1$ or $a_2$. At this point the notion of Region is helpful. Process $p_j$ does not find a Square but it finds Regions ($A_1, A_2$) (Fig. 9). This pattern proves that the processes of *Byz* are Byzantine and have lied to produce a Square somewhere else and it decides $a_1$.

$$M_1 = \left( \begin{array}{c|c|c|c|c} a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_2 \end{array} \right)$$

<caption>Figure 7: $p_1$'s matrix: Square</caption>

$$M_2 = \left( \begin{array}{c|c|c|c|c} a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_2 \\ \hline a_1 & a_1 & a_2 & a_2 & a_2 \\ \hline * & * & a_2 & a_2 & a_2 \\ \hline * & * & a_2 & a_2 & a_2 \end{array} \right)$$

<caption>Figure 8: $p_2$'s matrix: Square</caption>

$$M_j = \left( \begin{array}{c|c|c|c|c} A_1 & A_2 & \text{Byz} & A_1 & A_2 \\ \hline a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_1 \\ \hline a_1 & a_1 & a_2 & a_2 & a_2 \\ \hline a_1 & a_1 & a_2 & a_2 & a_2 \\ \hline * & * & * & * & * \\ \hline * & * & * & * & * \end{array} \right)$$

<caption>Figure 9: $p_j$'s matrix: Regions</caption>
If a process does not find a Square or Regions it decides $⊥$. We show in the next lemmas that if two correct processes decide two different values different from $⊥$ by finding a Square or Regions then all the other processes will decide by Square or Regions one of these values. This achieves the agreement property of the 2-set agreement.

**Lemma 4.** If a correct process $p_i$ decides a value different from $⊥$, then it has found a Square or Regions, and it decides its initial value.

*Proof.* Let $p_i$ be a correct process, in the second round, $p_i$ analyses its corresponding matrix $M_i$. If it finds a Square or Regions it decides its initial value, otherwise $⊥$. These instructions correspond to Lines 6, 7 and 8 of Algorithm 2 □

**Lemma 5.** If a correct process $p_i$ finds a Square $S_i$, there is at least one subset of $S_i$ of size $t$ including only correct processes.

*Proof.* Let $p_i$ find a Square $S_i$ such that $|S_i| = n - t$. As there are at most $t$ Byzantine processes and $n = 3t$, it follows that at least $n - 2t = t$ processes in $S_i$ are correct. □

Let $R_3$ be $Π - R_2 - R_1$.

**Lemma 6.** If a correct process $p_i$ finds Regions $(R_1, R_2)$, then all the processes of $R_1$ are correct and (1) either all the processes of $R_3$ are Byzantine and all the processes of $R_2$ are correct, (2) or all the processes of $R_3$ are correct and all the processes of $R_2$ are Byzantine.

*Proof.* We have $n = 3t$, let $p_i$ be a correct process in $R_1$ that finds Regions $(R_1, R_2)$. By the definition of Regions (items 2 and 3), $R_1, R_2$ and $R_3$ contain $t$ processes and are disjoint.

If all the processes of $R_2$ are Byzantine since there are at most $t$ Byzantine processes and $|R_2| = t$, then processes of $R_1 \cup R_3$ are correct.

If a process of $R_2$ is correct, let $p_k$ be this process and let $p_ℓ$ be a process of $R_3$. By item 4, $p_i$ receives $v$ from $p_ℓ$ at the first round. By item 6, $p_k$ sends to $p_i$ at the second round $M_k$ with $M_k[ℓ] = w$, which is the value that $p_k$ pretends to have received from $p_ℓ$ at the first round. If both the processes are correct then $w = v$, but by the definition of Regions, we have $v \neq w$, since $p_k$ is correct then $p_ℓ$ is Byzantine. Then all processes in $R_3$ are Byzantine, because we have at most $t$ Byzantine and $|R_3| = t$, thus the processes of $R_1 \cup R_2$ are correct.

In general, either processes in $R_2$ are Byzantine and the processes of $R_1 \cup R_3$ are correct, or $R_3$ are Byzantine and the processes of $R_1 \cup R_2$ are correct. □
**Lemma 7.** If a correct process $p_i$ decides $v$ by Regions $(R_1, R_2)$, then all the processes of $R_1 \cup R_2$ are correct and the other processes are Byzantine.

*Proof.* If $p_i$ decides by Regions $(R_1, R_2)$, it means that it did not find a Square. By Lemma 6, processes of $R_1$ are correct and either processes of $R_2$ are Byzantine or processes of $R_3$ are Byzantine.

Since $p_i$ did not find a Square, an $M[k][\ell]$ value for some $p_k \in R_3$ and $p_\ell$ in $R_1 \cup R_3$ is different from $v$. Let $z$ be that value.

If $p_\ell$ belongs to $R_1 \setminus \{p_i\}$: by Lemma 6, $p_\ell$ is correct and consequently, it sends the same value $v$ to $p_i$ and $p_k$ at the first round, while $p_k$ sends $z$ to $p_i$ at the second round, as a received value from $p_\ell$. Therefore $p_k$ is Byzantine. Thus processes of $R_3$ are Byzantine and $R_1 \cup R_2$ are correct.

If $p_\ell$ is in $R_3$: $p_i$ received $v$ from $p_\ell$ at the first round, and $z$ from $p_k$ as a received value from $p_\ell$ at the second round. Thus at least one of the two processes $p_k$ and $p_\ell$ is Byzantine since they both belong to $R_3$ from Lemma 6, processes of $R_3$ are Byzantine and those of $R_1 \cup R_2$ are correct. $\square$

**Lemma 8.** If a correct process $p_i$ decides $v$ by a Square $S_i$, and another correct process $p_j$ decides $v'$ by a Square $S_j$, with $v \neq v'$, then all the correct processes decide either $v$ or $v'$.

*Proof.* Let $p_i$ (respectively $p_j$) be a correct process that finds a Square $S_i$ (resp. $S_j$) and let $v$ (resp. $v'$) be its initial value with $v \neq v'$. Let us show that every correct process decides either $v$ or $v'$.

By Lemma 5, there is a subset $SS_i$ of size $t$ of correct processes in $S_i$ and there is a subset $SS_j$ of size $t$ of correct processes in $S_j$. By item (2) of the definition of Square, all the processes in $SS_i$ have $v$ as an initial value and all the processes in $SS_j$ have $v'$.

Such that $v \neq v'$, $SS_i$ and $SS_j$ are disjoint and $|S_i \cap S_j| = t$.

A process in $S_i \cap S_j$ sent $v$ to the processes of $SS_i$, and $v'$ to those in $SS_j$, so this process is Byzantine. Consequently, correct processes are exactly $SS_i \cup SS_j$.

Let $p_k$ be a correct process, without loss of generality, assume that $p_k$ is in $SS_i$. As processes of $SS_i$ and $SS_j$ are correct, they send the same vector to $p_k$, $p_i$ and $p_j$ in the second round, which means that:

1. a correct process may, following its initial value, find the Square $S_i$ or the Square $S_j$,

2. if a correct process does not find a Square, it finds, following its initial value, at least Regions $(SS_i, SS_j)$ or Regions $(SS_j, SS_i)$ and decides its initial value.
So either a process decides by the Square or by Regions in both case it decides its initial value $v$ or $v'$. □

We are now ready to prove that for $n = 3t$ and $t > 1$ Algorithm 2 solves 2-set agreement in two rounds. In the following, we prove separately the three properties, namely Validity, Agreement, and Termination.

**Lemma 9.** [Validity] *If all the correct processes propose the same value, they decide this value.*

*Proof.* Let $C$ be the set of correct processes that propose $v$. Since we have at most $t$ Byzantine, then $|C| \ge 2t$. Let $p_i$ be a correct process, $S$ a subset of $C$ of size $2t$, $p_i \in S$. Then all the processes in $S$ have as initial value $v$ and send $v$ to all the processes in the first round. For every process $p_s$ in $S$ we have $M_s[s][s'] = v$ for all $s'$ in $S$ and that value will be send to $p_i$ at the second round, then $p_i$ will find at least the Square $S$, and whatever the Square it finds, it decides $v$, and all the processes in $C$ will decide $v$. □

**Lemma 10.** [Termination] *All the correct processes decide.*

*Proof.* All the correct processes will execute the two synchronous rounds and will decide at the end of the second round. □

**Lemma 11.** [Agreement] *At most two values are decided by correct processes.*

*Proof.* Let's suppose we have three decided values, then at least two of them are different from $\perp$. To show the agreement, we need to prove that if two values $v$ and $v'$ different from $\perp$ are decided, then all the correct processes decide $v$ or $v'$.

Let $p_i$ and $p_j$ be two correct processes that decide $v$ or $v'$ different from $\perp$ ($v \neq v'$), by Lemma 4, the decided values are their initial values.

* If $p_i$ and $p_j$ decide by a Square, then from Lemma 8, all the correct processes decide $v$ or $v'$. □

* Else without loss of generality assume that $p_i$ decides $v$ by Regions ($R_1, R_2$), $|R_1| = |R_2| = t$, $R_1 \cap R_2 = \emptyset$. Furthermore by Lemma 7, processes of $R_1 \cup R_2$ are correct and other processes are Byzantine.

By definition of Regions, a process in $R_1$ has $v$ as an initial value. As $p_j$ decides $v'$ its initial value is $v'$. As it is correct and not in $R_1$, it is in $R_2$. By the definition of Regions, all the processes of $R_2$ have $v'$ as an initial value.
462

463

Let $p_k$ be a correct process, then it is in $R_1$ or in $R_2$ and its initial value is $v$ or $v'$.

464

465

466

467

Either it finds a Square and decides its initial value $v$, or $p_k$ does not find a Square $S$, in this case $p_k$, finds Regions $(R_1, R_2)$ or $(R_2, R_1)$, because the correct processes of $R_1 \cup R_2$ send the same value to $p_i$ and to $p_k$. So $p_k$ decides its initial value $v$ or $v'$. ☐

<figure><img src="image_11.png" /></figure>

469

Finally, from Lemmas 9, 10 and 11, we have:

470

**Theorem 2.** For $n = 3t$ and $t > 1$, Algorithm 2 solves 2SA in two rounds.

471

4.2. $k$SA for $2t + 1 < n \le 3t$, $\frac{n-t}{n-2t}$ is integer and $k \ge \frac{n-t}{n-2t}$ (general case)

472

473

474

This section shows that Algorithm 2 works for $2t + 1 < n \le 3t$ when $\frac{n-t}{n-2t}$ is an integer. Its adaptation to this new setting only requires some modifications in the way Regions are found.

475

4.2.1. Finding Regions {$R_\ell : \ell = 1, \dots, k$}

476

477

We say that $p_i$ finds Regions {$R_\ell : \ell = 1, \dots, k$}, if it has not found a Square and there exist $k$ subsets of $\Pi$, $R_1, \dots, R_k$ such as:

478

1. $p_i \in R_1$,

479

2. $\forall \alpha \in \{1, \dots, k\}, |R_\alpha| = n - 2t$,

480

3. $\forall \alpha, \beta \in \{1, \dots, k\}$ and $\alpha \ne \beta$, $R_\alpha \cap R_\beta = \emptyset$, the Regions are disjoint,

481

482

4. $\forall \alpha \in \{1, \dots, k\}, \forall x, y \in R_\alpha, M_i[x][*] = M_i[y][*]$, the lines in each Region are equal,

483

484

5. $\forall \alpha \in \{1, \dots, k\}, \forall x, y, x', y' \in R_\alpha, M_i[x][y] = M_i[x'][y']$, all the values of a certain Region are equal,

485

Let $val.R_\alpha$ be the value of $M_i[x][y]$ for any $x, y \in R_\alpha$

486

487

6. $\forall \alpha, \beta \in \{1, \dots, k\}$ and $\alpha \ne \beta$, $val.R_\alpha \ne val.R_\beta$, the values of two Regions are different,

488

7. $\forall \alpha \in \{1, \dots, k\}, \forall y \in R_\alpha, \forall x \in \bigcup_{r=1}^k R_r, M_i[x][y] = val.R_\alpha,$
Let $\bar{R} = \Pi - \bigcup_{r=1}^k R_r$.

489

490

8. $\forall \alpha \in \{1, \dots, k\}, \forall x \in R_\alpha, \forall y \in \bar{R}, M_i[x][y] = val.R_\alpha$.
<figure><img src="image_12.png" /><figcaption>Figure 10: View of correct processes</figcaption></figure>

**Example:** Let us take $n = 10, t = 4$ and $k = 3$. Then process $p_1$ may find Regions $R_1, R_2$ and $R_3$ as depicted in Figure 10.

The idea behind "Finding a Square" is the same as that in the previous section. The Regions are defined in such a way that if $k$ correct processes decide $k$ different values by Square, then any other processes find Regions.

**Lemma 12.** If a correct process $p_i$ decides a value different from $\perp$, then it either finds a Square *S* or Regions {$R_\ell : \ell = 1, \dots, k$}, and it decides its initial value.

*Proof.* Let $p_i$ be a correct process, in the second round, $p_i$ has its own matrix $M_i$, and decides $\perp$ at line 8 if it did not find a Square or Regions at line 6. If it decides at line 7, it decides its own value. $\square$

**Lemma 13.** If a correct process $p_i$ finds Regions {$R_\ell : \ell = 1, \dots, k$}, the size of the subsets $\bar{R} = \Pi - \bigcup_{\ell=1}^k R_\ell$ and $\bigcup_{\ell \neq 1}^k R_\ell$ is $t$.

*Proof.* From condition 2 of the definition of Regions $|R_1| = n-2t$. By hypothesis of the studied case, we have $k = \frac{n-t}{n-2t}$ since the size of the Regions are equal (condition 2) and we have $k$ distinct Regions (condition 3) then: $|\bigcup_{\ell \neq 1}^k R_\ell| = (k-1)(n-2t) = t$ and $|\bar{R}| = n - k(n-2t) = t$. $\square$

**Lemma 14.** If a correct process $p_i$ decides by Regions {$R_\ell : \ell = 1, \dots, k$}, then all processes of $R_1$ are correct, and (1) either processes of $\bar{R} = \Pi - \bigcup_{\ell=1}^k R_\ell$ are
Byzantine and processes of $\bigcup_{l \neq 1} R_l$ are correct, or (2) processes of $\bar{R}$ are correct and processes of $\bigcup_{l \neq 1} R_l$ are Byzantine.

Proof. Let $p_i$ be a correct process that decides $v_i$ by Regions $\{R_l : l = 1, \dots, k\}$, let $T_1$ be the subset $\bigcup_{r \neq 1} R_l$. By definition of Regions $\{R_l : l = 1, \dots, k\}$, if $p_j$ is a correct process and $v_j$ is its initial value, from the condition 6 we have:

$$1. \quad \forall p_j \in T_1, v_j \neq v_i$$

From the fact that $p_j$ sends its initial value to $p_i$ and $p_i$ puts it in $M_i[i][j]$ and the condition 8, we have:

$$3. \quad \forall p_j \in \bar{R}, v_j = v_i.$$

If all processes of $T_1$ are Byzantine since there is at most $t$ Byzantine processes and by Lemma 13, $|T_1| = t$, then processes of $\bar{R}$ and $R_1$ are correct.

Otherwise, there is a correct process in $T_1$. Let $p_r$ be a correct process of $T_1$ and $p_m$ be a process of $\bar{R}$, $p_i$ receives $v_i$ from $p_m$ at the first round, and $v$ from $p_r$ at the second round that it puts in $M_i[r][*]$. As $p_r$ is correct, $M_i[r][m]$ is the value that $p_m$ sent to $p_r$ at the first round as its initial value, if $p_m$ is a correct process then $v' = v$ but by definition of Regions $v \neq v'$. Then all processes in $\bar{R}$ are Byzantine, since we have at most $t$ Byzantine and by Lemma 13, $|\bar{R}| = t$, then processes of $T_1$ and $R_1$ are correct.

So either processes in $T_1$ are Byzantine and processes of $\bar{R}$ and $R_1$ are correct, or processes of $\bar{R}$ are Byzantine and processes of $T_1$ and $R_1$ are correct. $\square$

**Lemma 15.** If a correct process $p_i$ decides by Regions $R_l$ (line 6), then all the processes of $\bigcup_{l=1}^k R_l$ are correct and the other are Byzantine.

Let us notice that it follows from this lemma that, if a process decides by Regions $R_l$, it knows which processes are Byzantine.

Proof. Let $p_i$ be a correct process that decides $v$ by Regions $R_l$. Let $S_1$ be the subset $\bigcup_{l \neq 1} R_l$.

By Lemma 14, processes of $R_1$ are correct and either processes of $S_1$ or $\bar{R}$ are Byzantine. By condition 6 and 8, if $p_i$ decides by a Square $S$, then $S = \bar{R} \cup R_1$. In this case for $p_k$ and $p_j$ in $R_1 \cup \bar{R}$, $M[k][j]$ is equal to $v$.

Since $p_i$ didn't find a Square, the conditions 4 and 5 imply that some $M[k][j]$ values for $p_k \in \bar{R}$ and $p_j$ in $R_1 \cup \bar{R}$ is different from $v$. Let $w$ be that value.

If $p_j \in R_1$ with $p_j \neq p_i$, since $p_j$ is correct, it sends the same value to $p_i$ and $p_k$ at the first round. $p_k$ sent $w$ instead of $v$ to $p_i$ at the second round, as the
542

543

received value from $p_j$, then $p_k$ is Byzantine. Thus processes of $\bar{R}$ are Byzantine and $R_1 \cup S_1$ are correct.

544

545

546

547

If $p_j \in \bar{R}$, then by condition 7, $p_i$ received $val.R_1$ from $p_j$ at the first round, and $w \neq val.R_1$ from $p_k$ as a received value from $p_j$ at the second round. Thus at least one of the two processes $p_k$ and $p_j$ is Byzantine, since they belong to $\bar{R}$ from Lemma 14, processes of $\bar{R}$ are Byzantine and those of $R_1 \cup S_1$ are correct. $\square$

548

549

550

**Lemma 16.** If $k$ correct processes decide distinct $\{v_\ell : \ell = 1, ..., k\}$ by Squares $S_\ell$, then all the correct processes will eventually decide one of the $v_\ell$ distinct values.

551

552

553

*Proof.* Let $\{p_i, i = 1, ..., k\}$ be $k$ different correct processes with their $k$ corresponding distinct initial values $\{v_i, i = 1, ..., k\}$ that decide there own value by finding a Square $\{S_i, i = 1, ..., k\}$ of size $n - t$. Then all these sets are disjoint.

554

555

556

As each set $S_i$ is of size $n - t$, there exists there are $k$ subsets $\{T_i, i = 1, ..., k\}$ of size $n - 2t$ of correct processes. As a process of $T_i$ and a process of $T_j$ have different initial value then: $\forall i, j; i \neq j \implies T_i \cap T_j = \emptyset$.

557

558

The size of $\cup_{g=1}^{g=k} T_g$ is $k(n - 2t)$, then $K = \Pi - \cup_{g=1}^{g=k} T_g$ is of size $t$. So for each $i$ from 1 to $k$, $S_i = T_i \cup K$.

559

560

A process of $K$ sends $v_1$ to $p_1$ in $T_1$ and $v_2$ to $p_2$ in $T_2$ ($k \ge 2$), so it is a Byzantine process.

561

562

563

Let us show that any correct process decides one of the $v_i$ values. By the claims of Section 4.1.3 (Identical lines), any two correct processes have the same rows for processes in $\cup_{g=1}^{g=k} T_g$.

564

By the Byzantine behavior of $K$, a correct process $p_i$ in $T_i$:

565

1. May find a Square $T_i \cup K$ and decides $v_i$,

566

567

2. If it does not find a Square, it finds the Regions thanks to the sets $\{T_i, i = 1, ..., k\}$.

568

569

570

571

**Example 1:** Let us take $n = 10, k = 3$ and $t = 4$. Let us consider three correct processes $p_1, p_2$ and $p_3$ with their respective distinct initial values $v_1, v_2$ and $v_3$, that decide by Squares $S_1, S_2$ and $S_3$ their initial values. Looking at the matrix of Fig. 11, if $v_\alpha = v_1$ (resp $v_2, v_3$) then this is process $p_1$'s matrix (resp $p_2, p_3$).

572

573

574

575

576

Let $p_\ell$ be a correct process, and let us suppose that $p_\ell \in S_1$ then it has as an initial value $v_1$. From the matrix, we can tell that each correct process will eventually find the Regions $R_\ell$ thanks to claims of Section 4.1.3 and decides its initial value. And by the Byzantine behavior of the faulty processes if $v_\alpha = v_1$ then $p_\ell$ will find a Square $S_1$ and decides $v_1$. $\square$
<figure><img src="image_13.png" /><figcaption>Figure 11: View of correct processes</figcaption></figure>

4.2.2. *Proof of Algorithm 2 when $2t + 1 < n \le 3t$ and $\frac{n-t}{n-2t}$ is an integer*

We are now ready to prove that when $2t + 1 < n \le 3t$ and $\frac{n-t}{n-2t}$ is an integer Algorithm 2 solves $(\frac{n-t}{n-2t})$SA. In the following, we separately prove each of the three properties defining $k$SA in the presence of Byzantine failures, (Validity, Termination, and Agreement).

**Lemma 17.** [Validity] *If all the correct processes propose the same value they decide it.*

*Proof.* Let $C$ be the set of correct processes that propose $v$. Since we have at most $t$ Byzantine, then $|C| \ge n - t$. Let $S$ be a subset of size $n - t$ of $C$. Let $p_i$ be a correct process. Let $S$ be a subset of size $n - t$ of $C$ that contains $p_i$. Then all the processes in $S$ have as initial value $v$ and sends $v$ to all the processes at the first round. All the processes $p_c$ in $S$ have $M_c[c][c'] = v$ for all $c'$ in $S$ and that value will be send to $p_i$ at the second round, then $M_i[c][c'] = v$ for all $c, c'$ in $S$ (including $p_i$). So we have:

(1) $S = n - t$ and $p_i \in S$, and

(2) $\forall c, c' \in S \ M_i[c][c'] = M_i[c][c']$.

Then $p_i$ finds at least the Square $S$ and whatever the Square it finds, it decides

$v$.

**Lemma 18.** [Termination] *All the correct processes decide.*

*Proof.* All the correct processes will execute the two synchronous rounds and will decide at the end of the second round.
**Lemma 19.** [Agreement] *At most *k* values are decided by correct processes.*

*Proof.* We prove this result by contradiction. Assume we have at least $k + 1$ decided values. Therefore $k$ of them are different from $\perp$. We will show that all correct processes decide one of these $k$ values. By Lemma 12, if a correct process decides some value different from $\perp$, it is its initial value. So we have $k$ processes, each process decides its initial value and all these values are different :

* If these $k$ processes decide different values by a Square, then from Lemma 16, all the correct processes decide one of the $k$ values.

* Else, if a correct process $p_i$ decides by Regions $R_\ell$, then by Lemma 15, processes of $\bigcup_{\ell=1}^k R_\ell$ are correct and the other processes are Byzantine.

Let $p_j$ be a correct process of $\bigcup_{\ell=1}^k R_\ell$ from Lemma 6, all the lines concerning processes in $\{R_\ell\}$ of $M_i$ are equal to the lines concerning processes in $\{R_\ell\}$ of $M_j$. If $p_j$ does not find a Square, it finds at least Regions $R_\ell$. In all the case it decides its initial value which is one of the $k$ values. $\square$

By Lemmas 17 and 18 and 19, we get the following theorem.

**Theorem 3.** *When $2t + 1 < n \le 3t$ and $\frac{n-t}{n-2t}$ is an integer, Algorithm 2 solves kSA for $k \ge \frac{n-t}{n-2t}$.*

**5. On the k Side: Impossibility Result**

This section focuses on the case where kSA is impossible to solve in the presence of *t* Byzantine processes. The starting point is [4], which demonstrates that:

**Theorem 4.** (From [4]) *There is no algorithm that solves kSA when $n \le 2t + \frac{t}{k}$.*

This theorem implies that there is no algorithm that solves kSA ($k < n$) when $n \le 2t$. But Section 3 has presented an algorithm that solves ($t + 1$)SA in the presence of up to *t* Byzantine processes.

To prove their theorem, the authors of [4] have partitioned the system of $n$ processes into ($k + 1$) subsets $S_1, ..., S_{k+1}$ of size $\lceil \frac{n-t}{k+1} \rceil$ or $\lfloor \frac{n-t}{k+1} \rfloor$ such that $\text{card}(\bigcup_{j=1}^{j=k+1} S_j) = n - t$. They show that, if $n \le 2t + t/k$, then each set $S_i$ is a subset of the correct processes and processes of $S_i$ decide a value $v_i$ (with $v_i \ne v_j$). However, they missed the point that this is only true if every set contains at least one process i.e. $\frac{n-t}{k+1} \ge 1$. In fact, their proof is for the revised version of their theorem, namely:
**Theorem 5.** (Revised version of [4]) If $n - t \ge k + 1$, there is no algorithm that solves kSA when $n \le 2t + \frac{t}{k}$.

The rest of this section extends the result of [4] to the case $n - t < k + 1$. Theorem 5, Theorem 6 and Theorem 3 show that our bound is tight when $n \le 2t + 1$.

**Theorem 6.** If $n - t < k + 1$ and $n \le 2t + 1$, there is no kSA algorithm that solves k-SA when $k \le t$.

*Proof.* If $n - t < k + 1$ and $n \le 2t + 1$, if there is a kSA algorithm, we prove that there is an execution of this algorithm where there are at least $t+1$ different values that are decided by correct processes, proving that $k \ge t + 1$. Consequently, there is no kSA algorithm if $k \le t$.

We proceed as in the proof stated in [4]. Let $\mathcal{A}$ be a kSA algorithm. Let $v_1, \dots, v_{t+1}$ be $t+1$ different values of $V$.

In our system, we assume $n > t$, then there exists $t+1$ non empty subsets of processes: $S_1 = \{p_1\}$, $S_2 = \{p_2\}$, \dots, $S_{t+1} = \{p_{t+1}\}$ of $\Pi$.

<figure><img src="image_14.png" /><figcaption>Figure 12: The behavior of the *t* Byzantine processes</figcaption></figure>

Let $\bar{S}_i$ be $(\cup_{j=1}^{j=t+1} S_j) \setminus S_i$. By construction $\bar{S}_i$ contains $t$ processes. As $n \le 2t+1$ then $\bar{S}_i$ contains at least $n-t-1$ processes. Let $F$ be $\Pi \setminus \cup_{i=1}^{i=t+1} S_i$. By construction $F$ contains $n-t-1$ processes. As $n \le 2t+1$, $F$ contains at most $t$ processes.
For each $i$ from 1 to $t+1$, the process of $S_i$ executes the algorithm $\mathcal{A}$ with input value $v_i$.

If $F$ is an empty set, we have $n = t+1$. Then for $p_i$, all processes in $\bar{S}_i$ may be Byzantine, to achieve Validity, $p_i$ has to decide its own values. Hence $t+1$ different values are decided by correct processes.

Assuming that $F$ is not an empty set. We specify the behavior of the Byzantine processes in $F$, as seen in Figure 12. The Byzantine processes in $F$ simulate $(t+1)$ sets of processes $F_1, \dots, F_{t+1}$, such that processes of each set $F_i$ execute correctly $\mathcal{A}$ with the input value $v_i$. Moreover, the processes of $F_i$ ignore the messages sent by $\bar{S}_i$ and receive those from $F_i \cup S_i$. Thus, the processes $F_i$ appear as being correct to $S_i$ and $\bar{S}_i$ appear to be Byzantine. Besides, the processes of $F_i$ ignore the messages sent by $\bar{S}_i$ and receive those from $F_i \cup S_i$.

As $\bar{S}_i$ contains $t$ processes and at least $n-t-1$ processes, and $F$ contains $n-t-1$ and at most $t$ processes, the process in $S_i$ cannot distinguish the case where the processes of $F$ are Byzantine and the processes of $S_i \cup \bar{S}_i$ are correct, and the case where processes of $\bar{S}_i$ are Byzantine and the processes of $F \cup S_i$ are correct. Consequently, by assumption, $\mathcal{A}$ is a $k$-SA algorithm, it follows from the Termination and the Validity properties that, for each $i$ from 1 to $t+1$, the correct processes in $S_i$ decide $v_i$. Consequently, $t+1$ different values are decided by correct processes. $\square$

Combining this result with the one in [4] it follows that there is no $k$SA algorithm when

$$ [(n - t \geq k + 1) \land (n \leq 2t + \frac{t}{k})] \text{ or } [(n - t < k + 1) \land (n \leq 2t + 1) \land (k \leq t)]. $$

## 6. Round Optimality

This section proves that the proposed algorithms are optimal in terms of the number of rounds. To this end, we first prove the two following lemmas.

**Lemma 20.** If a process has $v$ as initial value and receives $v$ from $n-t$ processes (including itself) then if it decides after one round, it decides $v$.

*Proof.* Let $p$ be a process, and $v$ be its initial value. $p$ has to decide in one round, if it receives $v$ from $n-t$ processes, it may be in an execution where these $n-t$ processes are correct, so by the validity of the $k$SA, it has to decide $v$. $\square$

**Lemma 21.** There is no $k$SA algorithm with 0 round.
*Proof.* By contradiction, let $\mathcal{A}$ be an algorithm that works in 0 round. A process $p_i$ decides based on its initial value, since it can be in an execution where processes have the same initial value, to ensure validity, it must decide its own value.

In an execution where the $n$ processes are correct, each decides its own value. If the values are different then there are $n$ different decided values, which doesn't achieve $k$SA as by definition $k < n$. $\square$

If $n \le 2t + 1$, it follows from Theorem 3 that Algorithm 1 solves $k$SA with $k \ge t + 1$ in one round. Theorems 5 and 6 show that this is optimal in terms of $k$SA. Lemma 21 shows that there is no algorithm for $k$SA in 0-round, and consequently Algorithm 1 is also optimal in terms of the number of rounds. Hence the following property.

**Property 1.** For $n \le 2t + 1$, Algorithm 1 is optimal in term of $k$SA and number of rounds.

If $n > 2t + 1$, by Theorem 3 it follows that Algorithm 1 solves $k$SA with $\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k$ in one round. Hence the following property.

**Property 2.** For $2t + 1 < n \le 3t$, there is no one-round $k$SA algorithm where $\frac{n-t}{n-2t}$ is an integer and $k = \frac{n-t}{n-2t}$.

*Proof.* Notice first that $2t + 1 < n \le 3t$ implies that $t > 1$ and $k = \frac{n-t}{n-2t}$ implies $k \ge 2$.

Let $X_i$, for $i$ from 1 to $2k-1$, be disjoint sets of processes of size $n-2t \ge 2$, such that $\Pi = \bigcup_{i=1}^{2k-1} X_i$. Let $x_i$, for $i$ from 1 to $2k-1$, be $2k-1$ distinct values. Each process of the set $X_i$ has the initial value $x_i$.

Let $e$ be an execution where all the processes are correct and propose $2k-1$ values, but decide at most $k$ values to ensure $k$SA. We have then $k-1$ non-decided values among the $2k-1$ values, let $K$ be the set of non-decided values and $L$ be the set of decided values. $Z = \bigcup_{j=1}^{k-1} X_{ij}$ is the set of processes with their initial values in $K = \{x_{i_1}, x_{i_2}, \dots, x_{i_{k-1}}\}$.

Let $a$ and $b$ be two correct processes of $X_{i_1}$. If $b$ decides a value $w$ that is not in $K \cup L$ (not an initial value of some set $X_i$) then let $X_{i_k}$ be some set with initial values in $L$. If $b$ decides a value $w$ of $L$, as $k \ge 2$, $L$ contains at least 2 values. Let $X_{i_k}$ be a set of processes that have an initial value in $L \setminus \{w\}$. $Z' = \bigcup_{j=1}^{k} X_{ij}$. The size of $Z'$ is $k(n-2t) = n-t$.

We consider $k$ executions $\alpha_j$, $j = \{1, \dots, k\}$, where all processes are correct and in execution $\alpha_j$ the processes of the set $X_{ij}$ have $x_{ij}$ as initial value and the $t$
## 7. Conclusion

<footnote>processes of $\Pi \setminus Z'$ have $x_{ij}$. By lemma 20 each process of the set $X_{ij}$ will decide its initial value.</footnote>

<footnote>Let $\beta$ be an execution where the processes of the set $X_{ij}$ propose their initial value and each process in $X_i \subseteq \Pi \setminus Z'$ proposes as initial value $x_{ij}$ to processes of $X_{ij}$ except to the process $b$ for which it proposes $x_i$.</footnote>

<footnote>In this execution processes of $\Pi \setminus Z'$ are Byzantine, for $j$ from 2 to $k$: the executions $\beta$ and $\alpha_j$ are indistinguishable for each process of $X_{ij}$ and they decide $x_{ij}$.</footnote>

<footnote>For the process $a$: the executions $\beta$ and $\alpha_1$ are indistinguishable and it decides $x_{i_1}$.</footnote>

<footnote>For the process $b$: the executions $\beta$ and $e$ are indistinguishable and it decides $w$.</footnote>

<footnote>By construction all these values are different. Consequently, we will have $k+1$ decided values instead of $k$. $\square$</footnote>

<footnote>If $\frac{n-t}{n-2t}$ is an integer, Algorithm 2 solves $k$SA with $k = \frac{n-t}{n-2t}$ in two rounds. By Theorem 5, it is impossible to achieve $(\frac{t}{n-2t})$SA when we have $2t + 1 < n \le 3t$. Note that $\frac{t}{n-2t} = \frac{n-t}{n-2t} - 1$. So Algorithm 2 is optimal in terms of set agreement. By Property 2, there is no one-round algorithm for $(\frac{t}{n-2t})$SA, then Algorithm 2 is optimal also in term of number of rounds.</footnote>

<footnote>**Theorem 7.** When $2t + 1 < n \le 3t$ and $\frac{n-t}{n-2t}$ is an integer, Algorithm 2 is optimal in term of set agreement and number of rounds.</footnote>

<footnote>When $n > 3t$, there exists an algorithm in [2] that solves 1SA in $t + 1$ rounds that is optimal in term of set and number of rounds [10].</footnote>

<footnote>This article was on $k$-set agreement (kSA) in $n$-process synchronous systems in which up to $t$ processes can commit Byzantine failures. It has presented com- putability (possibility/impossibility) results and two algorithms.</footnote>

<footnote>The first algorithm is a one-round algorithm that solves $k$SA for the following cases defined by domain values for $t$ and $k$:</footnote>

<footnote n="1">1. $(n > 2t + 1) \land (\lfloor \frac{n-t}{n-2t} \rfloor + 1 \le k)$,</footnote>

<footnote n="2">2. $(n \le 2t + 1) \land (t + 1 \le k)$.</footnote>

<footnote>The second algorithm is a two-round algorithm solving 2SA in a system of $n = 3t$ processes in which up to $t > 1$ processes may be Byzantine. This algorithm</footnote>
is based on new notions (Square and Regions) which allow each process $p_i$ to capture a “second order” global knowledge (namely, “$p_i$ knows that $p_j$ knows the value proposed by $p_k$”). Extending the notion of Regions, it has been shown that the same two-round algorithm solves Byzantine kSA for the case where $k = \frac{n-t}{n-2t}$ is a positive integer, in a system such that $2t + 1 < n \le 3t$. While the statement of the algorithm is relatively simple, its proofs (based on the notions of Squares and Regions) are not.

For $k > 1$, the proposed algorithms use 1 or 2 rounds, which has been shown to be optimal. Finally, it has also been shown that if $n-t < k+1$ and $n \le 2t+1$, there is no algorithm that solves kSA when $k \le t$.

Combining the results of this article with the results presented in [4], this article “nearly close” the solvability (possibility/impossibility) of Byzantine kSA in synchronous message-passing systems. More precisely, the only remaining case is when $\frac{n-t}{n-2t}$ is not an integer, for which it is not known whether ($\lfloor \frac{n-t}{n-2t} \rfloor$)SA is solvable (while the case ($\lfloor \frac{n-t}{n-2t} \rfloor + 1$)SA can be solved in one round, and it is impossible to solve ($\lfloor \frac{n-t}{n-2t} \rfloor - 1$)SA. The algorithmic results of the article have been summarized in Table 1.

## Acknowledgments

The authors want to thank the referees for their constructive comments that helped them improve the presentation of the article.

C. Delporte-Gallet, H. Fauconnier and M. Safir have been partially supported by the ANR French projects DUCAT (ANR-20-CE48-0006) on Distributed Network Computing through the Lens of Combinatorial Topology, and FREDDA (ANR-17-CE40-0013) devoted to the development of formal methods in order to improve and ease the design of distributed algorithms.

M. Raynal has been partially supported by the ANR French projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81) devoted to the modular design of building blocks for large-scale Byzantine-tolerant applications.

## References

[1] Attiya H. and Welch J., *Distributed computing, fundamentals, simulation and advanced topics.* (Second edition). Wiley Series on Parallel and Distributed Computing, 414 pages (2004)
776
777
778

[2] Bar-Noy A., Dolev D., Dwork C. and Strong R., Shifting gears: changing algorithms on the fly to expedite Byzantine agreement. *Information and Computation*, 97(2):205-233 (1992)

779
780
781

[3] Borowsky E. and Gafni E., Generalized FLP impossibility results for t-resilient asynchronous computations. *Proc. 25th ACM Symposium on Theory of Computing (STOC'93)*, ACM Press, pp. 91-100 (1993)

782
783

[4] Bouzid Z., Imbs D., and Raynal M., A necessary condition for Byzantine k-set agreement. *Information Processing Letters*, 116(12):757-759 (2016)

784
785

[5] Chaudhuri S., More choices allow more faults: set consensus problems in totally asynchronous systems. *Information and Computation*, 105(1):132-158 (1993)

786
787

[6] Chaudhuri S., Herlihy M., Lynch N., and Tuttle M., Tight bounds for k-set agreement. *Journal of the ACM*, 47(5):912-943 (2000)

788
789

[7] Delporte-Gallet C., Fauconnier H., Guerraoui R and Tielmann A: The disagreement power of an adversary. *Distributed Computing*, 24(3-4):137-147 (2011)

790
791
792

[8] Delporte-Gallet C., Fauconnier H., and Safir M., Byzantine k-set agreement. *Proc. 8th Int'l Conference on Networked Systems (NETYS'20)*, Springer LNCS 12129, pp. 183-191 (2020)

793
794
795

[9] Delporte-Gallet C., Fauconnier H., Raynal M. and Safir M., Optimal algorithms for synchronous Byzantine k-set agreement. *Proc. 24th International Symposium, SSS'22*, Springer LNCS 13751, pp. 178-192, (2022)

796
797

[10] Dwork C. and Moses Y., Knowledge and common knowledge in a Byzantine environment: crash Failures. *Information and Computation*, 88(2):156-186 (1990)

798
799

[11] Fischer M.J. and Lynch N.A, A Lower Bound for the time to assure interactive consistency. *Information Processing Letters*, 14(4):183-186 (1982)

800
801

[12] Fischer M.J., Lynch N.A. and Paterson M.S., Impossibility of distributed consensus with one faulty process. *Journal of the ACM*, 32(2):374-382 (1985)

802
803
804

[13] Gafni E. and Guerraoui R., Generalizing universality. *Proc. 22nd Int'l Conference on Concurrency Theory (CONCUR'11)*, Springer LNCS 6901, pp. 17-27 (2011)

805
806

[14] Herlihy M., Wait-Free Synchronization. *ACM Transactions on Programming Languages and Systems*, 13(1):124-149 (1991)
807

808

[15] Herlihy M.P. and Shavit N., The topological structure of asynchronous com- putability. *Journal of the ACM*, 46(6):858-923 (1999)

809

810

811

[16] Imbs D., Mostéfaoui A., Perrin M. and Raynal M., Which Broadcast Ab- straction Captures k-Set Agreement? *Proc. 31st International Symposium on Distributed Computing (DISC2017)* 27:1–27:16 (2017)

812

813

814

[17] Lamport L., Shostack R. and Pease M., The Byzantine generals problem. *ACM Transactions on Programming Languages and Systems*, 4(3)-382-401 (1982)

815

816

[18] De Prisco R., Malkhi D. and Reiter M.K. On k-Set Consensus Problems in Asynchronous Systems. *IEEE Trans. Parallel Distributed Syst.* 7-21 ( 2001)

817

818

[19] Pease M., Shostack R. and Lamport L., Reaching agreement in the presence of Faults *Journal of the ACM*, 27(2):228–234 (1980)

819

820

[20] Raynal M., *Distributed algorithms for message-passing systems*. Springer, 510 pages, ISBN 978-3-642-38122-5 (2013)

821

822

[21] Raynal M., *Fault-tolerant message-passing distributed systems: an algorithmic approach*. Springer, 480 pages, ISBN 978-3-319-94140-0 (2018)

823

824

[22] Raynal M., Stainer J., and Taubenfeld G., Distributed universality. *Algorithmica*, 76(2):502-535 (2016)

825

826

827

[23] Saks M. and Zaharoglou F., Wait-free k-set agreement is impossible: the topology of public knowledge. *SIAM Journal on Computing*, 29(5):1449-1483 (2000)

828

829

[24] Schneider F.B., *Implementing fault-tolerant services using the state machine approach: a tutorial*, ACM Computing Survey, 22(4):299–319 (1990)

830

831

832

[25] Wuu G.T.J. and Bernstein A.J., Efficient solutions to the replicated log and dictionary problems. *Proc. 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC'84)*, ACM Press, pp. 233–242 (1984)