# All Byzantine Agreement Problems are Expensive

Pierre Civit  École Polytechnique Fédérale de Lausanne (EPFL)Switzerland ,
Seth Gilbert  NUS SingaporeSingapore ,  Rachid Guerraoui  École Polytechnique
Fédérale de Lausanne (EPFL)Switzerland ,  Jovan Komatovic  École Polytechnique
Fédérale de Lausanne (EPFL)Switzerland ,  Anton Paramonov  École Polytechnique
Fédérale de Lausanne (EPFL)Switzerland and  Manuel Vidigueira  École
Polytechnique Fédérale de Lausanne (EPFL)Switzerland

††copyright: none††conference: ACM Conference on Computer and Communications
Security; Due 06 May 2021; London, TBD††journalyear: 2019

Byzantine agreement, arguably the most fundamental problem in distributed
computing, operates among $n$ processes, out of which $t<n$ can exhibit
arbitrary failures. The problem states that all correct (non-faulty) processes
must eventually decide (termination) the same value (agreement) from a set of
admissible values defined by the proposals of the processes (validity).
Depending on the exact version of the validity property, Byzantine agreement
comes in different forms, from Byzantine broadcast to strong and weak
consensus, to modern variants of the problem introduced in today’s blockchain
systems. Regardless of the specific flavor of the agreement problem, its
communication cost is a fundamental metric whose improvement has been the
focus of decades of research. The Dolev-Reischuk bound, one of the most
celebrated results in distributed computing, proved 40 years ago that, at
least for Byzantine broadcast, no deterministic solution can do better than
$\Omega(t^{2})$ exchanged messages in the worst case. Since then, it remained
unknown whether the quadratic lower bound extends to seemingly weaker variants
of Byzantine agreement. This paper answers the question in the affirmative,
closing this long-standing open problem. Namely, we prove that _any_ non-
trivial agreement problem requires $\Omega(t^{2})$ messages to be exchanged in
the worst case. To prove the general lower bound, we determine the weakest
Byzantine agreement problem and show, via a novel indistinguishability
argument, that it incurs $\Omega(t^{2})$ exchanged messages.

##  1\. Introduction

Byzantine agreement (LSP82, ) is a foundational problem of distributed
computing. Its importance stems from the fact that Byzantine agreement lies at
the heart of state machine replication (CL02, ; adya2002farsite, ;
abd2005fault, ; kotla2004high, ; veronese2011efficient, ; amir2006scaling, ;
kotla2007zyzzyva, ; malkhi2019flexible, ; momose2021multi, ), distributed key
generation (AbrahamJMMST21, ; ShresthaBKN21, ; Kokoris-KogiasM20, ;
DasYXMK022, ), secure multi-party computation (DBLP:conf/tcc/DeligiosHL21, ;
DBLP:conf/eurocrypt/FitziGMR02, ; DBLP:conf/crypto/GennaroIKR02, ), as well as
various distributed services (galil1987cryptographic, ; gilbert2010rambo, ).
Recent years have witnessed a renewed interest in Byzantine agreement due to
the emergence of blockchain systems (abraham2016solida, ; chen2016algorand, ;
abraham2016solidus, ; luu2015scp, ; correia2019byzantine, ; CGL18, ;
buchman2016tendermint, ). Formally, the agreement problem is defined in a
distributed system of $n$ processes; up to $t<n$ processes can be _faulty_ ,
whereas the rest are _correct_. Correct processes behave according to the
prescribed deterministic protocol; faulty processes can deviate arbitrarily
from it. Byzantine agreement exposes the following interface:

  * •

input $\mathsf{propose}(v\in\mathcal{V}_{I})$: a process proposes a value $v$
from a (potentially infinite) set $\mathcal{V}_{I}$.

  * •

output $\mathsf{decide}(v^{\prime}\in\mathcal{V}_{O})$: a process decides a
value $v^{\prime}$ from a (potentially infinite) set $\mathcal{V}_{O}$.

Byzantine agreement ensures the following properties:

  * •

_Termination:_ Every correct process eventually decides.

  * •

_Agreement:_ No two correct processes decide different values.

To preclude a trivial solution in which processes agree on a predetermined
value, Byzantine agreement requires an additional property – _validity_ – that
specifies which decisions are admissible.

The exact definition of the validity property yields a specific agreement
problem. For example, Byzantine broadcast (Wan2020, ; Wan2023a, ;
abraham2021good, ; Nayak2020a, ) ensures _Sender Validity_ , i.e., if the
predetermined sender is correct, then its proposed value must be decided by a
correct process. Weak consensus (yin2019hotstuff, ; lewis2022quadratic, ;
civit2022byzantine, ; BKM19, ) guarantees only _Weak Validity_ , i.e., if all
processes are correct and they all propose the same value, that value is the
sole admissible decision. Other notable Byzantine agreement problems include
(1) strong consensus (LSP82, ; civit2022byzantine, ; CGL18, ), ensuring that,
if all correct processes propose the same value, that value must be decided,
(2) interactive consistency (LSP82, ; fischer1981lower, ; ben2003resilient, ),
where correct processes agree on the proposals of all $n$ processes, and (3)
agreement problems employed in today’s blockchain systems (Cachin2001, ;
BKM19, ; yin2019hotstuff, ), which require the decided value to satisfy a
globally verifiable condition (e.g., the value is a transaction correctly
signed by the issuing client).

##### The worst-case communication cost of Byzantine agreement

Motivated by practical implications, one of the most studied aspects of
Byzantine agreement is its communication cost. Since the inception of
Byzantine agreement, research has been focused on minimizing the number of
exchanged bits of information (dolev1985bounds, ; validity_podc, ;
lewis2022quadratic, ; wan2023amortized, ; civit2022byzantine, ;
everyBitCounts, ; DBLP:journals/iandc/CoanW92, ; berman1992bit, ; Chen2021, ;
Nayak2020a, ; Abraham2023a, ). However, there are intrinsic limits. The
seminal Dolev-Reischuk bound (dolev1985bounds, ) proves that Byzantine
broadcast cannot be solved unless $\Omega(t^{2})$ messages are exchanged in
the worst case. (This naturally applies to any problem to which Byzantine
broadcast can be reduced with $o(t^{2})$ messages.) The result of
(dolev1985bounds, ) is shown for any Byzantine broadcast algorithm that
operates in _synchrony_ , where the message delays are known. Inherently, this
lower bound applies to weaker network models as well. Concretely, it extends
to _partial synchrony_ (DLS88, ), in which the communication is asynchronous
(with arbitrary message delays) until some unknown point in time, after which
it becomes synchronous. (Byzantine agreement is known to be unsolvable in full
asynchrony (fischer1985impossibility, ).)

While the Dolev-Reishcuk bound answers the question of what the necessary
message cost is for Byzantine broadcast, it is not general, i.e., it does not
hold for _any_ specific non-trivial agreement problem. (An agreement problem
is trivial if there exists an always-admissible value that can be decided
immediately, i.e., without any communication.) For instance, the Dolev-
Reischuk bound does not apply to weak consensus. Thus, whether all non-trivial
agreement problems require a quadratic number of messages remains unknown. In
this paper, we answer this long-standing question in the affirmative.

###### Theorem 1.

No (non-trivial) Byzantine agreement problem can be solved with fewer than
$\Omega(t^{2})$ exchanged messages in the worst case even in synchrony.

To prove our general lower bound, we study binary
($\mathcal{V}_{I}=\mathcal{V}_{O}=\\{0,1\\}$) weak consensus in synchrony.
Namely, we first prove an $\Omega(t^{2})$ lower bound on the number of
exchanged messages for weak consensus. Then, to generalize the bound, we prove
that weak consensus is the weakest agreement problem by presenting a reduction
from it to any (solvable and non-trivial) agreement problem. As a byproduct,
the reduction allows us to define the entire landscape of solvable (and
unsolvable) agreement problems, thus unifying all previous results on the
solvability of Byzantine agreement. (We believe this result to be important in
its own right.)

##### The fundamental challenge of weak consensus

Recall that the _Weak Validity_ property of weak consensus guarantees only
that, if all processes are correct and they all propose the same value, that
value must be decided. This is a very weak requirement: picking $1$ as the
decision is always allowed except in a _single_ execution $\mathcal{E}$ where
all processes are correct and they all propose $0$. Hence, any weak consensus
algorithm needs only to distinguish _two_ scenarios: either the execution is
(1) $\mathcal{E}$, deciding $0$, or (2) non-$\mathcal{E}$, deciding $1$. This
observation was the starting point for our conjecture that weak consensus is
the _weakest_ (non-trivial) agreement problem (which we prove in this paper),
implying that any lower bound for weak consensus also applies to all other
agreement problems.

To illustrate the difficulty of proving a quadratic lower bound for weak
consensus, we briefly discuss the common point in the classical proof
techniques exploited for similar results (namely, (dolev1985bounds, ) and
(validity_podc, )) and explain why those techniques cannot be easily adapted
to weak consensus in synchrony. The crux of those proof techniques consists in
showing that, unless $\Omega(t^{2})$ messages are exchanged, there necessarily
exists an execution $\mathcal{E}_{1}$ in which some correct process $p$
decides $1$ without receiving any message. The second step of the proof
consists of constructing another execution $\mathcal{E}_{0}$ in which (1) $p$
is correct and receives no messages, and (2) some correct process $q\neq p$
decides $0$. As $p$ cannot distinguish $\mathcal{E}_{0}$ from
$\mathcal{E}_{1}$, $p$ decides $1$ in $\mathcal{E}_{0}$, thus violating
_Agreement_. Unfortunately, while elegant, this approach cannot be directly
adapted to weak consensus in synchrony as both $\mathcal{E}_{0}$ and
$\mathcal{E}_{1}$ inevitably contain detectable faults. Therefore, nothing
prevents a weak consensus algorithm from deciding $1$ in _both_
$\mathcal{E}_{0}$ and $\mathcal{E}_{1}$, making the aforementioned reasoning
inapplicable. Intuitively, the main difficulty in proving a quadratic lower
bound for weak consensus is that _any_ detectable misbehavior immediately
allows an algorithm to choose a predetermined “default” value.

##### Technical overview.

To prove an $\Omega(t^{2})$ lower bound for weak consensus in the Byzantine
failure model, we show that the bound holds even with only _omission_
failures. An omission-faulty process can only misbehave by failing to receive
or send some messages, but not by behaving maliciously. (In contrast to
Byzantine processes, it is reasonable to make claims about the behavior of
omission-faulty processes as they are still _honest_ , i.e., they never act
malevolently.) Our proof utilizes in a novel way the standard concept of
_isolation_ (dolev1985bounds, ; validity_podc, ; AbrahamStern22, ;
Abraham2023revisited, ; Abraham2019c, ; hadzilacos1991message, ), in which a
small subset of omission-faulty processes starts (from some round onward)
“dropping” all messages received from outside the set. Concretely, we obtain
our bound through a sequence of four critical observations about what happens
when _multiple_ groups of processes are isolated. Suppose that there are three
groups: group $A$, which is fully correct and sends $o(t^{2})$ messages, and
groups $B$ and $C$, which are (separately) isolated from rounds $k_{B}$ and
$k_{C}$, respectively. We observe that:

  1. (1)

In any execution in which group $B$ (resp., $C$) is isolated, correct
processes from $A$ and a majority of processes from $B$ (resp., $C$) must
decide the _same_ bit; otherwise, we could design an execution which violates
the properties of weak consensus.

  2. (2)

If both $B$ and $C$ are isolated from round $1$, group $A$ must decide some
“default” bit _independently_ of their proposals, i.e., group $A$ either
always decides 0 or always decides 1 whenever $B$ and $C$ are isolated from
round $1$.

  3. (3)

At some round $R$ in the execution, $A$ must stop deciding the default bit
_even if there are faults afterward_ (e.g., even if $B$ and $C$ are isolated).
For example, if the default bit is $1$, but all processes propose $0$ and act
correctly until the end, then, by an interpolation argument, all correct
processes must at some round $R$ direct their strategy towards deciding $0$
(otherwise, they would violate _Weak Validity_).

  4. (4)

Isolating $B$ and $C$ at the same round (e.g., $k_{C}=k_{B}=R$) or one round
apart (e.g., $k_{B}=k_{C}+1=R$) is indistinguishable for processes in $B$ or
$C$. Thus, we can create a situation where processes in $C$ decide the default
bit $1$, while processes in $B$ choose $0$. In this situation, processes in
$A$ necessarily violate the statement of the first observation: if they decide
$1$, they disagree with $B$; if they decide $0$, they disagree with $C$.

To generalize our lower bound, we then show that weak consensus is reducible
at $0$ message cost to any solvable and non-trivial agreement problem in
synchrony. This reduction is possible because, for any Byzantine agreement
problem that is non-trivial and synchronously solvable, its specific validity
property must follow a certain structure. Concretely, we define a simple
combinatorial condition – the _containment condition_ – which we prove to be a
necessary condition for synchronously solvable non-trivial agreement problems.
Interestingly, the containment condition is also _sufficient_ , enabling us to
devise the general solvability theorem for Byzantine agreement problems.

##### Roadmap.

We state the system model and preliminaries in § 2. In § 3, we prove the
$\Omega(t^{2})$ lower bound on exchanged messages for weak consensus. A
generalization of the bound to all (solvable) non-trivial agreement problems
is provided in § 4. In § 5, we present the general solvability theorem for
Byzantine agreement problems. We provide an overview of related work in § 6,
and conclude the paper in § 7. The optional appendix contains omitted proofs.

##  2\. System Model & Preliminaries

##### Processes & adversary.

We consider a static system $\Pi=\\{p_{1},...,p_{n}\\}$ of $n$ processes,
where each process acts as a deterministic state machine. Moreover, we
consider a _static adversary_ which can corrupt up to $t<n$ processes before
each run of the system.111 Note that a lower bound proven for a static
adversary trivially applies to a stronger adaptive adversary which can corrupt
processes during (and not only before) a run of the system. A corrupted
process can behave arbitrarily; a non-corrupted process behaves according to
its state machine. We say that a corrupted process is _faulty_ , whereas a
non-corrupted process is _correct_.

##### Synchronous environment.

Computation unfolds in synchronous rounds. In each round
$1,2,...\in\mathbb{N}$, each process (1) performs (deterministic) local
computations, (2) sends (possibly different) messages to (a subset of) the
other processes, and (3) receives the messages sent to it in the round. We
assume authenticated channels: the receiver of a message is aware of the
sender’s identity.

##### Executions.

Each execution of any algorithm is uniquely identified by (1) the sets of
correct and faulty processes, and (2) the messages faulty processes send (or
do not send) in each round. Given any algorithm $\mathcal{A}$,
$\mathit{execs}(\mathcal{A})$ denotes the set of all $\mathcal{A}$’s
executions with no more than $t$ faulty processes. Lastly,
$\mathit{Correct}_{\mathcal{A}}(\mathcal{E})$ denotes the set of correct
processes in any execution $\mathcal{E}\in\mathit{execs}(\mathcal{A})$.

##### Message complexity.

Let $\mathcal{A}$ be any algorithm and let $\mathcal{E}$ be any execution of
$\mathcal{A}$. The message complexity of $\mathcal{E}$ is the number of
messages sent by correct processes throughout the entire execution
$\mathcal{E}$. (Note that all messages count towards the message complexity of
$\mathcal{E}$, even those sent after all correct processes have already
decided.) The _message complexity_ of $\mathcal{A}$ is then defined as

$\max_{\mathcal{E}\in\mathit{execs}(\mathcal{A})}\bigg{\\{}\text{the message
complexity of }\mathcal{E}\bigg{\\}}.$

##  3\. Lower Bound on Message Complexity of Weak Consensus

To prove our general lower bound, we first show a quadratic lower bound for
weak consensus:

###### Theorem 1.

Any weak consensus algorithm has $\Omega(t^{2})$ message complexity.

In order to prove Theorem 1, we show a strictly stronger lower bound for the
omission failure model in which processes can only fail by “dropping” some
messages they send or receive, but not by behaving maliciously.

##### Omission failures.

In (only) this section, we consider _omission failures_. A static adversary
corrupts up to $t<n$ processes before each execution. A corrupted process can
commit:

  * •

_send-omission_ faults, by not sending some messages it is supposed to send;
or

  * •

_receive-omission_ faults, by not receiving some messages it is supposed to
receive.

Note that a faulty process cannot misbehave in an arbitrary manner, i.e., it
acts according to its state machine at all times. Moreover, corrupted
processes are unaware that they are corrupted, i.e., they do not know if or
when they omitted some messages. Corrupted processes are said to be _faulty_ ,
whereas non-corrupted processes are said to be _correct_.

Two executions are said to be _indistinguishable_ to a (correct or faulty)
process if and only if (1) the process has the same proposal in both
executions and (2) the process receives identical messages in each round of
both executions. Note that, given two executions indistinguishable to some
process, the process’s actions in each round of both executions are
_identical_ due to the process’s determinism. Concretely, if two $k$-round-
long ($k\in\mathbb{N}$) executions are indistinguishable to a process $p_{i}$,
then (1) $p_{i}$’s internal states at the start of the $(k+1)$-st round of
both executions are identical, and (2) the sets of all messages sent
(including those that are omitted) in the $(k+1)$-st round of both executions
are identical. We relegate a precise definition of the omission failure model
to Appendix A.

##### Notation & remarks.

Given any set of processes $G$, let $\bar{G}=\Pi\setminus{G}$. If a faulty
process omits sending (resp., omits receiving) some message $m$, we say that
the process _send-omits_ (resp., _receive-omits_) $m$. Note that, in the
omission failure model, it is reasonable to make claims about the behaviors of
faulty processes as they always behave according to their state machine.
Finally, observe that any weak consensus algorithm provides guarantees _only_
to correct processes, i.e., it is possible for faulty processes to not
terminate or to disagree (among themselves or with correct processes).

##### Proof of Theorem 1.

As previously mentioned, we prove a quadratic lower bound for weak consensus
by showing that the problem requires at least $\frac{t^{2}}{32}$ messages even
with omission failures:

###### Lemma 0.

Any omission-resilient weak consensus algorithm has at least
$\frac{t^{2}}{32}$ message complexity.

We prove Lemma 2 by contradiction. Fix any $n$ and $t$ such that
$t\in[8,n-1]$. (Without loss of generality, we consider $t$ divisible by $8$.)
Fix any weak consensus algorithm $\mathcal{A}$ which (1) tolerates $t$
omission failures and works among $n$ processes, and (2) whose message
complexity is less than $\frac{t^{2}}{32}$. This implies that correct
processes send fewer than $\frac{t^{2}}{32}$ messages in _every_ execution of
$\mathcal{A}$. Table 1 introduces notation we rely on throughout the proof.

_Notation_ | _Definition_
---|---
$(A,B,C)$ |  Any partition of $\Pi$ such that (1) $|B|=\frac{t}{4}$, and (2) $|C|=\frac{t}{4}$ (naturally, $|A|=n-\frac{t}{2}$).
$\mathcal{E}_{0}$ |  The infinite execution of $\mathcal{A}$ in which (1) all processes propose $0$, and (2) all processes are correct.
$\mathcal{E}_{0}^{B(k)},k\in\mathbb{N}$ |  The infinite execution of $\mathcal{A}$ in which (1) all processes propose $0$, (2) processes from $A\cup C$ are correct, and (3) group $B$ is isolated from round $k$.
$\mathcal{E}_{0}^{C(k)},k\in\mathbb{N}$ |  The infinite execution of $\mathcal{A}$ in which (1) all processes propose $0$, (2) processes from $A\cup B$ are correct, and (3) group $C$ is isolated from round $k$.
$\mathcal{E}_{1}^{C(1)}$ |  The infinite execution of $\mathcal{A}$ in which (1) all processes propose $1$, (2) processes from $A\cup B$ are correct, and (3) group $C$ is isolated from round $1$.
Table 1. Notation table for the lower bound for weak consensus.
(The concept of group isolation is described in Definition 3.)

First, let us introduce the concept of _isolation_ , which we use extensively
throughout the proof.

###### Definition 0 (Isolation).

A group $G\subsetneq\Pi$ of $|G|\leq t$ processes is _isolated from some round
$k\in\mathbb{N}$_ in an execution $\mathcal{E}$ of $\mathcal{A}$ if and only
if, for every process $p_{G}\in G$, the following holds:

  * •

$p_{G}$ is faulty in $\mathcal{E}$; and

  * •

$p_{G}$ does not send-omit any message in $\mathcal{E}$; and

  * •

for every message $m$ sent by any process $p_{m}$ to $p_{G}$ in any round
$k^{\prime}\in\mathbb{N}$ of $\mathcal{E}$, $p_{G}$ receive-omits $m$ in
$\mathcal{E}$ if and only if (1) $p_{m}\in\bar{G}$, and (2) $k^{\prime}\geq
k$.

Intuitively, a group $G$ is isolated from some round $k$ if and only if no
process $p_{G}\in G$ receives any message from outside of $G$ in any round
$k^{\prime}\geq k$, i.e., $p_{G}$ only receives messages sent by processes in
$G$ from round $k$ onward; other than these receive-omission faults, $p_{G}$
commits no other faults. Figure 1 illustrates the concept of isolation.

Figure 1. Illustration of Definition 3. The colors represent the local
behaviors of processes. Execution $\mathcal{E}_{0}$ has no faults. Execution
$\mathcal{E}_{0}^{G(R)}$ proceeds identically to $\mathcal{E}_{0}$, sending
the same messages (green color) up until round $R$ (inclusive). However, group
$G$ is _isolated_ at round $R$, causing it to drop all messages from group
$\overline{G}$ from then on. This (potentially) changes $G$’s sending behavior
from round $R+1$ onward (red color). By propagation, group $\overline{G}$ is
then (potentially) affected by $G$’s new sending behavior (red color), causing
$\overline{G}$ to deviate from $\mathcal{E}_{0}$ in the messages it sends from
round $R+2$ onward (blue color).

Let $(X,Y,Z)$ be any partition of $\Pi$ such that $|Y|=\frac{t}{4}$ and
$|Z|\leq\frac{t}{4}$. The following lemma proves that in any infinite
execution $\mathcal{E}$ of $\mathcal{A}$ in which processes from $X$ are
correct and processes from $Y\cup Z$ are faulty, more than half of processes
from $Y$ decide the same bit as (all) processes from $X$. If this was not the
case, we could construct an execution that demonstrates that $\mathcal{A}$ is
not a correct weak consensus algorithm. We formally prove the lemma in
Appendix A.

###### Lemma 0.

Let $(X,Y,Z)$ be any partition of $\Pi$ such that (1) $|Y|=\frac{t}{4}$, and
(2) $|Z|\leq\frac{t}{4}$ (naturally, $|X|=n-|Y|-|Z|$). Moreover, let
$\mathcal{E}$ be any infinite execution of $\mathcal{A}$ such that:

  * •

processes from $X$ are correct in $\mathcal{E}$, whereas processes from $Y\cup
Z$ are faulty in $\mathcal{E}$; and

  * •

all processes from $X$ decide the same bit $b_{X}$ (to satisfy _Termination_
and _Agreement_); and

  * •

group $Y$ is isolated from some round $k\in\mathbb{N}$ in $\mathcal{E}$.

Then, there exists a set $Y^{\prime}\subseteq Y$ of
$|Y^{\prime}|>\frac{|Y|}{2}$ processes such that all processes in $Y^{\prime}$
decide $b_{X}$ in $\mathcal{E}$.

Proof Sketch. For every process $p\in Y$, let $\mathcal{M}_{X\to p}$ denote
the set of all messages which are (1) sent by any process $p^{\prime}\in X$ in
$\mathcal{E}$, and (2) receive-omitted by $p$ in $\mathcal{E}$; as $p\in Y$
and group $Y$ is isolated from round $k$ in $\mathcal{E}$, every message
$m\in\mathcal{M}_{X\to p}$ is sent in some round $k^{\prime}\geq k$. For every
set $Y^{\prime\prime}\subseteq Y$, let $\mathcal{M}_{X\to
Y^{\prime\prime}}=\bigcup\limits_{p\in Y^{\prime\prime}}\mathcal{M}_{X\to p}$.
As correct processes (i.e., processes from group $X$) send fewer than
$\frac{t^{2}}{32}$ messages in $\mathcal{E}$, $|\mathcal{M}_{X\to
Y}|<\frac{t^{2}}{32}$. Therefore, there does not exist a set $Y^{*}\subseteq
Y$ of $|Y^{*}|\geq\frac{|Y|}{2}$ processes such that, for every process
$p_{Y^{*}}\in Y^{*}$, $|\mathcal{M}_{X\to p_{Y^{*}}}|\geq\frac{t}{2}$. This
implies that there exists a set $Y^{\prime}\subseteq Y$ of
$|Y^{\prime}|>\frac{|Y|}{2}$ processes such that, for every process
$p_{Y^{\prime}}\in Y^{\prime}$, $|\mathcal{M}_{X\to
p_{Y^{\prime}}}|<\frac{t}{2}$.

Fix any process $p_{Y^{\prime}}\in Y^{\prime}$. By contradiction, suppose that
$p_{Y^{\prime}}$ does not decide $b_{X}$ in $\mathcal{E}$. Let $\mathcal{S}$
denote the set of all processes whose messages $p_{Y^{\prime}}$ receive-omits
in (any round $k^{\prime}\geq k$ of) $\mathcal{E}$; note that
$|\mathcal{S}\cap X|<\frac{t}{2}$ (since $|\mathcal{M}_{X\to
p_{Y^{\prime}}}|<\frac{t}{2}$) and $\mathcal{S}\subsetneq X\cup Z$. Let us
construct another infinite execution $\mathcal{E}^{\prime}$ of $\mathcal{A}$
following the (sequentially-executed) steps below:

  1. (1)

Processes in $\mathcal{S}\cup Y\cup Z\setminus{\\{p_{Y^{\prime}}\\}}$ are
faulty in $\mathcal{E}^{\prime}$, whereas all other processes are correct.

  2. (2)

Then, we set $\mathcal{E}^{\prime}\leftarrow\mathcal{E}$: every process (at
first) behaves in the same manner as in $\mathcal{E}$.

  3. (3)

For every message $m$ such that $p_{Y^{\prime}}$ receive-omits $m$ in
$\mathcal{E}$, $m$ is send-omitted in $\mathcal{E}^{\prime}$. That is, the
sender of $m$ is responsible for $p_{Y^{\prime}}$ not receiving $m$ in
$\mathcal{E}^{\prime}$.

Observe that $p_{Y^{\prime}}$ is indeed correct in $\mathcal{E}^{\prime}$ as
(1) $p_{Y^{\prime}}$ does not commit any send-omission faults (since
$p_{Y^{\prime}}$ does not commit those faults in $\mathcal{E}$), and (2)
$p_{Y^{\prime}}$ does not commit any receive-omission faults (since every
message which is receive-omitted in $\mathcal{E}$ is send-omitted in
$\mathcal{E}^{\prime}$). Moreover, there are $|\mathcal{S}\cup Y\cup
Z\setminus{\\{p_{Y^{\prime}}\\}}|=|(\mathcal{S}\cap X)\cup Y\cup
Z\setminus{\\{p_{Y^{\prime}}\\}}|<\frac{t}{2}+\frac{t}{4}+\frac{t}{4}-1<t$
faulty processes in $\mathcal{E}^{\prime}$. Furthermore, there exists a
process $p_{X}\in X$ which is correct in $\mathcal{E}^{\prime}$ as
$|\mathcal{S}\cap X|<\frac{t}{2}$, $|X|\geq n-\frac{t}{2}$ and $n>t$. Finally,
neither $p_{Y^{\prime}}$ nor $p_{X}$ can distinguish $\mathcal{E}^{\prime}$
from $\mathcal{E}$ as their behaviors in $\mathcal{E}^{\prime}$ and
$\mathcal{E}$ are identical.222Recall that process $p_{Y^{\prime}}$ is unaware
of receive-omission failures it commits in $\mathcal{E}$. Therefore, the fact
that $p_{Y^{\prime}}$ does not commit receive-omission failures in
$\mathcal{E}^{\prime}$ does not allow $p_{Y^{\prime}}$ to distinguish
$\mathcal{E}^{\prime}$ from $\mathcal{E}$. Therefore, either _Termination_ (if
$p_{Y^{\prime}}$ does not decide) or _Agreement_ (if $p_{Y^{\prime}}$ decides
$1-b_{X}$) is violated in $\mathcal{E}^{\prime}$, which contradicts the fact
that $\mathcal{A}$ is a correct weak consensus algorithm. $\square$

Next, we define _mergeable_ executions.

###### Definition 0 (Mergeable executions).

Any two infinite executions $\mathcal{E}_{0}^{B(k_{1})}$
($k_{1}\in\mathbb{N}$) and $\mathcal{E}_{b}^{C(k_{2})}$ ($b\in\\{0,1\\}$,
$k_{2}\in\mathbb{N}$) are _mergeable_ if and only if:

  * •

$k_{1}=k_{2}=1$; or

  * •

$|k_{1}-k_{2}|\leq 1$ and $b=0$.

In brief, executions $\mathcal{E}_{0}^{B(k_{1})}$ and
$\mathcal{E}_{b}^{C(k_{2})}$ (which are defined in Table 1) are mergeable if
(1) group $B$ (resp., $C$) is isolated from round $1$ in
$\mathcal{E}_{0}^{B(k_{1})}$ (resp., $\mathcal{E}_{b}^{C(k_{2})}$), or (2)
$b=0$ and groups $B$ and $C$ are isolated at most one round apart in their
respective executions. Note that all processes from group $A$ are correct in
any two mergeable executions. The following lemma proves that processes from
group $A$ decide identically in any two mergeable executions, and it
represents a crucial intermediate result in proving our lower bound. We
formally prove the lemma in Appendix A. An illustration of its application can
be seen in Figure 2.

###### Lemma 0.

Let $\mathcal{E}_{0}^{B(k_{1})}$ ($k_{1}\in\mathbb{N}$) and
$\mathcal{E}_{b}^{C(k_{2})}$ ($b\in\\{0,1\\},k_{2}\in\mathbb{N}$) be any two
mergeable executions. Let any process from group $A$ decide $b_{1}$ (resp.,
$b_{2}$) in $\mathcal{E}_{0}^{B(k_{1})}$ (resp.,
$\mathcal{E}_{b}^{C(k_{2})}$). Then, $b_{1}=b_{2}$.

Proof Sketch. For $\mathcal{A}$ to satisfy _Termination_ and _Agreement_ , all
processes from group $A$ decide $b_{1}$ (resp., $b_{2}$) in
$\mathcal{E}_{0}^{B(k_{1})}$ (resp., $\mathcal{E}_{b}^{C(k_{2})}$). Given the
partition $(A\cup C,B,\emptyset)$ of $\Pi$ and the execution
$\mathcal{E}_{0}^{B(k_{1})}$, Lemma 4 proves that there exists a set
$B^{\prime}\subseteq B$ of more than $\frac{|B|}{2}$ processes such that every
process $p_{B^{\prime}}\in B^{\prime}$ decides $b_{1}$ in
$\mathcal{E}_{0}^{B(k_{1})}$. Similarly, given the partition $(A\cup
B,C,\emptyset)$ of $\Pi$ and the execution $\mathcal{E}_{b}^{C(k_{2})}$, Lemma
4 proves that there exists a set $C^{\prime}\subseteq C$ of more than
$\frac{|C|}{2}$ processes such that every process $p_{C^{\prime}}\in
C^{\prime}$ decides $b_{2}$ in $\mathcal{E}_{b}^{C(k_{2})}$.

We now construct another infinite execution $\mathcal{E}$ of $\mathcal{A}$:

  1. (1)

Processes from group $A$ are correct, whereas processes from $B\cup C$ are
faulty.

  2. (2)

All processes from $A\cup B$ propose $0$, whereas all processes from group $C$
propose $b$.

  3. (3)

Every process $p_{B}\in B$ (resp., $p_{C}\in C$) behaves in the same manner as
in $\mathcal{E}^{B(k_{1})}_{0}$ (resp., $\mathcal{E}^{C(k_{2})}_{b}$). Let us
elaborate on why this step of the construction is valid:

     * •

Suppose that $k_{1}=k_{2}=1$. Due to the construction of $\mathcal{E}$, every
process $p_{B}\in B$ (resp., $p_{C}\in C$) receives messages only from other
processes in the same group $B$ (resp., $C$) in $\mathcal{E}$. As (1) all
messages received by $p_{B}\in B$ (resp., $p_{C}\in C$) in $\mathcal{E}$ are
sent in $\mathcal{E}_{0}^{B(1)}$ (resp., $\mathcal{E}_{b}^{C(1)}$), and (2)
for every process $p_{B}^{\prime}\in B$ (resp., $p_{C}^{\prime}\in C$), the
set of messages sent by $p_{B}^{\prime}$ (resp., $p_{C}^{\prime}$) in
$\mathcal{E}$ is identical to the set of messages sent by $p_{B}^{\prime}$
(resp., $p_{C}^{\prime}$) in $\mathcal{E}_{0}^{B(1)}$ (resp.,
$\mathcal{E}_{b}^{C(1)}$), the construction step is indeed valid in this case.

     * •

Suppose that $|k_{1}-k_{2}|\leq 1$ and $b=0$. As the behavior of each process
from group $B$ (resp., $C$) in $\mathcal{E}$ is identical to its behavior in
$\mathcal{E}_{0}^{B(k_{1})}$ (resp., $\mathcal{E}_{0}^{C(k_{2})}$), the set of
messages received by any process $p_{B}\in B$ (resp., $p_{C}\in C$) in
$\mathcal{E}$ is identical to the set of messages received by $p_{B}\in B$
(resp., $p_{C}\in C$) in $\mathcal{E}_{0}^{B(k_{1})}$ (resp.,
$\mathcal{E}_{0}^{C(k_{2})}$). To prove the validity of the construction step
in this scenario, we show that, for each message received by any process
$p_{B}\in B$ (resp., $p_{C}\in C$) in $\mathcal{E}$, that message is sent in
$\mathcal{E}$.

Without loss of generality, we fix any message $m$ received by any process
$p_{B}\in B$ in $\mathcal{E}$. We denote the sender of $m$ by $p_{m}$. Note
that $m$ is sent by $p_{m}$ in $\mathcal{E}_{0}^{B(k_{1})}$ as $m$ is received
in $\mathcal{E}_{0}^{B(k_{1})}$. If $m$ is received before round
$R=\min(k_{1},k_{2})$, $m$ is sent in $\mathcal{E}$ as, for any process
$p\in\Pi$, $p$’s behaviour until (and excluding) round $R$ is identical in
$\mathcal{E}$ and $\mathcal{E}_{0}^{B(k_{1})}$. If $m$ is received in or after
round $R$, we distinguish two possibilities:

       * –

Let $m$ be received before round $k_{1}$. (This is possible only if
$k_{1}>k_{2}$.) Hence, $m$ is received in round $R$. In this case, $m$ is sent
in $\mathcal{E}$ as the set of messages $p_{m}$ sends in $\mathcal{E}$ is
identical to the set of messages $p_{m}$ sends in $\mathcal{E}_{0}^{B(k_{1})}$
(since the internal state of process $p_{m}$ at the beginning of round $R$ is
identical in $\mathcal{E}$ and $\mathcal{E}_{0}^{B(k_{1})}$).

       * –

Let $m$ be received in or after round $k_{1}$. In this case, $p_{m}\in B$ (as
group $B$ is isolated from round $k_{1}$ in $\mathcal{E}_{0}^{B(k_{1})}$).
Therefore, $m$ is sent in $\mathcal{E}$ as the behavior of every process from
group $B$ in $\mathcal{E}$ is identical to its behavior in
$\mathcal{E}_{0}^{B(k_{1})}$.

Note that this step of construction ensures that group $B$ (resp., $C$) is
isolated from round $k_{1}$ (resp., $k_{2}$) in $\mathcal{E}$.

As no process $p_{B^{\prime}}\in B^{\prime}$ (resp., $p_{C^{\prime}}\in
C^{\prime}$) distinguishes $\mathcal{E}$ from $\mathcal{E}_{0}^{B(k_{1})}$
(resp., $\mathcal{E}_{b}^{C(k_{2})}$), all processes from $B^{\prime}$ (resp.,
$C^{\prime}$) decide $b_{1}$ (resp., $b_{2}$) in $\mathcal{E}$. Let $b_{A}$ be
the decision of processes from group $A$ in $\mathcal{E}$; such a decision
must exist as $\mathcal{A}$ satisfies _Termination_ and _Agreement_. Given the
partition $(A,B,C)$ of $\Pi$ and the newly constructed execution
$\mathcal{E}$, Lemma 4 proves that $b_{1}=b_{A}$. Similarly, given the
partition $(A,C,B)$ of $\Pi$ and the execution $\mathcal{E}$, Lemma 4 shows
that $b_{2}=b_{A}$. As $b_{1}=b_{A}$ and $b_{A}=b_{2}$, $b_{1}=b_{2}$, which
concludes the proof. $\square$

Lemma 6 implies that all processes from group $A$ decide identical values in
executions $\mathcal{E}_{0}^{B(1)}$ and $\mathcal{E}_{1}^{C(1)}$ as these two
executions are mergeable (see Definition 5). Without loss of generality, the
rest of the proof assumes that all processes from group $A$ decide $1$ in
$\mathcal{E}_{0}^{B(1)}$ (and $\mathcal{E}_{1}^{C(1)}$). Intuitively, the
value $1$ acts as the “default” value for processes in $A$ if they detect
faults early. In the following lemma, we prove that there exists a round
$R\in\mathbb{N}$ such that processes from group $A$ decide $1$ in
$\mathcal{E}_{0}^{B(R)}$ and $0$ in $\mathcal{E}_{0}^{B(R+1)}$. This expresses
the idea that $A$ must, at some critical round (i.e., $R+1$), abandon its
initial strategy of always deciding the “default” value.

###### Lemma 0.

There exists a round $R\in\mathbb{N}$ such that (1) all processes from group
$A$ decide $1$ in $\mathcal{E}_{0}^{B(R)}$, and (2) all processes from group
$A$ decide $0$ in $\mathcal{E}_{0}^{B(R+1)}$.

###### Proof.

Let $R_{\mathit{max}}\in\mathbb{N}$ denote the round before which all
processes decide $0$ in $\mathcal{E}_{0}$, which is the fully correct
execution with all processes proposing $0$ (see Table 1); such a round must
exist for $\mathcal{A}$ to satisfy _Termination_ and _Weak Validity_. Hence,
all processes from group $A$ decide $0$ in
$\mathcal{E}_{0}^{B(R_{\mathit{max}})}$. By our assumption, all processes from
group $A$ decide $1$ in $\mathcal{E}_{0}^{B(1)}$. Therefore, there exists a
round $R\in[1,R_{\mathit{max}})$ which satisfies the statement of the lemma. ∎

Finally, we are ready to prove that $\mathcal{E}$ exchanges at least
$\frac{t^{2}}{32}$ messages.

###### Lemma 0.

The message complexity of $\mathcal{A}$ is at least $\frac{t^{2}}{32}$.

###### Proof.

According to Lemma 7, there exists a round $R\in\mathbb{N}$ such that (1)
processes from group $A$ decide $1$ in $\mathcal{E}_{0}^{B(R)}$, and (2)
processes from group $A$ decide $0$ in $\mathcal{E}_{0}^{B(R+1)}$. By
Definition 5, executions $\mathcal{E}_{0}^{B(R)}$ and $\mathcal{E}_{0}^{C(R)}$
are mergeable. As processes from group $A$ decide $1$ in
$\mathcal{E}_{0}^{B(R)}$, Lemma 6 implies that processes from group $A$ decide
$1$ in $\mathcal{E}_{0}^{C(R)}$. Moreover, executions
$\mathcal{E}_{0}^{B(R+1)}$ and $\mathcal{E}_{0}^{C(R)}$ are mergeable
according to Definition 5. Thus, by Lemma 6, all processes from group $A$
decide $1$ in $\mathcal{E}_{0}^{B(R+1)}$ (as they do so in
$\mathcal{E}_{0}^{C(R)}$). This is a contradiction with the fact that
processes from group $A$ decide $0$ in $\mathcal{E}_{0}^{B(R+1)}$. Hence, the
assumption of $\mathcal{A}$’s message complexity being less than
$\frac{t^{2}}{32}$ must be wrong. ∎

Figure 2. Illustration of Lemma 6 used in the proof of Lemma 8. The arrows
denoting messages are not exhaustive. As in Figure 1, the colors represent the
local behaviors of processes. This picture illustrates why group $A$ is forced
to decide the same value in executions $\mathcal{E}_{0}^{B(R+1)}$ and
$\mathcal{E}_{0}^{C(R)}$. Consider the “merged” execution
$\mathcal{E}_{0}^{B(R+1),C(R)}$ where $B$ and $C$ are isolated at rounds $R+1$
and $R$, respectively. If $A$ decides differently in
$\mathcal{E}_{0}^{B(R+1)}$ (row 1) and $\mathcal{E}_{0}^{C(R)}$ (row 5), then
majorities of $B$ and $C$ decide differently in the
$\mathcal{E}_{0}^{B(R+1),C(R)}$ (rows 2 and 4) due to indistinguishability.
Group $A$ in $\mathcal{E}_{0}^{B(R+1),C(R)}$ (row 3) then disagrees with
either a majority of $B$ (row 2) or a majority of $C$ (row 4), contradicting
Lemma 4.

##  4\. Generalization of the Lower Bound

In this section, we extend the quadratic lower bound proven for weak consensus
(see § 3) to all non-trivial (without an always-admissible decision) Byzantine
agreement problems:

###### Theorem 1.

Any algorithm that solves any non-trivial Byzantine agreement problem has
$\Omega(t^{2})$ message complexity.

To prove the general lower bound (Theorem 1), we show that weak consensus is
the weakest non-trivial agreement problem. Namely, we present a zero-message
reduction from weak consensus to any (solvable) non-trivial agreement problem.

###  4.1. Validity Properties

To capture any specific Byzantine agreement problem, we require a generic
definition of the validity property. For that purpose, we reuse the formalism
(and nomenclature) of (validity_podc, ). In brief, a validity property maps
the proposals of correct processes into a set of admissible decisions.

Let a _process-proposal_ pair be a pair $(p_{i},v)$, where $p_{i}\in\Pi$ is a
process and $v\in\mathcal{V}_{I}$ is a proposal. Given any process-proposal
pair $\mathit{pp}=(p_{i},v)$, we denote by $\mathsf{proposal}(\mathit{pp})=v$
the proposal associated with the pair. An _input configuration_ is a tuple
$\big{[}\mathit{pp}_{1},\mathit{pp}_{2},...,\mathit{pp}_{x}\big{]}$ such that
(1) $n-t\leq x\leq n$, and (2) every process-proposal pair is associated with
a distinct process. In a nutshell, an input configuration is an assignment of
proposals to (all) correct processes. For instance,
$\big{[}(p_{1},v_{1}),(p_{4},v_{4}),(p_{5},v_{5})\big{]}$ is an input
configuration according to which (1) only processes $p_{1}$, $p_{4}$ and
$p_{5}$ are correct, and (2) $p_{1}$ proposes $v_{1}$, $p_{4}$ proposes
$v_{4}$ and $p_{5}$ proposes $v_{5}$.

The set of all input configurations is denoted by $\mathcal{I}$. Moreover,
$\mathcal{I}_{n}\subsetneq\mathcal{I}$ denotes the set of all input
configurations with exactly $n$ process-proposals pairs. Given any input
configuration $c\in\mathcal{I}$, $c[i]$ denotes the process-proposal pair
associated with the process $p_{i}$; if such a process-proposal pair does not
exist, $c[i]=\bot$. Moreover, $\pi(c)=\\{p_{i}\in\Pi\,|\,c[i]\neq\bot\\}$
denotes the set of all correct processes according to any input configuration
$c\in\mathcal{I}$.

##### Execution - input configuration correspondence.

Let $\mathcal{E}$ be any execution of any algorithm $\mathcal{A}$ which
exposes the $\mathsf{propose}(\cdot)/\mathsf{decide}(\cdot)$ interface, and
let $c\in\mathcal{I}$ be any input configuration. We say that $\mathcal{E}$
_corresponds to_ $c$ (in short, $\mathsf{input\\_conf}(\mathcal{E})=c$) if and
only if:

  * •

$\pi(c)=\mathit{Correct}_{\mathcal{A}}(\mathcal{E})$, i.e., the set of
processes which are correct in $\mathcal{E}$ is identical to the set of
processes which are correct according to $c$; and

  * •

for every process $p_{i}\in\pi(c)$, $p_{i}$’s proposal in $\mathcal{E}$ is
$\mathsf{proposal}(c[i])$.

##### Satisfying validity.

A validity property $\mathit{val}$ is a function $\mathit{val}:\mathcal{I}\to
2^{\mathcal{V}_{O}}$ such that $\mathit{val}(c)\neq\emptyset$, for every input
configuration $c\in\mathcal{I}$. We say that any algorithm $\mathcal{A}$ which
exposes the $\mathsf{propose}(\cdot)/\mathsf{decide}(\cdot)$ interface
_satisfies_ a validity property $\mathit{val}$ if and only if, in any
execution $\mathcal{E}\in\mathit{execs}(\mathcal{A})$, no correct process
decides any value
$v^{\prime}\notin\mathit{val}\big{(}\mathsf{input\\_conf}(\mathcal{E})\big{)}$.
Intuitively, an algorithm satisfies a validity property if correct processes
only decide admissible values.

##### The defining property of Byzantine agreement.

Observe that an exact definition of validity uniquely defines a _specific_
agreement problem. Indeed, any validity property encodes information about (1)
$n$, the total number of processes, (2) $t$, the upper bound on the number of
failures, (3) $\mathcal{V}_{I}$, the set of proposals, and (4)
$\mathcal{V}_{O}$, the set of decisions. We refer to a specific agreement
problem with a validity property $\mathit{val}$ as the
“$\mathit{val}$-agreement” problem. Lastly, we recall that the
$\mathit{val}$-agreement problem, for some validity property $\mathit{val}$,
is _trivial_ if and only if there exists an always-admissible value, i.e.,

$\exists
v^{\prime}\in\mathcal{V}_{O}:v^{\prime}\in\bigcap\limits_{c\in\mathcal{I}}\mathit{val}(c).$

###  4.2. Weak Consensus: The Weakest Non-Trivial Byzantine Agreement Problem

In this subsection, we prove that any solution to any non-trivial agreement
problem yields, at no additional communication cost, a solution to weak
consensus:

###### Lemma 0.

There exists a zero-message reduction from weak consensus to any solvable non-
trivial Byzantine agreement problem.

Before presenting the reduction, we introduce the _containment relation_.

##### Containment relation.

We define the containment relation (“$\sqsupseteq$”) between input
configurations:

$\forall c_{1},c_{2}\in\mathcal{I}:c_{1}\sqsupseteq
c_{2}\iff(\pi(c_{1})\supseteq\pi(c_{2}))\land(\forall
p_{i}\in\pi(c_{2}):c_{1}[i]=c_{2}[i]).$

Intuitively, $c_{1}$ contains $c_{2}$ if and only if (1) each process in
$c_{2}$ belongs to $c_{1}$, and (2) for each process in $c_{2}$, its proposals
in $c_{1}$ and $c_{2}$ are identical. For example, when $n=3$ and $t=1$,
$\big{[}(p_{1},v_{1}),(p_{2},v_{2}),(p_{3},v_{3})\big{]}$ contains
$\big{[}(p_{1},v_{1}),(p_{3},v_{3})\big{]}$, but it does not contain
$\big{[}(p_{1},v_{1}),(p_{3},v_{3}^{\prime}\neq v_{3})\big{]}$. Note that the
containment relation is reflexive (for every $c\in\mathcal{I}$, $c\sqsupseteq
c$). For any input configuration $c\in\mathcal{I}$, we define its _containment
set_ $\mathit{Cnt}(c)$ as the set of all input configurations which $c$
contains:

$\mathit{Cnt}(c)=\\{c^{\prime}\in\mathcal{I}\,|\,c\sqsupseteq c^{\prime}\\}.$

The following lemma proves that, in any execution that corresponds to some
input configuration $c$, if any agreement algorithm decides some value
$v^{\prime}$, then $v^{\prime}$ must be admissible according to all input
configurations $c$ contains. Otherwise, the same scenario can correspond to
_another_ input configuration for which $v^{\prime}$ is not admissible, thus
violating the considered validity property. A formal proof of the following
lemma is relegated to Appendix B.

###### Lemma 0.

Let $\mathcal{A}$ be any algorithm that solves the $\mathit{val}$-agreement
problem, for any validity property $\mathit{val}$. Let $\mathcal{E}$ be any
(potentially infinite) execution of $\mathcal{A}$, and let
$c=\mathsf{input\\_conf}(\mathcal{E})$, for some input configuration $c$. If a
correct process decides a value $v^{\prime}\in\mathcal{V}_{O}$ in
$\mathcal{E}$, then
$v^{\prime}\in\bigcap\limits_{c^{\prime}\in\mathit{Cnt}(c)}\mathit{val}(c^{\prime})$.

##### Reduction.

We fix any solvable non-trivial agreement problem $\mathcal{P}$, and any
algorithm $\mathcal{A}$ which solves $\mathcal{P}$. Let $\mathit{val}$ denote
the specific validity property of $\mathcal{P}$. Moreover, we fix the
following notation:

_Notation_ | _Definition & commentary_
---|---
$c_{0}\in\mathcal{I}_{n}$ |  Any input configuration (of $\mathcal{P}$) according to which all processes are correct ($\pi(c_{0})=\Pi$).
$\mathcal{E}_{0}\in\mathit{execs}(\mathcal{A})$ |  The infinite execution of $\mathcal{A}$ such that $\mathsf{input\\_conf}(\mathcal{E}_{0})=c_{0}$.
$v_{0}^{\prime}\in\mathcal{V}_{O}$ |  The value decided in $\mathcal{E}_{0}$. Note that such a value exists as $\mathcal{A}$ satisfies _Termination_ and _Agreement_.
$c_{1}^{*}\in\mathcal{I}$ |  Any input configuration (of $\mathcal{P}$) such that $v_{0}^{\prime}\notin\mathit{val}(c_{1}^{*})$. Note that such an input configuration exists as $\mathcal{P}$ is non-trivial.
$c_{1}\in\mathcal{I}_{n}$ |  Any input configuration (of $\mathcal{P}$) such that (1) $c_{1}\sqsupseteq c_{1}^{*}$, and (2) all processes are correct according to $c_{1}$ ($\pi(c_{1})=\Pi$). Note that such an input configuration exists as the containment condition is reflexive.
$\mathcal{E}_{1}\in\mathit{execs}(\mathcal{A})$ |  The infinite execution of $\mathcal{A}$ such that $\mathsf{input\\_conf}(\mathcal{E}_{1})=c_{1}$.
$v_{1}^{\prime}\in\mathcal{V}_{O}$ |  The value decided in $\mathcal{E}_{1}$. Note that such a value exists as $\mathcal{A}$ satisfies _Termination_ and _Agreement_. Crucially, as $c_{1}\sqsupseteq c_{1}^{*}$ and $v_{0}^{\prime}\notin\mathit{val}(c_{1}^{*})$, Lemma 3 proves that $v_{1}^{\prime}\neq v_{0}^{\prime}$.
Table 2. Notation table for the reduction.

The reduction from weak consensus to $\mathcal{P}$ is presented in Algorithm
1. Our crucial observation is that $\mathcal{A}$, the fixed algorithm solving
$\mathcal{P}$, decides _different_ values in $\mathcal{E}_{0}$ and
$\mathcal{E}_{1}$: by Lemma 3, the value $v_{1}^{\prime}$ decided in
$\mathcal{E}_{1}$ is admissible according to $c_{1}^{*}$ (as $c_{1}\sqsupseteq
c_{1}^{*}$), which implies that $v_{1}^{\prime}\neq v_{0}^{\prime}$. We
utilize the aforementioned fact to distinguish (1) the fully correct execution
$\mathcal{E}_{0}^{w}$ of weak consensus where all processes propose $0$, and
(2) the fully correct execution $\mathcal{E}_{1}^{w}$ of weak consensus where
all processes propose $1$. Namely, our reduction works as follows: If a
correct process $p_{i}$ proposes $0$ (resp., $1$) to weak consensus, $p_{i}$
proposes its proposal from the input configuration $c_{0}$ (resp., $c_{1}$) to
the underlying algorithm $\mathcal{A}$. Moreover, if $p_{i}$ decides
$v_{0}^{\prime}$ from $\mathcal{A}$, $p_{i}$ decides $0$ from weak consensus;
otherwise, $p_{i}$ decides $1$ from weak consensus. Thus, if all processes are
correct and propose $0$ (resp., $1$) to weak consensus, $\mathcal{A}$
_necessarily_ decides $v_{0}^{\prime}$ (resp., $v_{1}^{\prime}\neq
v_{0}^{\prime}$), which then implies that all correct processes decide $0$
(resp., $1$) from weak consensus, thus satisfying _Weak Validity_. The
correctness of our reduction is proven in Appendix C.

Algorithm 1 Reduction from weak consensus to $\mathcal{P}$: Pseudocode for
process $p_{i}$

1:Uses:

2: $\mathcal{A}$, an algorithm solving the non-trivial agreement problem
$\mathcal{P}$

3:upon $\mathsf{propose}(b\in\\{0,1\\})$:

4: if $b=0$:

5: invoke
$\mathcal{A}.\mathsf{propose}\big{(}\mathsf{proposal}(c_{0}[i])\big{)}$

6: else:

7: invoke
$\mathcal{A}.\mathsf{propose}\big{(}\mathsf{proposal}(c_{1}[i])\big{)}$

8:upon $\mathcal{A}.\mathsf{decide}(\mathit{decision}\in\mathcal{V}_{O})$:

9: if $\mathit{decision}=v_{0}^{\prime}$:

10: trigger $\mathsf{decide}(0)$

11: else

12: trigger $\mathsf{decide}(1)$

Importantly, our reduction proves the general quadratic lower bound (Theorem
1). Indeed, if there was a sub-quadratic algorithm $\mathcal{A}$ which solves
any non-trivial Byzantine agreement problem, the introduced reduction would
yield a sub-quadratic weak consensus algorithm, thus contradicting the
quadratic lower bound for weak consensus (proven in § 3).

###  4.3. On the Lower Bound for the Blockchain-Specific Agreement Problem

At the heart of today’s blockchain systems lies an agreement problem that
requires the decided value to satisfy a globally verifiable condition.
Concretely, modern blockchain systems satisfy the following validity property:

  * •

_External Validity_ (Cachin2001, ): If a correct process decides a value
$v^{\prime}$, then $\mathsf{valid}(v^{\prime})=\mathit{true}$, where
$\mathsf{valid}(\cdot)$ is a globally verifiable predicate.

This subsection underlines that the general quadratic lower bound (Theorem 1)
extends to all “reasonable” agreement problems with _External Validity_.

_External Validity_ emerged as the validity property of blockchain systems
because stronger notions of validity have limited applicability in this
setting. For example, consider _Strong Validity_ which guarantees only that,
if all correct processes propose the same value, that value must be decided.
Whenever correct processes do not propose the same value, _Strong Validity_
provides no guarantees, e.g., a value proposed by a faulty process can be
decided. In a blockchain setting, it will rarely be the case that all correct
validators (i.e., processes that operate the blockchain) construct and propose
an identical block with the clients’ pending transactions. Hence, the chain
could be comprised of “faulty blocks”, thus allowing faulty validators to
commit invalid (e.g., incorrectly signed) transactions. _External Validity_
eliminates this problem by allowing only valid blocks to be committed.

As mentioned in (validity_podc, ), the formalism we use for defining validity
properties (see § 4.1) is not suitable for expressing _External Validity_.
Namely, the formalism would technically classify _External Validity_ as a
trivial validity property since any fixed valid value is admissible according
to _every_ input configuration. However, in practice, the agreement problem
with _External Validity_ does not allow for a trivial solution in the
blockchain setting. For example, the fact that some transaction $\mathit{tx}$,
which is _correctly signed_ by some client, is valid does not mean that
validators can always decide $\mathit{tx}$. Indeed, for a validator to decide
$\mathit{tx}$, it needs to first _learn_ about $\mathit{tx}$ (otherwise,
cryptographic hardness assumptions on signatures would break). Therefore,
validators cannot decide $\mathit{tx}$ “on their own”, which precludes a
trivial solution to agreement problems with _External Validity_.

Nonetheless, our quadratic lower bound applies to _any_ algorithm
$\mathcal{A}$ which solves Byzantine agreement with _External Validity_ as
long as the algorithm has two fully correct executions with different
decisions. Indeed, if $\mathcal{A}$ has two fully correct infinite executions
$\mathcal{E}_{0}$ and $\mathcal{E}_{1}$ that decide different values,
Algorithm 1 (see § 4.2) solves weak consensus using $\mathcal{A}$ by employing
$c_{0}=\mathsf{input\\_conf}(\mathcal{E}_{0})$ (line 5 of Algorithm 1) and
$c_{1}=\mathsf{input\\_conf}(\mathcal{E}_{1})$ (line 7 of Algorithm 1). To the
best of our knowledge, every known agreement algorithm with _External
Validity_ (e.g., (yin2019hotstuff, ; BKM19, ; CGL18, ; lewis2022quadratic, ))
has different fully correct executions in which different values are decided.
Concretely, it is ensured that, if all processes are correct and they all
propose the same value, that value will be decided.333In other words, all
these agreement algorithms satisfy _both_ _External Validity_ and _Weak
Validity_.

###### Corollary 0.

Let $\mathcal{A}$ be any algorithm that solves Byzantine agreement with
_External Validity_. Moreover, let there exist two executions
$\mathcal{E}_{0}$ and $\mathcal{E}_{1}$ of $\mathcal{A}$ such that (1) all
processes are correct in both $\mathcal{E}_{0}$ and $\mathcal{E}_{1}$, (2)
some value $v_{0}^{\prime}$ is decided in $\mathcal{E}_{0}$, and (3) some
value $v_{1}^{\prime}\neq v_{0}^{\prime}$ is decided in $\mathcal{E}_{1}$.
Then, $\mathcal{A}$ has at least $\frac{t^{2}}{32}$ message complexity.

##  5\. Solvability of Byzantine Agreement Problems

In this section, we observe that a deeper study of the containment relation
(introduced in § 4.2) enables us to deduce which Byzantine agreement problems
are solvable in synchrony. Concretely, we introduce the general solvability
theorem, which unifies all previous results on the synchronous solvability of
Byzantine agreement problems (e.g., (LSP82, ; FLM85, ; lynch1996distributed, ;
dolev1983authenticated, ; abraham2022authenticated, ; fitzi2003efficient, )).

###  5.1. Authenticated & Unauthenticated Algorithms

When it comes to the solvability of Byzantine agreement problems in synchrony,
authentication makes a significant difference. For instance,
(dolev1983authenticated, ) proved that authenticated Byzantine broadcast can
tolerate any number $t<n$ of corrupted processes, whereas (LSP82, ) showed
that unauthenticated Byzantine broadcast cannot be solved unless $n>3t$. We
thus distinguish two types of algorithms:

  * •

_Authenticated algorithms_ , which allow processes to sign their messages in a
way that prevents their signature from being forged by any other process
(Canetti04, ).

  * •

_Unauthenticated algorithms_ , which do not provide any mechanism for
signatures. (Note that the receiver of a message knows the identity of its
sender.)

A Byzantine agreement problem $\mathcal{P}$ is _authenticated-solvable_
(resp., _unauthenticated-solvable_) if and only if there exists an
authenticated (resp., unauthenticated) algorithm which solves
$\mathcal{P}$.444Recall that the exact specification of $\mathcal{P}$
(concretely, $\mathcal{P}$’s validity property) encodes the resilience of
$\mathcal{P}$.

##### Remark about unauthenticated algorithms.

This section assumes that unauthenticated algorithms confront the adversary
that is able to simulate other processes. In other words, we do not assume the
resource-restricted paradigm (Garay2020RRC, ), where the adversary’s
capability to simulate other processes can be restricted assuming a per-
process bounded rate of cryptographic puzzle-solving capability with no bound
on the number of corruptions and without any setup (i.e., without any
authentication mechanism) (Andrychowicz2015, ; Katz2014, ).

###  5.2. General Solvability Theorem

Before presenting our solvability theorem, we define its key component – the
_containment condition_.

###### Definition 0 (Containment condition).

A non-trivial agreement problem $\mathcal{P}$ with some validity property
$\mathit{val}$ satisfies the _containment condition_ ($\mathcal{CC}$, in
short) if and only if there exists a Turing-computable function
$\Gamma:\mathcal{I}\to\mathcal{V}_{O}$ such that:

$\forall
c\in\mathcal{I}:\Gamma(c)\in\bigcap\limits_{c^{\prime}\in\mathit{Cnt}(c)}\mathit{val}(c^{\prime}).$

Intuitively, a non-trivial agreement problem satisfies $\mathcal{CC}$ if and
only if there exists a finite procedure which, for every input configuration
$c\in\mathcal{I}$, returns a value that is admissible according to _all_ input
configurations to which $c$ reduces.

We are now ready to introduce the general solvability theorem:

###### Theorem 2 (General solvability theorem).

A non-trivial Byzantine agreement problem $\mathcal{P}$ is:

  * •

authenticated-solvable if and only if $\mathcal{P}$ satisfies $\mathcal{CC}$;
and

  * •

unauthenticated-solvable if and only if (1) $\mathcal{P}$ satisfies
$\mathcal{CC}$, and (2) $n>3t$.

To prove the general solvability theorem (Theorem 2), we show the following
three results:

  * •

_Necessity of $\mathcal{CC}$:_ If a non-trivial Byzantine agreement problem
$\mathcal{P}$ is authenticated- or unauthenticated-solvable, then
$\mathcal{P}$ satisfies $\mathcal{CC}$.

  * •

_Sufficiency of $\mathcal{CC}$:_ If a non-trivial Byzantine agreement problem
$\mathcal{P}$ satisfies $\mathcal{CC}$ (resp., satisfies $\mathcal{CC}$ and
$n>3t$), then $\mathcal{P}$ is authenticated-solvable (resp., unauthenticated-
solvable).

  * •

_Unauthenticated triviality when $n\leq 3t$:_ If a Byzantine agreement problem
$\mathcal{P}$ is unauthenticated-solvable with $n\leq 3t$, then $\mathcal{P}$
is trivial.

####  5.2.1. Necessity of $\mathcal{CC}$

The necessity of $\mathcal{CC}$ for solvable non-trivial agreement problems
follows directly from Lemma 3:

###### Lemma 0.

If a non-trivial Byzantine agreement problem $\mathcal{P}$ is authenticated-
or unauthenticated-solvable, then $\mathcal{P}$ satisfies $\mathcal{CC}$.

###### Proof.

Let $\mathcal{P}$ be any authenticated- or unauthenticated-solvable non-
trivial Byzantine agreement problem. Let $\mathit{val}$ denote the validity
property of $\mathcal{P}$. As $\mathcal{P}$ is solvable, there exists an
(authenticated or unauthenticated) algorithm $\mathcal{A}$ which solves it.

Let us fix any input configuration $c\in\mathcal{I}$. Consider any infinite
execution $\mathcal{E}\in\mathit{execs}(\mathcal{A})$ such that
$c=\mathsf{input\\_conf}(\mathcal{E})$. As $\mathcal{E}$ is infinite, some
correct process decides (in finitely many rounds) some value
$v^{\prime}\in\mathcal{V}_{O}$ (to satisfy _Termination_). Due to Lemma 3,
$v^{\prime}\in\bigcap\limits_{c^{\prime}\in\mathit{Cnt}(c)}\mathit{val}(c^{\prime})$.
Thus, $\Gamma(c)$ is defined (as $\Gamma(c)=v^{\prime}$) and is Turing-
computable ($\mathcal{A}$ computes it in $\mathcal{E}$). Hence, $\mathcal{P}$
satisfies $\mathcal{CC}$. ∎

####  5.2.2. Sufficiency of $\mathcal{CC}$

Let us start by recalling interactive consistency, a specific Byzantine
agreement problem. In interactive consistency, each process proposes its
value, and processes decide vectors of $n$ elements, one for each process
(i.e., $\mathcal{V}_{O}=\mathcal{I}_{n}$). Besides _Termination_ and
_Agreement_ , interactive consistency requires the following validity property
to hold:

  * •

_IC-Validity_ : Let $V$ denote the vector decided by a correct process. If a
correct process $p_{i}$ proposed a value $v$, then $V[i]=v$.

Using our formalism, _IC-Validity_ can be expressed as $\text{\emph{IC-
Validity}}(c)=\\{c^{\prime}\in\mathcal{I}_{n}\,|\,c^{\prime}\sqsupseteq c\\}$.
Importantly, interactive consistency is authenticated-solvable for any $n$ and
any $t\in[1,n-1]$ (dolev1983authenticated, ). On the other hand, interactive
consistency is unauthenticated-solvable if $n>3t$ (LSP82, ; FLM85, ).

To prove the sufficiency of $\mathcal{CC}$, we prove that any non-trivial
Byzantine agreement problem that satisfies $\mathcal{CC}$ can be reduced to
interactive consistency at no resilience penalty.

###### Lemma 0.

If a non-trivial Byzantine agreement problem $\mathcal{P}$ satisfies
$\mathcal{CC}$ (resp., satisfies $\mathcal{CC}$ and $n>3t$), then
$\mathcal{P}$ is authenticated-solvable (resp., unauthenticated-solvable).

###### Proof.

To prove the lemma, we design a reduction from $\mathcal{P}$ to interactive
consistency (Algorithm 2). Our reduction is comprised of two steps: (1) When a
correct process proposes to $\mathcal{P}$ (line 3), the process forwards its
proposal to the underlying interactive consistency algorithm (line 4). (2)
Once a correct process decides a vector $\mathit{vec}$ of $n$ proposals from
interactive consistency (line 5), the process decides $\Gamma(\mathit{vec})$
from $\mathcal{P}$ (line 6). _Termination_ and _Agreement_ of the reduction
algorithm follow directly from _Termination_ and _Agreement_ of interactive
consistency, respectively. Finally, let us prove that the reduction algorithm
satisfies the specific validity property $\mathit{val}$ of $\mathcal{P}$.
Consider any specific execution $\mathcal{E}$ of the reduction algorithm such
that $\mathsf{input\\_conf}(\mathcal{E})=c$, for some input configuration
$c\in\mathcal{I}$. Let $\mathit{vec}\in\mathcal{I}_{n}$ denote the vector
which a correct process decides from the underlying interactive consistency
algorithm (line 5). _IC-Validity_ ensures that $\mathit{vec}\sqsupseteq c$ as,
for every correct process $p_{i}$, $\mathit{vec}[i]=\mathsf{proposal}(c[i])$.
As $\mathcal{P}$ satisfies $\mathcal{CC}$,
$\Gamma(\mathit{vec})\in\mathit{val}(c)$, which proves that the reduction
algorithm satisfies $\mathit{val}$.

As interactive consistency is authenticated-solvable for any $n$ and any
$t\in[1,n-1]$ (dolev1983authenticated, ), a non-trivial Byzantine agreement
problem $\mathcal{P}$ which satisfies $\mathcal{CC}$ is authenticated-
solvable. Similarly, as interactive consistency is unauthenticated-solvable if
$n>3t$ (LSP82, ; FLM85, ), a non-trivial Byzantine agreement problem
$\mathcal{P}$ which satisfies $\mathcal{CC}$ with $n>3t$ is unauthenticated-
solvable. ∎

Algorithm 2 Reduction from $\mathcal{P}$ to interactive consistency:
Pseudocode for process $p_{i}$

1:Uses:

2: Interactive consistency, instance $\mathcal{IC}$

3:upon $\mathsf{propose}(v\in\mathcal{V}_{I})$:

4: invoke $\mathcal{IC}.\mathsf{propose}(v)$

5:upon $\mathcal{IC}.\mathsf{decide}(\mathit{vec}\in\mathcal{I}_{n})$:
$\triangleright$ processes decide input configurations with $n$ process-
proposal pairs

6: trigger $\mathsf{decide}\big{(}\Gamma(\mathit{vec})\big{)}$

####  5.2.3. Unauthenticated triviality when $n\leq 3t$

We prove that any agreement problem that is unauthenticated-solvable with
$n\leq 3t$ is trivial by contradiction. Namely, if there existed a non-trivial
agreement problem $\mathcal{P}$ that is unauthenticated-solvable with $n\leq
3t$, the reduction from weak consensus to $\mathcal{P}$ presented in Algorithm
1 would yield an unauthenticated weak consensus algorithm with $n\leq 3t$,
which is known to be impossible (FLM85, ).

###### Lemma 0.

If a Byzantine agreement problem $\mathcal{P}$ is unauthenticated-solvable
with $n\leq 3t$, then $\mathcal{P}$ is trivial.

###### Proof.

By contradiction, let $\mathcal{P}$ be non-trivial. As weak consensus can be
reduced to any solvable non-trivial agreement problem at no resilience penalty
(see Algorithm 1), weak consensus is unauthenticated-solvable with $n\leq 3t$.
This is a contradiction with the fact that weak consensus is unauthenticated-
solvable only if $n>3t$ (FLM85, ). ∎

###  5.3. General Solvability Theorem: Application to Strong Consensus

Here, we show how the general solvability theorem (Theorem 2) can be applied
with the example of strong consensus. (Recall that strong consensus satisfies
_Strong Validity_ : if all correct processes propose the same value, that
value must be decided.) Namely, it is known that strong consensus is
authenticated-solvable only if $n>2t$ (abraham2022authenticated, ). The
general solvability theorem enables us to obtain another proof of this claim.

###### Theorem 6 (Proven in (abraham2022authenticated, )).

Strong consensus is authenticated-solvable only if $n>2t$.

###### Proof.

To prove the theorem, we show that strong consensus does not satisfy
$\mathcal{CC}$ with $n\leq 2t$. Without loss of generality, let $n=2t$ and let
$\mathcal{V}_{I}=\mathcal{V}_{O}=\\{0,1\\}$. Consider the input configuration
$c\in\mathcal{I}_{n}$ such that (1) for every $i\in[1,t]$,
$\mathsf{proposal}(c[i])=0$, and (2) for every $i\in[t+1,n]$,
$\mathsf{proposal}(c[i])=1$. That is, the proposal of the first $t$ processes
is $0$, whereas the proposal of the other processes is $1$. Note that both $0$
and $1$ are admissible according to $c$. Importantly, $c$ contains
$c_{0}\in\mathcal{I}_{t}$, where $\pi(c_{0})=\\{p_{1},p_{2},...,p_{t}\\}$ and
$\mathsf{proposal}(c_{0}[i])=0$, for every $i\in[1,t]$. Similarly, $c$
contains $c_{1}\in\mathcal{I}_{t}$, where
$\pi(c_{0})=\\{p_{t+1},p_{t+2},...,p_{n}\\}$ and
$\mathsf{proposal}(c_{0}[i])=1$, for every $i\in[t+1,n]$. According to $c_{0}$
(resp., $c_{1}$), only $0$ (resp., $1$) is admissible. Hence, strong consensus
with $n\leq 2t$ does not satisfy $\mathcal{CC}$ as $c$ contains two input
configurations (namely, $c_{0}$ and $c_{1}$) which do not have a common
admissible value. ∎

##  6\. Related Work

##### Reductions and equivalences between Byzantine agreement problems.

Interactive consistency can be reduced to $n$ (parallel) instances of
Byzantine broadcast (Nayak2020a, ). In the honest-majority setting
($t<\frac{n}{2}$), Byzantine broadcast and strong consensus are
computationally equivalent (lynch1996distributed, ; AW04, ). Moreover,
Byzantine broadcast can be reduced to strong consensus with only $O(n)$
additional exchanged messages (lynch1996distributed, ; AW04, ). Furthermore,
it is known that weak consensus is reducible to strong consensus (and, thus,
to Byzantine broadcast) (lynch1996distributed, ; AW04, ).

##### Deterministic Byzantine agreement in synchrony.

In their seminal paper, (dolev1985bounds, ) established a quadratic lower
bound on message complexity of deterministic Byzantine broadcast (and,
consequently, strong consensus). It is shown that, in the authenticated
setting (with idealized digital signatures (Canetti04, )), deterministic
Byzantine broadcast algorithms must exchange $\Omega(nt)$ signatures and
$\Omega(n+t^{2})$ messages. Similarly, their proof shows that, in the
unauthenticated setting, there exists an execution with $\Omega(nt)$ exchanged
messages. The $\Omega(nt)$ bound on exchanged signatures is proven to be tight
when $t<\frac{n}{2}-O(1)$ and $t\in\Theta(n)$ (Momose2021, ). Additionally,
(berman1992bit, ) proved that the $\Omega(nt)$ bound on message complexity in
the unauthenticated setting is tight when $t\in\Theta(n)$. The
$\Omega(n+t^{2})$ bound on message complexity in the authenticated setting has
recently been proven to be tight (Chlebus23, ). A quadratic lower bound on the
message complexity of binary crusader broadcast, a problem in which
disagreements are sometimes allowed, has also been shown in (AbrahamStern22,
). Lower bounds on other relevant metrics, such as resilience, network
connectivity, or latency, have also been established (FLM85, ;
dolev1983authenticated, ; dolev2013early, ).

By employing threshold signatures (Shoup00, ), which extend beyond the
idealized authenticated model, the word complexity of $O(n(f+1))$, where
$f\leq t<\frac{n}{2}$ represents the actual number of failures and a word
contains a constant number of values and signatures, can be achieved for
Byzantine agreement with _External Validity_ (spiegelman2020search, ) and
Byzantine broadcast (cohen2023make, ; strong, ) by utilizing the algorithm of
(Momose2021, ). Additionally, an amortized cost of $O(n)$ is attainable in
multi-shot Byzantine broadcast (wan2023amortized, ). Amortization is similarly
possible with long inputs (Chen2021, ; Nayak2020a, ). In the dishonest-
majority setting (with $t\geq\frac{n}{2}$), the most efficient broadcast
constructions are based on the deterministic broadcast protocol of
(dolev1985bounds, ) with a cubic message complexity.

##### Randomized Byzantine agreement in synchrony.

Even with randomization, no Byzantine broadcast algorithm can achieve sub-
quadratic expected message complexity against a strongly rushing adaptive
adversary equipped with after-the-fact message removal capabilities
(Abraham2019c, ). However, designing randomized synchronous Byzantine
agreement algorithms with sub-quadratic expected message complexity is
possible against a weaker adversary. In certain models, such as those with a
static adversary (Boyle2021, ; King2011a, ) or with (only) private channels
(King2011, ), algorithms with a sub-linear number of messages (or bits) sent
per correct process can be designed (Gelles, ; Gelles23, ; King2011a, ;
King2009, ; King2011, ; Boyle2021, ; Boyle2018b, ).

When the adversary is adaptive (without after-the-fact message removal
capabilities) and computationally bounded, there exist Byzantine agreement
algorithms (Chen2019, ; Abraham2019c, ; RambaudBootstrapping, ) which achieve
both sub-quadratic (but unbalanced) communication and constant latency in
expectation by relying on a verifiable random function (VRF)
(DBLP:conf/focs/MicaliRV99, ). It has been shown that, in the idealized
authenticated setting (Canetti04, ) (which is strictly weaker than bare or
bulletin-board PKI (Canetti00, ; Boyle2021, ; RambaudBootstrapping, )), in the
presence of a rushing adaptive adversary, no randomized protocol can achieve a
sub-quadratic expected communication complexity in the synchronous multi-cast
model, where a sent message is necessarily sent to all the processes
(RambaudBootstrapping, ).

A VRF setup and a sub-quadratic binary strong consensus algorithm were shown
to yield a $O(n\ell+n\mathit{poly}(\kappa))$ bit complexity, where $\ell$ is
the proposal size and $\kappa$ is the security parameter, for solving strong
consensus with long inputs (Bhangale2022, ). State-of-the-art algorithms for
interactive consistency with long inputs (of size $\ell$) yield the bit
complexity of $O(n^{2}\ell+n^{2}\kappa^{3})$ (Bhangale2022, ) or
$O(n^{2}\ell+n^{3}\kappa)$ (Abraham2023a, ).

In the dishonest-majority setting, (Blum2023, ) establishes new lower bounds
on the expected message complexity for Byzantine broadcast: no (randomized)
algorithm can achieve sub-quadratic message complexity with only $O(1)$
correct processes. The algorithm of (Chan2020, ) achieves the bit complexity
of $O(n^{2}\kappa^{2})$ for binary Byzantine broadcast. (Tsimos2022, ) proves
that an $\tilde{O}(n^{2}\mathit{poly}(\kappa))$ bit complexity can be achieved
for binary interactive consistency. Randomization additionally helps in
circumventing the Dolev-Strong lower bound (dolev1983authenticated, ) which
states that $t+1$ rounds are necessary in the worst case to deterministically
solve Byzantine broadcast (dolev1983authenticated, ). While using
randomization for circumventing the Dolev-Strong lower bound is well-
established for the honest-majority setting (KatzKoo2009, ;
abraham2019synchronous, ; Abraham2019c, ; RambaudBootstrapping, ), recent
findings have proven that the same approach can be utilized even in the
presence of a dishonest majority (Wan2020, ; Wan2020a, ; Chan2020, ).

##### Byzantine agreement in partial synchrony and asynchrony.

The worst-case complexity of all Byzantine agreement problems in partial
synchrony was studied in (validity_podc, ) where it was proven that any
specific Byzantine agreement problem requires $\Theta(n^{2})$ exchanged
messages (after the network has stabilized) in the worst case. Prior to
(validity_podc, ), it was shown that there exist deterministic algorithms,
building on top of threshold signatures and HotStuff (YMR19, ), which achieve
$O(n^{2})$ word complexity for strong consensus (lewis2022quadratic, ;
civit2022byzantine, ). Recently, (everyBitCounts, ) proved that vector
consensus, a Byzantine agreement problem in which processes agree on the
proposals of $n-t$ processes, can be solved with $O(n^{2.5})$ or $O(n^{2})$
words (when employing STARK proofs (Ben-Sasson_stark, )). In the randomized
paradigm, there exist VRF-based sub-quadratic Byzantine agreement protocols
(Chen2019, ; Abraham2019c, ; RambaudBootstrapping, ; Sheng22, ). Moreover, it
is possible to achieve $O(n\ell+n\mathit{poly}(\kappa))$ bit complexity for
strong consensus with long inputs of size $\ell$ (Bhangale2022, ).
Furthermore, reaching the communication complexity of $O(n\ell+n^{2}\kappa)$
for validated asynchronous Byzantine agreement was proven to be possible:
(LL0W20, ) and (Nayak2020a, ) achieve the aforementioned bound by extending
the VABA protocol of (abraham2019asymptotically, ). With some additional
assumptions (e.g., private setup or delayed adversary), it is possible to
design a sub-quadratic asynchronous Byzantine agreement algorithm (Blum2020, ;
CKS20, ). A generic transformation proposed in (Bhangale2022, ) produces, on
top of any asynchronous sub-quadratic Byzantine agreement algorithm, an
asynchronous solution with $O(n\ell+n\mathit{poly}(\kappa))$ bit complexity.

##  7\. Concluding Remarks

We study in this paper the necessary worst-case communication cost for all
Byzantine agreement problems. We show that any (deterministic) solution to any
solvable non-trivial Byzantine agreement problem exchanges $\Omega(t^{2})$
messages in the worst-case. We prove the general lower bound in two steps: (1)
we show that weak consensus (yin2019hotstuff, ; lewis2022quadratic, ;
civit2022byzantine, ; BKM19, ) requires $\Omega(t^{2})$ exchanged messages
even in synchrony; (2) we design a reduction from weak consensus to any
solvable non-trivial Byzantine agreement problem, thus generalizing the
$\Omega(t^{2})$ bound. Interestingly, our reduction allows us to determine a
general result about the synchronous solvability of Byzantine agreement, thus
demarcating the entire landscape of solvable (and unsolvable) variants of the
problem.

We plan on extending our results to the randomized setting. Concretely, the
goal is to study the cost of solving randomized Byzantine agreement against an
adaptive adversary, with after-the-fact message removal capabilities
(Abraham2019c, ) or the ability to access the internal states of all processes
(DBLP:conf/soda/HuangPZ23, ). It would also be interesting to extend our work
to problems which do not require agreement (e.g., approximate (AbrahamAD04, ;
MendesH13, ; GhineaLW22, ; ghinea2023multidimensional, ) or $k$-set
(BouzidIR16, ; Delporte-Gallet20, ; Delporte-Gallet22, ; lynch1996distributed,
) agreement). Finally, improving the known upper bounds on the cost of solving
Byzantine agreement problems constitutes another important research direction.

## References

  * (1) Abd-El-Malek, M., Ganger, G. R., Goodson, G. R., Reiter, M. K., and Wylie, J. J. Fault-Scalable Byzantine Fault-Tolerant Services.  ACM SIGOPS Operating Systems Review 39, 5 (2005), 59–74.
  * (2) Abraham, I., Amit, Y., and Dolev, D. Optimal Resilience Asynchronous Approximate Agreement.  In Principles of Distributed Systems, 8th International Conference, OPODIS 2004, Grenoble, France, December 15-17, 2004, Revised Selected Papers (2004), T. Higashino, Ed., vol. 3544 of Lecture Notes in Computer Science, Springer, pp. 229–239.
  * (3) Abraham, I., Chan, T. H., Dolev, D., Nayak, K., Pass, R., Ren, L., and Shi, E. Communication complexity of byzantine agreement, revisited.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (2019), 317–326.
  * (4) Abraham, I., Chan, T. H., Dolev, D., Nayak, K., Pass, R., Ren, L., and Shi, E. Communication complexity of byzantine agreement, revisited.  Distributed Comput. 36, 1 (2023), 3–28.
  * (5) Abraham, I., Devadas, S., Dolev, D., Nayak, K., and Ren, L. Synchronous Byzantine Agreement with Expected $O(1)$ Rounds, Expected $O(n^{2})$ Communication, and Optimal Resilience.  In Financial Cryptography and Data Security - 23rd International Conference (2019), vol. 11598 LNCS, pp. 320–334.
  * (6) Abraham, I., Dolev, D., Kagan, A., and Stern, G. Authenticated Consensus in Synchronous Systems with Mixed Faults.  Cryptology ePrint Archive (2022).
  * (7) Abraham, I., Jovanovic, P., Maller, M., Meiklejohn, S., Stern, G., and Tomescu, A. Reaching Consensus for Asynchronous Distributed Key Generation.  In PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021 (2021), A. Miller, K. Censor-Hillel, and J. H. Korhonen, Eds., ACM, pp. 363–373.
  * (8) Abraham, I., Malkhi, D., Nayak, K., Ren, L., and Spiegelman, A. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus.  arXiv preprint arXiv:1612.02916 (2016).
  * (9) Abraham, I., Malkhi, D., Nayak, K., Ren, L., and Spiegelman, A. Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus.  CoRR, abs/1612.02916 (2016).
  * (10) Abraham, I., Malkhi, D., and Spiegelman, A. Asymptotically Optimal Validated Asynchronous Byzantine Agreement.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (2019), pp. 337–346.
  * (11) Abraham, I., Nayak, K., Ren, L., and Xiang, Z. Good-case Latency of Byzantine Broadcast: A Complete Categorization.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (2021), pp. 331–341.
  * (12) Abraham, I., Nayak, K., and Shrestha, N. Communication and Round Efficient Parallel Broadcast Protocols.  In IACR Cryptol. ePrint Arch. (2023), pp. 1–22.
  * (13) Abraham, I., and Stern, G. New dolev-reischuk lower bounds meet blockchain eclipse attacks.  In 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium (2022), E. Hillel, R. Palmieri, and E. Rivière, Eds., vol. 253 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 16:1–16:18.
  * (14) Adya, A., Bolosky, W., Castro, M., Cermak, G., Chaiken, R., Douceur, J., Howell, J., Lorch, J., Theimer, M., and Wattenhofer, R. $\\{$FARSITE$\\}$: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment.  In 5th Symposium on Operating Systems Design and Implementation (OSDI 02) (2002).
  * (15) Amir, Y., Danilov, C., Kirsch, J., Lane, J., Dolev, D., Nita-Rotaru, C., Olsen, J., and Zage, D. Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks.  In International Conference on Dependable Systems and Networks (DSN’06) (2006), IEEE, pp. 105–114.
  * (16) Andrychowicz, M., and Dziembowski, S. Pow-based distributed cryptography with no trusted setup.  In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II (2015), R. Gennaro and M. Robshaw, Eds., vol. 9216 of Lecture Notes in Computer Science, Springer, pp. 379–399.
  * (17) Attiya, H., and Welch, J. L. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.).  Wiley series on parallel and distributed computing. Wiley, 2004.
  * (18) Ben-Or, M., and El-Yaniv, R. Resilient-optimal interactive consistency in constant time.  Distributed Computing 16, 4 (2003), 249–262.
  * (19) Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. Scalable, transparent, and post-quantum secure computational integrity.  IACR Cryptol. ePrint Arch. (2018), 46.
  * (20) Berman, P., Garay, J. A., and Perry, K. J. Bit Optimal Distributed Consensus.  In Computer science: research and applications. Springer, 1992, pp. 313–321.
  * (21) Bhangale, A., Liu-Zhang, C. D., Loss, J., and Nayak, K. Efficient Adaptively-Secure Byzantine Agreement for Long Messages.  In Advances in Cryptology - ASIACRYPT - 28th International Conference on the Theory and Application of Cryptology and Information Security (Taipei, Taiwan, 2022), vol. 13791 LNCS, pp. 504–525.
  * (22) Blum, E., Boyle, E., Cohen, R., and Liu-Zhang, C.-D. Communication Lower Bounds for Cryptographic Broadcast Protocols.  In 37th International Symposium on Distributed Computing (DISC) (L’Aquila, Italy, 2023), pp. 10:1—-10:19.
  * (23) Blum, E., Katz, J., Liu-Zhang, C., and Loss, J. Asynchronous byzantine agreement with subquadratic communication.  In Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part I (2020), R. Pass and K. Pietrzak, Eds., vol. 12550 of Lecture Notes in Computer Science, Springer, pp. 353–380.
  * (24) Bouzid, Z., Imbs, D., and Raynal, M. A necessary condition for Byzantine k-set agreement.  Inf. Process. Lett. 116, 12 (2016), 757–759.
  * (25) Boyle, E., Cohen, R., and Goel, A. Breaking the O($\surd$ n)-bit barrier: Byzantine agreement with polylog bits per party.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (2021), 319–330.
  * (26) Boyle, E., Jain, A., Prabhakaran, M., and Yu, C. H. The bottleneck complexity of secure multiparty computation.  In 45th International Colloquium on Automata, Languages, and Programming, (ICALP) (Prague, Czech Republic, 2018), vol. 107, pp. 1–16.
  * (27) Buchman, E. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains.  PhD thesis, University of Guelph, 2016.
  * (28) Buchman, E., Kwon, J., and Milosevic, Z. The latest gossip on BFT consensus.  Tech. Rep. 1807.04938, arXiv, 2019.
  * (29) Cachin, C., Kursawe, K., Petzold, F., and Shoup, V. Secure and Efficient Asynchronous Broadcast Protocols.  In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings (2001), J. Kilian, Ed., vol. 2139 of Lecture Notes in Computer Science, Springer, pp. 524–541.
  * (30) Canetti, R. Universally composable signature, certification, and authentication.  In 17th IEEE Computer Security Foundations Workshop, (CSFW-17 2004), 28-30 June 2004, Pacific Grove, CA, USA (2004), IEEE Computer Society, p. 219.
  * (31) Canetti, R., Goldreich, O., Goldwasser, S., and Micali, S. Resettable zero-knowledge (extended abstract).  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA (2000), F. F. Yao and E. M. Luks, Eds., ACM, pp. 235–244.
  * (32) Castro, M., and Liskov, B. Practical Byzantine Fault Tolerance and Proactive Recovery.  ACM Transactions on Computer Systems 20, 4 (2002).
  * (33) Chan, T. H., Pass, R., and Shi, E. Sublinear-Round Byzantine Agreement Under Corrupt Majority.  In Public-Key Cryptography (Edinburgh, UK, 2020), vol. 12111 LNCS, pp. 246–265.
  * (34) Chen, J. Optimal error-free multi-valued byzantine agreement, 2021.
  * (35) Chen, J., and Micali, S. Algorand: A secure and efficient distributed ledger.  Theoretical Computer Science 777 (2019), 155–183.
  * (36) Chlebus, B. S., Kowalski, D. R., and Olkowski, J. Deterministic fault-tolerant distributed computing in linear time and communication.  In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023 (2023), R. Oshman, A. Nolin, M. M. Halldórsson, and A. Balliu, Eds., ACM, pp. 344–354.
  * (37) Civit, P., Dzulfikar, M. A., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J., and Vidigueira, M. Byzantine Consensus is $\Theta(n^{2})$: The Dolev-Reischuk Bound is Tight even in Partial Synchrony!  In 36th International Symposium on Distributed Computing (DISC 2022) (Dagstuhl, Germany, 2022), C. Scheideler, Ed., vol. 246 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 14:1–14:21.
  * (38) Civit, P., Gilbert, S., Guerraoui, R., Komatovic, J., Monti, M., and Vidigueira, M. Every Bit Counts in Consensus.  In 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy (2023), R. Oshman, Ed., vol. 281 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 13:1–13:26.
  * (39) Civit, P., Gilbert, S., Guerraoui, R., Komatovic, J., and Vidigueira, M. On the Validity of Consensus.  In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023 (2023), R. Oshman, A. Nolin, M. M. Halldórsson, and A. Balliu, Eds., ACM, pp. 332–343.
  * (40) Civit, P., Gilbert, S., Guerraoui, R., Komatovic, J., and Vidigueira, M. Strong byzantine agreement with adaptive word complexity.  arXiv preprint arXiv:2308.03524 (2023).
  * (41) Coan, B. A., and Welch, J. L. Modular Construction of a Byzantine Agreement Protocol with Optimal Message Bit Complexity.  Inf. Comput. 97, 1 (1992), 61–85.
  * (42) Cohen, S., Keidar, I., and Spiegelman, A. Not a coincidence: Sub-quadratic asynchronous byzantine agreement WHP.  In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference (2020), H. Attiya, Ed., vol. 179 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 25:1–25:17.
  * (43) Cohen, S., Keidar, I., and Spiegelman, A. Make every word count: Adaptive byzantine agreement with fewer words.  In 26th International Conference on Principles of Distributed Systems (OPODIS 2022) (2023), Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * (44) Correia, M. From Byzantine Consensus to Blockchain Consensus.  In Essentials of Blockchain Technology. Chapman and Hall/CRC, 2019, pp. 41–80.
  * (45) Crain, T., Gramoli, V., Larrea, M., and Raynal, M. DBFT: Efficient Leaderless Byzantine Consensus and its Applications to Blockchains.  In Proceedings of the 17th IEEE International Symposium on Network Computing and Applications (NCA’18) (2018), IEEE.
  * (46) Das, S., Yurek, T., Xiang, Z., Miller, A., Kokoris-Kogias, L., and Ren, L. Practical Asynchronous Distributed Key Generation.  In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022 (2022), IEEE, pp. 2518–2534.
  * (47) Deligios, G., Hirt, M., and Liu-Zhang, C. Round-Efficient Byzantine Agreement and Multi-party Computation with Asynchronous Fallback.  In Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part I (2021), K. Nissim and B. Waters, Eds., vol. 13042 of Lecture Notes in Computer Science, Springer, pp. 623–653.
  * (48) Delporte-Gallet, C., Fauconnier, H., Raynal, M., and Safir, M. Optimal algorithms for synchronous byzantine k-set agreement.  In Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Clermont-Ferrand, France, November 15-17, 2022, Proceedings (2022), S. Devismes, F. Petit, K. Altisen, G. A. D. Luna, and A. F. Anta, Eds., vol. 13751 of Lecture Notes in Computer Science, Springer, pp. 178–192.
  * (49) Delporte-Gallet, C., Fauconnier, H., and Safir, M. Byzantine k-Set Agreement.  In Networked Systems - 8th International Conference, NETYS 2020, Marrakech, Morocco, June 3-5, 2020, Proceedings (2020), C. Georgiou and R. Majumdar, Eds., vol. 12129 of Lecture Notes in Computer Science, Springer, pp. 183–191.
  * (50) Dolev, D., and Lenzen, C. Early-deciding consensus is expensive.  In Proceedings of the 2013 ACM symposium on Principles of distributed computing (2013), pp. 270–279.
  * (51) Dolev, D., and Reischuk, R. Bounds on Information Exchange for Byzantine Agreement.  Journal of the ACM (JACM) 32, 1 (1985), 191–204.
  * (52) Dolev, D., and Strong, H. R. Authenticated Algorithms for Byzantine Agreement.  SIAM Journal on Computing 12, 4 (1983), 656–666.
  * (53) Dwork, C., Lynch, N., and Stockmeyer, L. Consensus in the Presence of Partial Synchrony.  Journal of the Association for Computing Machinery, Vol. 35, No. 2, pp.288-323 (1988).
  * (54) Fischer, M. J., and Lynch, N. A. A lower bound for the time to assure interactive consistency.  Inf. Process. Lett. 14, 4 (1982), 183–186.
  * (55) Fischer, M. J., Lynch, N. A., and Merritt, M. Easy Impossibility Proofs for Distributed Consensus Problems.  In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, Minaki, Ontario, Canada, August 5-7, 1985 (1985), M. A. Malcolm and H. R. Strong, Eds., ACM, pp. 59–70.
  * (56) Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of Distributed Consensus with One Faulty Process.  Journal of the ACM (JACM) 32, 2 (1985), 374–382.
  * (57) Fitzi, M., and Garay, J. A. Efficient Player-Optimal Protocols for Strong and Differential Consensus.  In Proceedings of the twenty-second annual symposium on Principles of distributed computing (2003), pp. 211–220.
  * (58) Fitzi, M., Gisin, N., Maurer, U. M., and von Rotz, O. Unconditional Byzantine Agreement and Multi-party Computation Secure against Dishonest Minorities from Scratch.  In Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings (2002), L. R. Knudsen, Ed., vol. 2332 of Lecture Notes in Computer Science, Springer, pp. 482–501.
  * (59) Galil, Z., Haber, S., and Yung, M. Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model.  In Conference on the Theory and Application of Cryptographic Techniques (1987), Springer, pp. 135–155.
  * (60) Garay, J. A., Kiayias, A., Ostrovsky, R. M., Panagiotakos, G., and Zikas, V. Resource-restricted cryptography: Revisiting MPC bounds in the proof-of-work era.  In Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II (2020), A. Canteaut and Y. Ishai, Eds., vol. 12106 of Lecture Notes in Computer Science, Springer, pp. 129–158.
  * (61) Gelles, Y., and Komargodski, I. Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency.  37th International Symposium on Distributed Computing, (DISC) (2023), 42:1—-42:6.
  * (62) Gelles, Y., and Komargodski, I. Optimal Load-Balanced Scalable Distributed Agreement.  In IACR Cryptol. ePrint Arch. (2023).
  * (63) Gennaro, R., Ishai, Y., Kushilevitz, E., and Rabin, T. On 2-Round Secure Multiparty Computation.  In Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings (2002), M. Yung, Ed., vol. 2442 of Lecture Notes in Computer Science, Springer, pp. 178–193.
  * (64) Ghinea, D., Liu-Zhang, C., and Wattenhofer, R. Optimal Synchronous Approximate Agreement with Asynchronous Fallback.  In PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022 (2022), A. Milani and P. Woelfel, Eds., ACM, pp. 70–80.
  * (65) Ghinea, D., Liu-Zhang, C.-D., and Wattenhofer, R. Multidimensional Approximate Agreement with Asynchronous Fallback.  Cryptology ePrint Archive (2023).
  * (66) Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. Algorand: Scaling Byzantine Agreements for Cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles (New York, NY, USA, 2017), SOSP ’17, Association for Computing Machinery, p. 51–68.
  * (67) Gilbert, S., Lynch, N. A., and Shvartsman, A. A. Rambo: A Robust, Reconfigurable Atomic Memory Service for Dynamic Networks.  Distributed Computing 23, 4 (2010), 225–272.
  * (68) Hadzilacos, V., and Halpern, J. Y. Message-optimal protocols for byzantine agreement.  In Proceedings of the tenth annual ACM symposium on Principles of distributed computing (1991), pp. 309–323.
  * (69) Huang, S., Pettie, S., and Zhu, L. Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (2023), N. Bansal and V. Nagarajan, Eds., SIAM, pp. 4335–4353.
  * (70) Katz, J., and Koo, C. On expected constant-round protocols for byzantine agreement.  J. Comput. Syst. Sci. 75, 2 (2009), 91–112.
  * (71) Katz, J., Miller, A., and Shi, E. Pseudonymous secure computation from time-lock puzzles.  IACR Cryptol. ePrint Arch. (2014), 857.
  * (72) King, V., Lonargan, S., Saia, J., and Trehan, A. Load balanced scalable byzantine agreement through quorum building, with full information.  Distributed Computing and Networking - 12th International Conference (ICDCN) 6522 LNCS (2011), 203–214.
  * (73) King, V., and Saia, J. From almost everywhere to everywhere: Byzantine agreement with Õ (n3/2) bits.  In Distributed Computing, 23rd International Symposium (DISC) (2009), vol. 5805 LNCS, pp. 464–478.
  * (74) King, V., and Saia, J. Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary.  Journal of the ACM 58, 4 (2011), 1–24.
  * (75) Kokoris-Kogias, E., Malkhi, D., and Spiegelman, A. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.  In CCS ’20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020 (2020), J. Ligatti, X. Ou, J. Katz, and G. Vigna, Eds., ACM, pp. 1751–1767.
  * (76) Kotla, R., Alvisi, L., Dahlin, M., Clement, A., and Wong, E. Zyzzyva: Speculative Byzantine Fault Tolerance.  In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles (2007), pp. 45–58.
  * (77) Kotla, R., and Dahlin, M. High Throughput Byzantine Fault Tolerance.  In International Conference on Dependable Systems and Networks, 2004 (2004), IEEE, pp. 575–584.
  * (78) Lamport, L., Shostak, R., and Pease, M. The Byzantine Generals Problem.  ACM Transactions on Programming Languages and Systems 4, 3 (1982), 382–401.
  * (79) Lewis-Pye, A. Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model.  arXiv preprint arXiv:2201.01107 (2022).
  * (80) Lu, Y., Lu, Z., Tang, Q., and Wang, G. Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited.  In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020 (2020), Y. Emek and C. Cachin, Eds., ACM, pp. 129–138.
  * (81) Luu, L., Narayanan, V., Baweja, K., Zheng, C., Gilbert, S., and Saxena, P. SCP: A Computationally-Scalable Byzantine Consensus Protocol For Blockchains.  Cryptology ePrint Archive (2015).
  * (82) Lynch, N. A. Distributed Algorithms.  Elsevier, 1996.
  * (83) Malkhi, D., Nayak, K., and Ren, L. Flexible Byzantine Fault Tolerance.  In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security (2019), pp. 1041–1053.
  * (84) Mendes, H., and Herlihy, M. Multidimensional Approximate Agreement in Byzantine Asynchronous Systems.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 (2013), D. Boneh, T. Roughgarden, and J. Feigenbaum, Eds., ACM, pp. 391–400.
  * (85) Micali, S., Rabin, M. O., and Vadhan, S. P. Verifiable Random Functions.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA (1999), IEEE Computer Society, pp. 120–130.
  * (86) Momose, A., and Ren, L. Multi-Threshold Byzantine Fault Tolerance.  In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (2021), pp. 1686–1699.
  * (87) Momose, A., and Ren, L. Optimal Communication Complexity of Authenticated Byzantine Agreement.  In 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference) (2021), S. Gilbert, Ed., vol. 209 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 32:1–32:16.
  * (88) Nayak, K., Ren, L., Shi, E., Vaidya, N. H., and Xiang, Z. Improved extension protocols for byzantine broadcast and agreement.  34th International Symposium on Distributed Computing (DISC) 2020 179 (2020), 1–29.
  * (89) Rambaud, M. Bootstrapping Message-Linear-Constant-Round Consensus from a Bare PKI Setup , and Separation Bounds from the Idealized Message-Authentication Model.
  * (90) Sheng, P., Wang, G., Nayak, K., Kannan, S., and Viswanath, P. Player-replaceability and forensic support are two sides of the same (crypto) coin.  IACR Cryptol. ePrint Arch. (2022), 1513.
  * (91) Shoup, V. Practical threshold signatures.  In Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding (2000), B. Preneel, Ed., vol. 1807 of Lecture Notes in Computer Science, Springer, pp. 207–220.
  * (92) Shrestha, N., Bhat, A., Kate, A., and Nayak, K. Synchronous Distributed Key Generation without Broadcasts.  IACR Cryptol. ePrint Arch. (2021), 1635.
  * (93) Spiegelman, A. In search for an optimal authenticated byzantine agreement.  arXiv preprint arXiv:2002.06993 (2020).
  * (94) Tsimos, G., Loss, J., and Papamanthou, C. Gossiping for Communication-Efficient Broadcast.  Advances in Cryptology - CRYPTO - 42nd Annual International Cryptology Conference 13509 LNCS (2022), 439–469.
  * (95) Veronese, G. S., Correia, M., Bessani, A. N., Lung, L. C., and Verissimo, P. Efficient Byzantine Fault-Tolerance.  IEEE Transactions on Computers 62, 1 (2011), 16–30.
  * (96) Wan, J., Momose, A., Ren, L., Shi, E., and Xiang, Z. On the Amortized Communication Complexity of Byzantine Broadcast.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (2023), 253–261.
  * (97) Wan, J., Momose, A., Ren, L., Shi, E., and Xiang, Z. On the Amortized Communication Complexity of Byzantine Broadcast.  In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (2023), pp. 253–261.
  * (98) Wan, J., Xiao, H., Devadas, S., and Shi, E. Round-efficient byzantine broadcast under strongly adaptive and majority corruptions.  In Theory of Cryptography (TCC) (Durham, NC, USA,, 2020), vol. 12550 LNCS, pp. 412–456.
  * (99) Wan, J., Xiao, H., Shi, E., and Devadas, S. Expected constant round byzantine broadcast under dishonest majority.  Theory of Cryptography - 18th International Conference (TCC) 12550 LNCS (2020), 381–411.
  * (100) Yin, M., Malkhi, D., Reiter, M. K., Golan-Gueta, G., and Abraham, I. HotStuff: BFT consensus with linearity and responsiveness.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (2019), pp. 347–356.
  * (101) Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., and Abraham, I. HotStuff: BFT Consensus with Linearity and Responsiveness.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (2019), pp. 347–356.

##  Appendix A Proofs of Lemmas 4 and 6

In this section, we formally prove lemmas 4 and 6. Recall that, in § 3, we fix
a weak consensus algorithm $\mathcal{A}$ which tolerates up to $t<n$ omission
failures. First, we introduce the computational model (§ A.1). Then, we show
preliminary lemmas (§ A.2) required for proving lemmas 4 and 6 (§ A.3).

###  A.1. Computational Model

Without loss of generality, we assume that each process sends at most one
message to any specific process in a single round. That is, $\mathcal{A}$
instructs no process $p_{i}\in\Pi$ to send two (or more) messages to any
specific process $p_{j}\in\Pi$ in a single round. Moreover, we assume that no
process sends messages to itself.

####  A.1.1. Messages.

Let $\mathcal{M}$ denote the set of messages. Each message $m\in\mathcal{M}$
encodes the following:

  * •

the sender of $m$ (denoted by $m.\mathsf{sender}\in\Pi$); and

  * •

the receiver of $m$ (denoted by $m.\mathsf{receiver}\in\Pi$); and

  * •

the round (denoted by $m.\mathsf{round}\in\mathbb{N}$).

Due to our assumption that only one message is sent in a round from any
specific process to any other specific process, no message $m$ is sent more
than once in any execution of $\mathcal{A}$.

####  A.1.2. States.

Let $\mathcal{S}$ denote the set of states. Each state $s\in\mathcal{S}$
encodes the following:

  * •

the process associated with $s$ (denoted by $s.\mathsf{process}\in\Pi$); and

  * •

the round associated with $s$ (denoted by $s.\mathsf{round}\in\mathbb{N}$);
and

  * •

the proposal-bit associated with $s$ (denoted by
$s.\mathsf{proposal}\in\\{0,1\\}$); and

  * •

the decision-bit associated with $s$ (denoted by
$s.\mathsf{decision}\in\\{\bot,0,1\\}$).

Intuitively, a state $s\in\mathcal{S}$, where (1) $s.\mathsf{process}=p_{i}$,
(2) $s.\mathsf{round}=k$, (3) $s.\mathsf{proposal}=b$, and (4)
$s.\mathsf{decision}=b^{\prime}$, denotes the state of process $p_{i}$ at the
start of round $k$ with $p_{i}$’s proposal being $b$ and $p_{i}$’s decision
being $b^{\prime}$ (if $b^{\prime}=\bot$, $p_{i}$ has not yet decided by the
start of round $k$).

For each process $p_{i}$, there are two _initial states_ $0_{i}\in\mathcal{S}$
and $1_{i}\in\mathcal{S}$ associated with $p_{i}$ such that (1)
$0_{i}.\mathsf{process}=1_{i}.\mathsf{process}=p_{i}$, (2)
$0_{i}.\mathsf{proposal}=0$, and (3) $1_{i}.\mathsf{proposal}=1$. Each process
$p_{i}$ starts round $1$ in state $0_{i}$ or state $1_{i}$.

####  A.1.3. State-Transition Function.

Algorithm $\mathcal{A}$ maps (1) the state of a process at the start of a
round, and (2) messages the process received in the round into (a) a new state
of the process at the start of the next round, and (b) messages the process
sends in the next round. Formally, given (1) a state $s\in\mathcal{S}$, and
(2) a set of messages $M^{R}\subsetneq\mathcal{M}$ such that, for every
message $m\in M^{R}$, $m.\mathsf{receiver}=s.\mathsf{process}$ and
$m.\mathsf{round}=s.\mathsf{round}$,
$\mathcal{A}(s,M^{R})=(s^{\prime},M^{S})$, where

  * •

$s^{\prime}\in\mathcal{S}$ is a state such that:

    * –

$s^{\prime}.\mathsf{process}=s.\mathsf{process}$,

    * –

$s^{\prime}.\mathsf{round}=s.\mathsf{round}+1$,

    * –

$s^{\prime}.\mathsf{proposal}=s.\mathsf{proposal}$,

    * –

if $s.\mathsf{decision}\neq\bot$,
$s^{\prime}.\mathsf{decision}=s.\mathsf{decision}$; and

  * •

$M^{S}\subsetneq\mathcal{M}$ is a set of messages such that, for every message
$m\in M^{S}$, the following holds:

    * –

$m.\mathsf{sender}=s^{\prime}.\mathsf{process}=s.\mathsf{process}$,

    * –

$m.\mathsf{round}=s^{\prime}.\mathsf{round}=s.\mathsf{round}+1$,

    * –

$m.\mathsf{receiver}\neq m.\mathsf{sender}$,

    * –

there is no message $m^{\prime}\in M^{S}$ such that (1) $m^{\prime}\neq m$,
and (2) $m.\mathsf{receiver}=m^{\prime}.\mathsf{receiver}$.

The messages each process $p_{i}$ sends in the first round depend solely on
$p_{i}$’s initial state:

  * •

If $p_{i}$’s state at the start of the first round is $0_{i}$, then
$\mathcal{M}_{i}^{0}$ denotes the messages $p_{i}$ sends in the first round.
For every message $m\in\mathcal{M}_{i}^{0}$, the following holds: (1)
$m.\mathsf{sender}=p_{i}$, (2) $m.\mathsf{round}=1$, (3)
$m.\mathsf{receiver}\neq p_{i}$, and (4) there is no message
$m^{\prime}\in\mathcal{M}_{i}^{0}$ such that (a) $m^{\prime}\neq m$, and (b)
$m^{\prime}.\mathsf{receiver}=m.\mathsf{receiver}$.

  * •

If $p_{i}$’s state at the start of the first round is $1_{i}$, then
$\mathcal{M}_{i}^{1}$ denotes the messages $p_{i}$ sends in the first round.
For every message $m\in\mathcal{M}_{i}^{1}$, the following holds: (1)
$m.\mathsf{sender}=p_{i}$, (2) $m.\mathsf{round}=1$, (3)
$m.\mathsf{receiver}\neq p_{i}$, and (4) there is no message
$m^{\prime}\in\mathcal{M}_{i}^{1}$ such that (a) $m^{\prime}\neq m$, and (b)
$m^{\prime}.\mathsf{receiver}=m.\mathsf{receiver}$.

####  A.1.4. Fragments.

A tuple
$\mathcal{FR}=\Bigl{(}s,M^{S},M^{\mathit{SO}},M^{R},M^{\mathit{RO}}\Bigl{)}$,
where $s\in\mathcal{S}$ and
$M^{S},M^{\mathit{SO}},M^{R},M^{\mathit{RO}}\subsetneq\mathcal{M}$, is a _$k$
-round fragment_, for some $k\in\mathbb{N}\cup\\{+\infty\\}$, of a process
$p_{i}$ if and only if:

  1. (1)

$s.\mathsf{process}=p_{i}$; and

  2. (2)

$s.\mathsf{round}=k$; and

  3. (3)

for every message $m\in M^{S}\cup M^{\mathit{SO}}\cup M^{R}\cup
M^{\mathit{RO}}$, $m.\mathsf{round}=k$; and

  4. (4)

$M^{S}\cap M^{\mathit{SO}}=\emptyset$; and

  5. (5)

$M^{R}\cap M^{\mathit{RO}}=\emptyset$; and

  6. (6)

for every message $m\in M^{S}\cup M^{\mathit{SO}}$, $m.\mathsf{sender}=p_{i}$;
and

  7. (7)

for every message $m\in M^{R}\cup M^{\mathit{RO}}$,
$m.\mathsf{receiver}=p_{i}$; and

  8. (8)

there is no message $m\in M^{S}\cup M^{\mathit{SO}}\cup M^{R}\cup
M^{\mathit{RO}}$ such that $m.\mathsf{sender}=m.\mathsf{receiver}=p_{i}$; and

  9. (9)

there are no two messages $m,m^{\prime}\in M^{S}\cup M^{\mathit{SO}}$ such
that $m.\mathsf{receiver}=m^{\prime}.\mathsf{receiver}$; and

  10. (10)

there are no two messages $m,m^{\prime}\in M^{R}\cup M^{\mathit{RO}}$ such
that $m.\mathsf{sender}=m^{\prime}.\mathsf{sender}$.

Intuitively, a $k$-round fragment of a process describes what happens at a
process from the perspective of an omniscient external observer in the $k$-th
round.

##### Intermediate results on fragments.

We now present a few simple results.

###### Lemma 0.

Consider any $k$-round ($k\in\mathbb{N}\cup\\{+\infty\\}$) fragment
$\mathcal{FR}=\Bigl{(}s,M^{S},M^{\mathit{SO}},M^{R},M^{\mathit{RO}}\Bigl{)}$
of any process $p_{i}$, and any tuple
$\mathcal{FR}^{\prime}=\Bigl{(}s,M^{S},M^{\mathit{SO}},M^{R},X\subsetneq\mathcal{M}\Bigl{)}$
for which the following holds:

  1. (i)

for every message $m\in X$, $m.\mathsf{round}=k$; and

  2. (ii)

$M^{R}\cap X=\emptyset$; and

  3. (iii)

for every $m\in X$, $m.\mathsf{receiver}=p_{i}$; and

  4. (iv)

there is no message $m\in X$, $m.\mathsf{sender}=m.\mathsf{receiver}=p_{i}$;
and

  5. (v)

there are no two messages $m,m^{\prime}\in M^{R}\cup X$ such that
$m.\mathsf{sender}=m^{\prime}.\mathsf{sender}$.

Then, $\mathcal{FR}^{\prime}$ is a $k$-round fragment of $p_{i}$.

###### Proof.

To prove that $\mathcal{FR}^{\prime}$ is a $k$-round fragment of $p_{i}$, we
prove that all ten conditions hold for $\mathcal{FR}^{\prime}$. By the
statement of the lemma, $\mathcal{FR}$ is a $k$-round fragment of $p_{i}$.
Conditions (1), (2), (4), (6), and (9) hold for $\mathcal{FR}^{\prime}$ as the
first four elements of the tuple $\mathcal{FR}^{\prime}$ are identical to the
first four elements of $\mathcal{FR}$. Conditions (3), (5), (7), (8), and (10)
hold due to conditions (i), (ii), (iii), (iv), and (v), respectively. ∎

###### Lemma 0.

Consider any $k$-round ($k\in\mathbb{N}\cup\\{+\infty\\}$) fragment
$\mathcal{FR}=\Bigl{(}s,M^{S},M^{\mathit{SO}},M^{R},M^{\mathit{RO}}\Bigl{)}$
of any process $p_{i}$, and any tuple
$\mathcal{FR}^{\prime}=\Bigl{(}s,X\subsetneq\mathcal{M},Y\subsetneq\mathcal{M},M^{R},M^{\mathit{RO}}\Bigl{)}$
for which the following holds:

  1. (i)

for every message $m\in X\cup Y$, $m.\mathsf{round}=k$; and

  2. (ii)

$X\cap Y=\emptyset$; and

  3. (iii)

for every message $m\in X\cup Y$, $m.\mathsf{sender}=p_{i}$; and

  4. (iv)

there is no message $m\in X\cup Y$,
$m.\mathsf{sender}=m.\mathsf{receiver}=p_{i}$; and

  5. (v)

there are no two messages $m,m^{\prime}\in X\cup Y$ such that
$m.\mathsf{receiver}=m^{\prime}.\mathsf{receiver}$.

Then, $\mathcal{FR}^{\prime}$ is a $k$-round fragment of $p_{i}$.

###### Proof.

Due to the statement of the lemma, $\mathcal{FR}$ is a $k$-round fragment of
$p_{i}$. Therefore, conditions (1), (2), (5), (7), and (10) hold directly for
$\mathcal{FR}^{\prime}$ as the first, fourth, and fifth elements of
$\mathcal{FR}^{\prime}$ are identical to the first, fourth and fifth elements
of $\mathcal{FR}$. Conditions (3), (4), (6), (8), and (9) hold due to
conditions (i), (ii), (iii), (iv), and (v), respectively. ∎

####  A.1.5. Behaviors.

In this subsection, we define behaviors of processes. A tuple
$\mathcal{B}=\Bigl{\langle}\mathcal{FR}^{1}=\Bigl{(}s^{1},M^{S(1)},M^{\mathit{SO}(1)},M^{\mathit{R}(1)},M^{\mathit{RO}(1)}\Bigl{)},...,\mathcal{FR}^{k}=\Bigl{(}s^{k},M^{S(k)},M^{\mathit{SO}(k)},M^{\mathit{R}(k)},M^{\mathit{RO}(k)}\Bigl{)}\Bigl{\rangle}$
is a _$k$ -round behavior_, for some $k\in\mathbb{N}\cup\\{+\infty\\}$, of a
process $p_{i}$ if and only if:

  1. (1)

for every $j\in[1,k]$, $\mathcal{FR}^{j}$ is a $j$-round fragment of $p_{i}$;
and

  2. (2)

$s^{1}=0_{i}$ or $s^{1}=1_{i}$; and

  3. (3)

if $s^{1}=0_{i}$, then $M^{S(1)}\cup M^{\mathit{SO}(1)}=\mathcal{M}_{i}^{0}$;
and

  4. (4)

if $s^{1}=1_{i}$, then $M^{S(1)}\cup M^{\mathit{SO}(1)}=\mathcal{M}_{i}^{1}$;
and

  5. (5)

$s^{1}.\mathsf{proposal}=s^{2}.\mathsf{proposal}=...=s^{k}.\mathsf{proposal}$;
and

  6. (6)

if there exists $j\in[1,k]$ such that $s^{j}.\mathsf{decision}\neq\bot$, then
there exists $j^{*}\in[1,j]$ such that (1) for every
$j^{\prime}\in[1,j^{*}-1]$, $s^{j^{\prime}}.\mathsf{decision}=\bot$, and (2)
$s^{j^{*}}.\mathsf{decision}=s^{j^{*}+1}.\mathsf{decision}=...=s^{k}.\mathsf{decision}$;
and

  7. (7)

for every $j\in[1,k-1]$, $\mathcal{A}(s^{j},M^{R(j)})=(s^{j+1},M^{S(j+1)}\cup
M^{\mathit{SO}(j+1)})$.

If $k=+\infty$, we say that $\mathcal{B}$ is an _infinite behavior_ of
$p_{i}$. Intuitively, a process’s behavior describes the states and sets of
sent and received messages (including those that are omitted) of that process.

##### Intermediate results on behaviors.

We first introduce a few functions concerned with behaviors (see the
_Functions_ table) before proving two intermediate results (lemmas 3 and 4).

Functions defined on the $k$-round behavior $\mathcal{B}$ defined above

1:function $\mathsf{state}(\mathcal{B},j\in[1,k])$:

2: return $s^{j}$ $\triangleright$ returns the state at the start of round $j$

3:function $\mathsf{sent}(\mathcal{B},j\in[1,k])$:

4: return $M^{S(j)}$ $\triangleright$ returns the messages (successfully) sent
in round $j$

5:function $\mathsf{send\\_omitted}(\mathcal{B},j\in[1,k])$:

6: return $M^{\mathit{SO}(j)}$ $\triangleright$ returns the messages send-
omitted in round $j$

7:function $\mathsf{received}(\mathcal{B},j\in[1,k])$:

8: return $M^{R(j)}$ $\triangleright$ returns the messages received in round
$j$

9:function $\mathsf{receive\\_omitted}(\mathcal{B},j\in[1,k])$:

10: return $M^{\mathit{RO}(j)}$ $\triangleright$ returns the messages receive-
omitted in round $j$

11:function $\mathsf{all\\_sent}(\mathcal{B})$:

12: return $\bigcup\limits_{j\in[1,k]}M^{\mathit{S}(j)}$ $\triangleright$
returns all (successfully) sent messages

13:function $\mathsf{all\\_send\\_omitted}(\mathcal{B})$:

14: return $\bigcup\limits_{j\in[1,k]}M^{\mathit{SO}(j)}$ $\triangleright$
returns all send-omitted messages

15:function $\mathsf{all\\_receive\\_omitted}(\mathcal{B})$:

16: return $\bigcup\limits_{j\in[1,k]}M^{\mathit{RO}(j)}$ $\triangleright$
returns all receive-omitted messages

###### Lemma 0.

Consider any $k$-round ($k\in\mathbb{N}\cup\\{+\infty\\}$) behavior
$\mathcal{B}=\Bigl{\langle}\mathcal{F}^{1},\cdots,\mathcal{F}^{k}\Bigl{\rangle}$
of any process $p_{i}$, and any tuple
$\mathcal{B}^{\prime}=\Bigl{\langle}\mathcal{FR}^{1},\cdots,\mathcal{FR}^{k}\Bigl{\rangle}$.
For every $j\in[1,k]$,
$\mathcal{F}^{j}=\Bigl{(}s^{j},M^{S(j)},M^{\mathit{SO}(j)},M^{\mathit{R}(j)},M^{\mathit{RO}(j)}\Bigl{)}$.
Moreover, for every $j\in[1,k]$,
$\mathcal{FR}^{j}=\Bigl{(}s^{j},M^{S(j)},M^{\mathit{SO}(j)},M^{R(j)},X^{j}\subsetneq\mathcal{M}\Bigl{)}$
and the following holds:

  1. (i)

for every message $m\in X^{j}$, $m.\mathsf{round}=j$; and

  2. (ii)

$M^{R(j)}\cap X^{j}=\emptyset$; and

  3. (iii)

for every message $m\in X^{j}$, $m.\mathsf{receiver}=p_{i}$; and

  4. (iv)

there is no message $m\in X^{j}$,
$m.\mathsf{sender}=m.\mathsf{receiver}=p_{i}$; and

  5. (v)

there are no two messages $m,m^{\prime}\in M^{R(j)}\cup X^{j}$ such that
$m.\mathsf{sender}=m^{\prime}.\mathsf{sender}$.

Then, $\mathcal{B}^{\prime}$ is a $k$-round behavior of $p_{i}$.

###### Proof.

Since $\mathcal{B}$ is a behavior of $p_{i}$,
$\mathcal{F}^{1},\cdots,\mathcal{F}^{k}$ are fragments of $p_{i}$. Thus, for
every $j\in[1,k]$, $\mathcal{FR}^{j}$ is a $j$-round fragment of $p_{i}$ due
to conditions (i) to (v) and Lemma 1, which implies that condition (1) holds
for $\mathcal{B}^{\prime}$. Conditions (3) and (4) hold for
$\mathcal{B}^{\prime}$ as, for every $j\in[1,k]$, the second and third
elements of $\mathcal{FR}^{j}$ are identical to the second and third elements
of $\mathcal{F}^{j}$. Similarly, conditions (2), (5) and (6) hold for
$\mathcal{B}^{\prime}$ as, for every $j\in[1,k]$, the first element of
$\mathcal{FR}^{j}$ is identical to the state from $\mathcal{F}^{j}$. Finally,
condition (7) holds for $\mathcal{B}^{\prime}$: first, for every $j\in[1,k]$,
the first four elements of $\mathcal{FR}^{j}$ are identical to the first four
elements of $\mathcal{F}^{j}$; second, condition (7) holds for $\mathcal{B}$.
∎

###### Lemma 0.

Consider any $k$-round ($k\in\mathbb{N}\cup\\{+\infty\\}$) behavior
$\mathcal{B}=\Bigl{\langle}\mathcal{F}^{1},\cdots,\mathcal{F}^{k}\Bigl{\rangle}$
of any process $p_{i}$ and a tuple
$\mathcal{B}^{\prime}=\Bigl{\langle}\mathcal{FR}^{1},\cdots,\mathcal{FR}^{k}\Bigl{\rangle}$.
For every $j\in[1,k]$,
$\mathcal{F}^{j}=\Bigl{(}s^{j},M^{S(j)},M^{\mathit{SO}(j)},M^{\mathit{R}(j)},M^{\mathit{RO}(j)}\Bigl{)}$.
Moreover, for every $j\in[1,k]$,
$\mathcal{FR}^{j}=\Bigl{(}s^{j},X^{j}\subsetneq\mathcal{M},Y^{j}\subsetneq\mathcal{M},M^{\mathit{R}(j)},M^{\mathit{RO}(j)}\Bigl{)}$
such that (1) $X^{j}\cup Y^{j}=M^{S(j)}\cup M^{\mathit{SO}(j)}$, and (2)
$X^{j}\cap Y^{j}=\emptyset$. Then, $\mathcal{B}^{\prime}$ is a $k$-round
behavior of $p_{i}$.

###### Proof.

Since $\mathcal{B}$ is a behavior of $p_{i}$,
$\mathcal{F}^{1},\cdots,\mathcal{F}^{k}$ are fragments of $p_{i}$. Thus, for
every $j\in[1,k]$, $\mathcal{FR}^{j}$ is a $j$-round fragment of $p_{i}$ due
to Lemma 2, which implies that condition (1) holds for $\mathcal{B}^{\prime}$.
Conditions (3) and (4) hold for $\mathcal{B}^{\prime}$ as (1) both conditions
hold for $\mathcal{B}$, and (2) for every $j\in[1,k]$, $X^{j}\cup
Y^{j}=M^{S(j)}\cup M^{\mathit{SO}(j)}$. Similarly, conditions (2), (5) and (6)
hold for $\mathcal{B}^{\prime}$ as, for every $j\in[1,k]$, the first element
of $\mathcal{FR}^{j}$ is identical to the state from $\mathcal{F}^{j}$.
Finally, condition (7) holds for $\mathcal{B}^{\prime}$: first, for every
$j\in[1,k]$, $X^{j}\cup Y^{j}=M^{S(j)}\cup M^{\mathit{SO}(j)}$ and the first
and the fourth elements of $\mathcal{FR}^{j}$ are identical to the first and
the fourth elements of $\mathcal{F}^{j}$; second, condition (7) holds for
$\mathcal{B}$. ∎

####  A.1.6. Executions.

A _$k$ -round execution_ $\mathcal{E}$, for some
$k\in\mathbb{N}\cup\\{+\infty\\}$, is a tuple
$\mathcal{E}=[\mathcal{F}\subsetneq\Pi,\mathcal{B}_{1},...,\mathcal{B}_{n}]$
such that the following guarantees hold:

  * •

_Faulty processes:_ $\mathcal{F}$ is a set of $|\mathcal{F}|\leq t$ processes.

  * •

_Composition:_ For every $j\in[1,n]$, $\mathcal{B}_{j}$ is a $k$-round
behavior of process $p_{j}$.

  * •

_Send-validity:_ If there exists a message $m$, where
$p_{s}=m.\mathsf{sender}$, $p_{r}=m.\mathsf{receiver}$ and
$j=m.\mathsf{round}$, such that $m\in\mathsf{sent}(\mathcal{B}_{s},j)$, then
the following holds: $m\in\mathsf{received}(\mathcal{B}_{r},j)$ or
$m\in\mathsf{receive\\_omitted}(\mathcal{B}_{r},j)$. That is, if a message is
(successfully) sent, the message is either received or receive-omitted in the
same round.

  * •

_Receive-validity:_ If there exists a message $m$, where
$p_{s}=m.\mathsf{sender}$, $p_{r}=m.\mathsf{receiver}$ and
$j=m.\mathsf{round}$, such that
$m\in\mathsf{received}(\mathcal{B}_{r},j)\cup\mathsf{receive\\_omitted}(\mathcal{B}_{r},j)$,
then $m\in\mathsf{sent}(\mathcal{B}_{s},j)$. That is, if a message is received
or receive-omitted, the message is (successfully) sent in the same round.

  * •

_Omission-validity:_ If there exists a process $p_{i}$ and $j\in[1,k]$ such
that (1) $\mathsf{send\\_omitted}(\mathcal{B}_{i},j)\neq\emptyset$, or (2)
$\mathsf{receive\\_omitted}(\mathcal{B}_{i},j)\neq\emptyset$, then
$p_{i}\in\mathcal{F}$. That is, if a process commits an omission fault, the
process belongs to $\mathcal{F}$.

If $k=+\infty$, we say that $\mathcal{E}$ is an _infinite execution_.

###  A.2. Preliminary Lemmas

We start by defining the $\mathsf{swap\\_omission}$ procedure (Algorithm 4).

Algorithm 4 Procedure $\mathsf{swap\\_omission}$

1:procedure $\mathsf{swap\\_omission}(\mathsf{Execution}\text{
}\mathcal{E}=[\mathcal{F},\mathcal{B}_{1},...,\mathcal{B}_{n}],p_{i}\in\Pi)$:

2: let $M\leftarrow\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{i})$
$\triangleright$ $M$ contains all messages which are receive-omitted by
$p_{i}$

3: let $\mathcal{F}^{\prime}\leftarrow\emptyset$ $\triangleright$ new set of
faulty processes

4: for each $p_{z}\in\Pi$:

5: let
$\mathcal{B}_{z}=\langle\mathcal{FR}_{z}^{1},...,\mathcal{FR}_{z}^{k}\rangle$,
for some $k\in\mathbb{N}\cup\\{+\infty\\}$

6: for each $j\in[1,k]$:

7: let $\mathit{sent}_{z}\leftarrow\\{m\in\mathcal{M}\,|\,m\in M\land
m.\mathsf{round}=j\land m.\mathsf{sender}=p_{z}\\}$ $\triangleright$ messages
from $M$ sent by $p_{z}$

8: let
$\mathcal{FR}_{z}^{j}=(s^{j},M^{S(j)},M^{\mathit{SO}(j)},M^{R(j)},M^{\mathit{RO}(j)})$
$\triangleright$ old fragment

9: let
$\mathcal{FR}^{j}\leftarrow(s^{j},M^{S(j)}\setminus\mathit{sent}_{z},M^{\mathit{SO}(j)}\cup\mathit{sent}_{z},M^{R(j)},M^{\mathit{RO}(j)}\setminus{M})$
$\triangleright$ new fragment

10: if
$(M^{\mathit{SO}(j)}\cup\mathit{sent}_{z})\cup(M^{\mathit{RO}(j)}\setminus{M})\neq\emptyset$:
$\triangleright$ check for an omission fault

11: $\mathcal{F}^{\prime}\leftarrow\mathcal{F}^{\prime}\cup\\{p_{z}\\}$
$\triangleright$ $p_{z}$ is faulty

12: let
$\mathcal{B}_{z}^{\prime}\leftarrow\langle\mathcal{FR}^{1},...,\mathcal{FR}^{k}\rangle$

13: return
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$

Intuitively, $\mathsf{swap\\_omission}(\mathcal{E},p_{i})$, for some execution
$\mathcal{E}$ and process $p_{i}$, constructs an execution
$\mathcal{E}^{\prime}$ in which receive-omission faults of process $p_{i}$ are
“swapped” for send-omission faults of other processes. The following lemma
proves that, if some preconditions are true, $\mathcal{E}^{\prime}$ is indeed
an execution and it satisfies certain properties.

###### Lemma 0.

Let $\mathcal{E}=[\mathcal{F},\mathcal{B}_{1},...,\mathcal{B}_{n}]$ be any
$k$-round ($k\in\mathbb{N}\cup\\{+\infty\\}$) execution. Moreover, let
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]\leftarrow\mathsf{swap\\_omission}(\mathcal{E},p_{i})$,
for some process $p_{i}$. Let the following hold:

  * •

$|\mathcal{F}^{\prime}|\leq t$; and

  * •

$\mathsf{all\\_send\\_omitted}(\mathcal{B}_{i})=\emptyset$; and

  * •

there exists a process $p_{h}\in\Pi\setminus{\mathcal{F}}$ such that
$p_{h}\neq p_{i}$ and
$\mathsf{all\\_sent}(\mathcal{B}_{h})\cap\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{i})=\emptyset$.

Then, (1)
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$
is a $k$-round execution, (2) $\mathcal{E}$ and
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$
are indistinguishable to every process $p_{z}\in\Pi$, (3)
$p_{i}\notin\mathcal{F}^{\prime}$, and (4) $p_{h}\notin\mathcal{F}^{\prime}$.

###### Proof.

To prove the lemma, we first prove that all guarantees that an execution needs
to satisfy (see § A.1.6) are indeed satisfied for the tuple
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$.

  * •

_Faulty processes:_ Follows from the precondition of the lemma.

  * •

_Composition:_ As $\mathcal{E}$ is a $k$-round execution, $\mathcal{B}_{i}$ is
a $k$-round behavior of every process $p_{i}$. Therefore, for every process
$p_{i}$, $\mathcal{B}^{\prime}_{i}$ is a $k$-round behavior of $p_{i}$ due to
lemmas 3 and 4.

  * •

_Send-validity:_ Consider any message $m$, where $p_{s}=m.\mathsf{sender}$,
$p_{r}=m.\mathsf{receiver}$ and $j=m.\mathsf{round}$, such that $m$ is sent in
$\mathcal{B}^{\prime}_{s}$. Note that $m\in\mathsf{sent}(\mathcal{B}_{s},j)$
(as no new sent messages are added to $\mathcal{B}_{s}^{\prime}$ at line 9).
Therefore, $m\in\mathsf{sent}(\mathcal{B}_{s}^{\prime},j)$ and
$m\in\mathsf{received}(\mathcal{B}_{r},j)\cup\mathsf{receive\\_omitted}(\mathcal{B}_{r},j)$
(due to the send-validity property of $\mathcal{E}$). As $m$ is sent in
$\mathcal{B}^{\prime}_{s}$ (i.e., $m\in M^{S(j)}$ at process $p_{s}$; line 9),
$m\notin M$. Thus, $m$ is not excluded from $M^{\mathit{RO}(j)}$ at process
$p_{r}$ (line 9), which implies $m\in
M^{R(j)}\cup(M^{\mathit{RO}(j)}\setminus{M})$ at process $p_{r}$. Thus, send-
validity holds.

  * •

_Receive-validity:_ Consider any message $m$, where $p_{s}=m.\mathsf{sender}$,
$p_{r}=m.\mathsf{receiver}$ and $j=m.\mathsf{round}$, such that $m$ is
received or receive-omitted in $\mathcal{B}_{r}^{\prime}$. As $m$ is received
or receive-omitted in $\mathcal{B}_{r}^{\prime}$, $m$ is received or receive-
omitted in $\mathcal{B}_{r}$ (as no new received or receive-omitted messages
are added to $\mathcal{B}_{r}^{\prime}$ at line 9). Moreover,
$m\in\mathsf{received}(\mathcal{B}_{r},j)\cup\mathsf{receive\\_omitted}(\mathcal{B}_{r},j)$
(as $\mathcal{B}_{r}$ is $k$-round behavior of $p_{r}$), which then implies
that $m\in\mathsf{sent}(\mathcal{B}_{s},j)$ (as $\mathcal{E}$ satisfies
receive-validity). Furthermore, $m\notin M$; otherwise, $m$ would not be
received nor receive-omitted in $\mathcal{B}_{r}^{\prime}$. Therefore, $m$ is
not excluded from $M^{S(j)}$ at process $p_{s}$ (line 9), which proves that
receive-validity is satisfied.

  * •

_Omission-validity:_ Follows directly from the check at line 10.

As all guarantees are satisfied,
$[\mathcal{F}^{\prime},\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$
is a $k$-round execution, which proves the first statement of the lemma.

Second, we prove the indistinguishability statement for every process
$p_{z}\in\Pi$. The $\mathsf{swap\\_omission}$ procedure (Algorithm 4) ensures
that
$\mathsf{received}(\mathcal{B}_{z}^{\prime},j)=\mathsf{received}(\mathcal{B}_{z},j)$
(line 9), for every round $j\in[1,k]$. Moreover, for every round $j\in[1,k]$,
$\mathsf{state}(\mathcal{B}_{z}^{\prime},j)=\mathsf{state}(\mathcal{B}_{z},j)$
and
$\mathsf{sent}(\mathcal{B}_{z}^{\prime},j)\cup\mathsf{send\\_omitted}(\mathcal{B}_{z}^{\prime},j)=\mathsf{sent}(\mathcal{B}_{z},j)\cup\mathsf{send\\_omitted}(\mathcal{B}_{z},j)$
(line 9). Therefore, the second statement of the lemma holds.

Third, we prove that $p_{i}\notin\mathcal{F}^{\prime}$. As no process sends
messages to itself, $\mathit{sent}_{i}=\emptyset$ (line 7) in every round
$j\in[1,k]$. Hence,
$\mathsf{all\\_send\\_omitted}(\mathcal{B}^{\prime}_{i})=\emptyset$ (line 9).
Moreover,
$M=\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{i})=\bigcup\limits_{j\in[1,k]}M^{\mathit{RO}(j)}$
(line 2). Therefore,
$\mathsf{all\\_receive\\_omitted}(\mathcal{B}^{\prime}_{i})=\emptyset$, which
implies that the third statement of the lemma holds.

Finally, we prove that $p_{h}\notin\mathcal{F}^{\prime}$. As
$p_{h}\notin\mathcal{F}$,
$\mathsf{all\\_send\\_omitted}(\mathcal{B}_{h})=\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{h})=\emptyset$.
As $\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{h})=\emptyset$,
$\mathsf{all\\_receive\\_omitted}(\mathcal{B}_{h}^{\prime})=\emptyset$ (line
9). Moreover, $\mathit{sent}_{h}=\emptyset$ (line 7) in every round
$j\in[1,k]$. Therefore,
$\mathsf{all\\_send\\_omitted}(\mathcal{B}_{h}^{\prime})=\emptyset$ (line 9).
Hence, $p_{h}\notin\mathcal{F}^{\prime}$, which concludes the proof of the
lemma. ∎

Algorithm 5 defines the $\mathsf{merge}$ procedure which constructs a new
execution from two mergeable ones; recall that mergeable executions are
defined by Definition 5. The following lemma proves that the result of the
$\mathsf{merge}$ procedure (Algorithm 5) is an execution that is
indistinguishable from the original one and satisfies some important
properties.

Algorithm 5 Procedure $\mathsf{merge}$

1:procedure $\mathsf{merge}(\mathsf{Execution}\text{
}\mathcal{E}_{0}^{B(k_{1})}=[B,\mathcal{B}_{1},...,\mathcal{B}_{n}],\mathsf{Execution}\text{
}\mathcal{E}_{b}^{C(k_{2})}=[C,\mathcal{B}_{1}^{\prime},...,\mathcal{B}^{\prime}_{n}])$:

2: assert ($\mathcal{E}_{0}^{B(k_{1})}$ and $\mathcal{E}_{b}^{C(k_{2})}$ are
mergeable executions)

3: let $\mathit{sent}\leftarrow\bigcup\limits_{p_{i}\in A\cup
B}\mathcal{M}_{i}^{0}\cup\bigcup\limits_{p_{i}\in C}\mathcal{M}_{i}^{b}$
$\triangleright$ messages sent in the first round

4: let $s_{i}\leftarrow 0_{i}$, for every process $p_{i}\in A\cup B$
$\triangleright$ the initial state of processes in $A\cup B$

5: let $\mathit{sent}_{i}\leftarrow\mathcal{M}_{i}^{0}$, for every process
$p_{i}\in A\cup B$ $\triangleright$ the initial messages sent by processes in
$A\cup B$

6: let $s_{i}\leftarrow b_{i}$, for every process $p_{i}\in C$
$\triangleright$ the initial state of processes in $C$

7: let $\mathit{sent}_{i}\leftarrow\mathcal{M}_{i}^{b}$, for every process
$p_{i}\in C$ $\triangleright$ the initial messages sent by processes in $C$

8: for each $j\geq 1$:

9: for each $p_{i}\in\Pi$:

10: let $\mathit{to}_{i}\leftarrow\\{m\,|\,m\in\mathit{sent}\land
m.\mathsf{receiver}=p_{i}\\}$ $\triangleright$ messages sent in the round $j$
to $p_{i}$

11: let $\mathit{received}_{i}\leftarrow\emptyset$

12: if $p_{i}\in A$:

13: let
$\mathcal{FR}_{i}^{j}=(s_{i},\mathit{sent}_{i},\emptyset,\mathit{to}_{i},\emptyset)$

14: $\mathit{received}_{i}\leftarrow\mathit{to}_{i}$

15: else:

16: if $p_{i}\in B$:
$\mathit{received}_{i}\leftarrow\mathsf{received}(\mathcal{B}_{i},j)$
$\triangleright$ receive messages from $\mathcal{B}_{i}$

17: else:
$\mathit{received}_{i}\leftarrow\mathsf{received}(\mathcal{B}_{i}^{\prime},j)$
$\triangleright$ receive messages from $\mathcal{B}^{\prime}_{i}$

18: let
$\mathcal{FR}_{i}^{j}=(s_{i},\mathit{sent}_{i},\emptyset,\mathit{received}_{i},\mathit{to}_{i}\setminus{\mathit{received}_{i}})$

19:
$(s_{i},\mathit{sent}_{i})\leftarrow\mathcal{A}(s_{i},\mathit{received}_{i})$
$\triangleright$ compute new state and newly sent messages

20: $\mathit{sent}\leftarrow\bigcup\limits_{p_{i}\in\Pi}\mathit{sent}_{i}$
$\triangleright$ update sent messages

21: for each $p_{i}\in\Pi$:

22: let
$\mathcal{B}_{i}^{*}=\langle\mathcal{FR}_{i}^{1},\mathcal{FR}_{i}^{2},...\rangle$

23: return $[B\cup C,\mathcal{B}_{1}^{*},...,\mathcal{B}_{n}^{*}]$

###### Lemma 0.

Let executions $\mathcal{E}_{0}^{B(k_{1})}$ ($k_{1}\in\mathbb{N}$) and
$\mathcal{E}_{b}^{C(k_{2})}$ ($b\in\\{0,1\\}$, $k_{2}\in\mathbb{N}$) be
mergeable. Then, (1)
$\mathcal{E}^{*}=\mathsf{merge}(\mathcal{E}_{0}^{B(k_{1})},\mathcal{E}_{b}^{C(k_{2})})$
is an infinite execution, (2) $\mathcal{E}^{*}$ is indistinguishable from
$\mathcal{E}_{0}^{B(k_{1})}$ (resp., $\mathcal{E}_{b}^{C(k_{2})}$) to every
process $p_{B}\in B$ (resp., $p_{C}\in C$), and (3) group $B$ (resp., $C$) is
isolated from round $k_{1}$ (resp., $k_{2}$) in $\mathcal{E}^{*}$.

###### Proof.

Let $\mathcal{E}^{*}=[B\cup C,\mathcal{B}_{1}^{*},...,\mathcal{B}_{n}^{*}]$.
Let $\mathcal{E}_{0}^{B(k_{1})}=[B,\mathcal{B}_{1},...,\mathcal{B}_{n}]$ and
$\mathcal{E}_{b}^{C(k_{2})}=[C,\mathcal{B}_{1}^{\prime},...,\mathcal{B}_{n}^{\prime}]$.
To prove the lemma, we first prove that all guarantees from § A.1.6 are
satisfied by $\mathcal{E}^{*}$:

  * •

_Faulty processes:_ As $\mathcal{F}^{*}=B\cup C$,
$|\mathcal{F}^{*}|=\frac{t}{4}+\frac{t}{4}\leq t$.

  * •

_Composition:_ For each process $p_{i}\in\Pi$, we construct
$\mathcal{B}_{i}^{*}$ by following the valid transitions of the algorithm
$\mathcal{A}$ (line 19). Thus, for each process $p_{i}\in\Pi$,
$\mathcal{B}_{i}^{*}$ is an infinite behavior of $p_{i}$.

  * •

_Send-validity:_ Consider any message $m$, where $p_{s}=m.\mathsf{sender}$,
$p_{r}=m.\mathsf{receiver}$ and $j=m.\mathsf{round}$, such that $m$ is sent
$\mathcal{B}_{s}^{*}$. As $m.\mathsf{round}=j$, $m\in\mathit{sent}_{s}$ in the
$j$-th iteration of the for loop at line 8. Therefore, $m\in\mathit{to}_{r}$
(line 10) in the $j$-th iteration of the for loop at line 8. Hence,
$m\in\mathsf{received}(\mathcal{B}_{r}^{*},j)\cup\mathsf{receive\\_omitted}(\mathcal{B}_{r}^{*},j)$
(line 13 or line 18).

  * •