# On the complexity of fault-tolerant consensus

Dariusz R. Kowalski***Department of Computer Science, University of Liverpool,
Ashton Building, Ashton Street, Liverpool L69 3BX, UK. Email:
<EMAIL_ADDRESS>Jarosław Mirek11footnotemark: 1

###### Abstract

The paper studies the problem of reaching agreement in a distributed message-
passing system prone to crash failures. Crashes are generated by Constrained
adversaries - a Weakly-Adaptive adversary, who has to fix in advance the set
of $f$ crash-prone processes, or a $k$-Chain-Ordered adversary, who orders all
the processes into $k$ disjoint chains and has to follow this pattern when
crashing them. Apart from these constraints, both of them may crash processes
in an adaptive way at any time. While commonly used Strongly-Adaptive
adversaries model attacks and Non-Adaptive ones – pre-defined faults, the
constrained adversaries model more realistic scenarios when there are fault-
prone dependent processes, e.g., in hierarchical or dependable
software/hardware systems. We propose time-efficient consensus algorithms
against such adversaries and also show how to improve the message complexity
of proposed solutions. Finally, we show how to reach consensus against a
$k$-Ordered adversary, limited by an arbitrary partial order  with a maximal
anti-chain of length $k$. We complement our algorithmic results with (almost)
tight lower bounds, and extend the one for Weakly-Adaptive adversaries to hold
also for (syntactically) weaker Non-Adaptive adversaries. Together with the
consensus algorithm against Weakly-Adaptive adversaries (which automatically
translates to Non-Adaptive adversaries), these results extend the state-of-
the-art of the popular class of Non-Adaptive adversaries, in particular the
result of Chor, Meritt and Shmoys [21], and prove general separation between
Strongly-Adaptive and the constrained adversaries (including Non-Adaptive)
analyzed by Bar-Joseph and Ben-Or [12] and others.

##  1 Introduction

We study the problem of consensus in synchronous message passing distributed
systems. There are $n$ processes, out of which at most $f$ can crash. Each
process is initialized with a binary input value, and the goal is to agree on
one value from the input ones by all processes. Formally, the following three
properties need to be satisfied: agreement: no two processes decide on
different values; validity: only a value among the initial ones may be decided
upon; and termination: each process eventually decides, unless it crashes. In
case of randomized solutions, the specification of consensus needs to be
reformulated, which can be done in various ways (c.f., [9]). We consider a
classic reformulation in which validity and agreement are required to hold for
every execution, while termination needs to hold with probability $1$.

Efficiency of algorithms is measured twofold: by the the number of rounds
(time complexity) and by the total number of point-to-point messages sent
(message complexity) until all non-faulty processes decide. This work focuses
on _efficient randomized solutions_ – time and communication performance
metrics are understood in expected sense  (though we also provide some
analysis on work performance per process and time complexity formulas
depending on the desired probability of achieving it). Randomization has been
used in consensus algorithms for various kinds of failures specified by
adversarial models, see [4, 9]. Reason for considering randomization is to
overcome inherent limitations of deterministic solutions. Most surprising
benefits of randomization is the solvability of consensus in as small as
constant time [21, 24, 39]. Feasibility of achieving small upper bounds on
performance of algorithms solving consensus in a given distributed environment
depends on the power of adversaries inflicting failures.

On the other hand, Chlebus, Kowalski and Strojnowski [20] observed that
consensus cannot be solved _deterministically_ by an algorithm that is locally
scalable (i.e., slowly growing performance function per each process) with
respect to message complexity. They developed a globally scalable (i.e.,
slowly growing performance function per average process) deterministic
solution with respect to bit communication that can cope with any number $f<n$
of crash failures. Their solution is not explicit in the sense that it relies
on families of graphs with properties related to graph expansion that are
shown to exist by the probabilistic method.  In this work, we investigate
scalability of randomized algorithms against Constrained adversaries.

###  1.1 Previous and related work

Consensus is one of the fundamental problems in distributed computing, with a
rich history of research done in various settings and systems, c.f., [9].
Recently its popularity grew even further due to applications in emerging
technologies such as blockchains. Below we present only a small digest of
literature closely related with the setting considered in this work.

Consensus is solvable in synchronous systems with processes prone to crashing,
although time $f+1$ is required [25] and sufficient [27] in case of
deterministic solutions. Chor, Meritt and Shmoys [21] showed that
randomization allows to obtain a constant expected time algorithm against a
Non-Adaptive adversary, if the minority of processes may crash. Bar-Joseph and
Ben-Or [12] proved tight upper and lower bounds $\Theta(f/\sqrt{n\log n})$ on
the expected time of randomized consensus solutions for the Strongly-Adaptive
adversary that can decide to fail $f=\Omega(n)$ processes.

Message complexity of consensus was extensively studied before. Amdur, Weber
and Hadzilacos [2] showed that $\Omega(n)$ messages need to be sent by a
protocol solving consensus in an eventually synchronous environment in a
failure-free execution. Dolev and Reischuk [23] and Hadzilacos and Halpern
[31] proved the $\Omega(fn)$ lower bound on the message complexity of
deterministic consensus for Byzantine failures.

Chlebus and Kowalski [19] showed that consensus can be solved by a randomized
algorithm that is locally scalable with respect to both time and bit
communication complexities, when the number $f$ of failures is at most a
constant fraction of the number $n$ of processes and the adversary is Non-
Adaptive. A comparable performance is impossible to achieve by a deterministic
solution, as was observed in [20]. A deterministic algorithm solving consensus
in the synchronous setting that has processes sending a total of
${\mathcal{O}}(n\,{\mbox{polylog}}n)$ bits per message, meaning the algorithm
is globally scalable, and which can handle up to $n-1$ crashes, has been
developed in [20]. The globally scalable solution given in [20] is
deterministic but it is not explicit.

Gilbert and Kowalski [30] presented a randomized consensus algorithm that
achieves optimal communication complexity, using $\mathcal{O}(n)$ bits of
communication and terminates in $\mathcal{O}(\log n)$ time with high
probability, tolerating up to $f<n/2$ crash failures against a Non-Adaptive
adversary.

###  1.2 Our results

|  | Strongly-Adaptive |  Weakly-Adaptive and Non-Adaptive |  $k$-Chain-Ordered
---|---|---|---|---
randomized | upper bound |  $\mathcal{O}\left(\sqrt{\frac{n}{\log n}}\right)$ [12] |  $\mathcal{O}\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ * |  $\mathcal{O}\left(\sqrt{\frac{k}{\log k}}\log(n/k)\right)$ *
lower bound |  $\Omega\left(\sqrt{\frac{n}{\log n}}\right)$ [12] |  $\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ * |  $\Omega\left(\sqrt{\frac{k}{\log k}}\right)$ *
deterministic | upper bound |  $f+1$ [27]
lower bound |  $f+1$ [25]

Table 1: Time complexity of solutions for the consensus problem against
different adversaries. Formulas with * are presented in this paper.

We analyze the consensus problem against restricted adaptive adversaries. The
motivation is that a Strongly-Adaptive adversary, typically used for analysis
of randomized consensus algorithms, may not be very realistic; for instance,
in practice some processes could be set as fault-prone in advance, before the
execution of an algorithm, or may be dependent i.e., in hierarchical
hardware/software systems. In this context, a Strongly-Adaptive adversary
should be used to model attacks rather than realistic crash-prone systems. On
the other hand, a Non-Adaptive adversary who must fix all its actions before
the execution does not capture many aspects of fault-prone systems, e.g.,
attacks or reactive failures (occurring as an unplanned consequence of some
actions of the algorithm in the system). Therefore, analyzing the complexity
of consensus under such constraints gives a much better estimate on what may
happen in real executions and, as we demonstrate, leads to new interesting
theoretical findings about the performance of consensus algorithms.

Table 1 presents time complexities of solutions for the consensus problem
against different adversaries.  Results for the Strongly-Adaptive adversary
and for deterministic algorithms are known (see Section 1.1), while the other
ones are delivered in this work. We design and analyze a randomized algorithm
that reaches consensus in expected
$\mathcal{O}\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ rounds using
$\mathcal{O}\left(n^{2}+\sqrt{\frac{n^{5}}{(n-f)^{5}\log(n/(n-f))}}\right)$
point-to-point messages, in expectation, against any Weakly-Adaptive adversary
that may crash up to $f<n$ processes. This result is time optimal due to the
proved lower bound $\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ on
expected number of rounds.

The lower bound could be also generalized to hold against the (syntactically)
weaker Non-Adaptive adversaries, therefore all the results concerning Weakly-
Adaptive adversaries delivered in this paper hold for Non-Adaptive adversaries
as well. This extends the state-of-the-art of the study of Non-Adaptive
adversaries done in high volume of previous work, c.f., [21, 19, 30],
specifically, an $O(1)$ expected time algorithm of Chor et al. [21] only for a
constant (smaller than $1$) fraction of failures. Our lower bound is the first
non-constant formula depending on the number of crashes proved for this
adversary. In view of the lower bound $\Omega\left(\frac{f}{\sqrt{n\log
n}}\right)$ [12] on the expected number of rounds of any consensus algorithm
against a Strongly-Adaptive adversary crashing at most $f$ processes, _our
result shows separation of the two important classes of adversaries – Non-
Adaptive and Strongly-Adaptive – for one of the most fundamental problems in
distributed computing, which is consensus._

Furthermore we show an extension of the above mentioned algorithm
accomplishing consensus in slightly (polylogarithmically) longer number
$\mathcal{O}\left(\sqrt{\frac{n\log^{5}n}{(n-f)}}\right)$ of expected rounds
but using a substantially smaller number of
$\mathcal{O}\left(\left(\frac{n}{n-f}\right)^{3/2}\log^{7/2}n+n\log^{4}n\right)$
point-to-point messages in expectation. Time and message complexities of the
latter algorithm are only polylogarithmically far from the lower bounds for
almost all values of $f$. More specifically, only for $f=n-\Omega(\sqrt{n})$
the message complexity is away from the lower bound by some small polynomial.

We complement the results by showing how to modify the algorithm designed for
the Weakly-Adaptive adversary, to work against a $k$-Chain-Ordered adversary,
who has to arrange all processes into an order of $k$ chains, and then has to
preserve this order of crashes in the course of the execution. The algorithm
reaches consensus in $\mathcal{O}\left(\sqrt{\frac{k}{\log
k}}\log(n/k)\right)$ rounds in expectation.  Additionally, we show a lower
bound $\Omega\left(\sqrt{\frac{k}{\log k}}\right)$ for the problem against a
$k$-Ordered adversary. Finally, we show that this solution is capable of
running against an arbitrary partial order with a maximal anti-chain of size
$k$.  Similarly to results for the Weakly-Adaptive adversary, formulas
obtained for Ordered adversaries separate them from Strongly-Adaptive ones.

For algorithms proposed in this paper, we also analyze expected work per
process and give time complexity formulas depending on the desired probability
of achieving it.

Due to space limitations some parts of this work were deferred to the
Appendix.

##  2 Model

#### Synchronous distributed system.

We assume having a system of $n$ processes that communicate in the message
passing model. This means that processes form a complete graph where each edge
represents a communication link between two processes. If process $v$ wants to
send a message to process $w$, then this message is sent via link $(v,w)$. It
is worth noticing that links are symmetric, i.e., $(v,w)=(w,v)$. We assume
that messages are sent instantly.

Following the synchronous model by [12], we assume that computations are held
in a synchronous manner and hence time is divided into rounds consisting of
two phases:

– Phase A - generating local coins and local computation.

– Phase B - sending and receiving messages.

#### Adversarial scenarios.

Processes are prone to crash-failures that are a result of the adversary
activity. The adversary of our particular interest is an adaptive one - it can
make arbitrary decisions and see all local computations and local coins, as
well as messages intended to be sent by active processes. Therefore, it can
decide to crash processes during phase B. Additionally while deciding that a
certain process will crash, it can decide which subset of messages will reach
their recipients.

In the context of the adversaries in this paper we distinguish three types of
processes:

– Crash-prone - processes that can be crashed by the adversary.

– Fault-resistant - processes that are not in the subset of the Weakly-
Adaptive adversary and hence cannot be crashed.

– Non-faulty - processes that survived until the end of the algorithm.

• Strongly-Adaptive and Weakly-Adaptive adversaries. The only restriction for
the Strongly-Adaptive adversary is that it can fail up to $f$ processes, where
$0\leq f<n$.

The Weakly-Adaptive adversary is restricted by the fact that before the
algorithm execution it must choose $f$ processes that will be prone to
crashes, where $0\leq f<n$.

Observe that for deterministic algorithms the Weakly-Adaptive adversary is
consistent with the Strongly-Adaptive adversary, because it could simulate the
algorithm before its execution and decide on choosing the most convenient
subset of processes.

• $k$-Chain-Ordered and $k$-Ordered adversaries. The notion of a $k$-Chain-
Ordered adversary originates from partial order relations, hence appropriate
notions and definitions translate straightforwardly. The relation of our
particular interest while considering partially ordered adversaries is the
precedence relation. Precisely, if some process $v$ precedes process $w$ in
the partial order of the adversary, then we say that $v$ and $w$ are
comparable. This means that process $v$ must be crashed by the adversary
before process $w$. Consequently a subset of processes where every pair of
processes is comparable is called a chain. On the other hand a subset of
processes where no two different processes are comparable is called an anti-
chain.

It is convenient to think about the partial order of the adversary from a
Hasse diagram perspective. The notion of chains and anti-chains seems to be
intuitive when graphically presented, e.g., a chain is a pattern of
consecutive crashes that may occur while an anti-chain gives the adversary
freedom to crash in any order due to non-comparability of processes.

Formally, the $k$-Chain-Ordered adversary has to arrange all the processes
into a partial order consisting of $k$ disjoint chains of arbitrary length
that represent in what order these processes may be crashed.

By the thickness of a partial order $P$ we understand the maximal size of an
anti-chain in $P$. An adversary restricted by a wider class of partial orders
of thickness $k$ is called a $k$-Ordered adversary.

We refer to a wider class of adversaries in this paper, constrained by an
arbitrary partial order, as Ordered adversaries. What is more, adversaries
having additional limitations, apart from the possible number of crashes (i.e.
all described in this paper but the Strongly-Adaptive adversary), will be
called Constrained adversaries.

Note that Ordered adversaries are also restricted by the number of possible
crashes $f$ they may enforce. Additionally, throughout this paper we denote
$l_{j}$ as the length of chain $j$

• Non-Adaptive adversaries. The Non-Adaptive adversaries are characterised by
the fact that they must fix all their decisions prior to the execution of the
algorithm and then follow this pattern during the execution.

#### Consensus problem.

In the consensus problem $n$ processes, each having its input bit
$x_{i}\in\\{0,1\\}$, $i\in\\{1,\dots,n\\}$, have to agree on a common output
bit in the presence of the adversary, capable of crashing processes. We
require any consensus protocol to fulfill the following conditions:

– Agreement: all non-faulty processes decide the same value.

– Validity: if all processes have the same initial value $v$, then $v$ is the
only possible decision value.

– Termination: all non-faulty processes decide with probability $1$.

We follow typical assumption that the first two requirements must hold in
_any_ execution, while termination should be satisfied with probability $1$.

#### Complexity measures.

The main complexity measure used to benchmark the consensus problem is the
number of rounds by which all non-faulty processes decide on a common value.

On the other hand we discuss on the message complexity, understood as the
total number of messages sent in the system, until all non-faulty processes
decide on a common value.

The expected work per process is the expected number of non-idle computational
steps of a process accrued during the execution of an algorithm.

#### Algorithmic tools.

Throughout this paper we use black-box fashioned procedures that allow us to
clarify the presentation. We now briefly describe their properties and refer
to them in the algorithms’ analysis.

Leader-Consensus properties. Because we treat the Leader-Consensus procedure
as a black-box tool for reaching consensus on a small group of processes, we
need to define properties that we expect to be met by this protocol:

• Leader-Consensus reaches consensus on a group of no more than
$\frac{6n}{n-f}$ processes in time $T_{LC}(\frac{6n}{n-f})$ with probability
at least $\frac{9}{10}$, where $T_{LC}$ is time complexity of Leader-
Consensus.

• Leader-Consensus satisfies termination, validity and agreement.

A candidate solution to serve as Leader-Consensus is the Ben-Or and Bar-
Joseph’s SynRan algorithm from [12] and we refer the reader to the details
therein.

Propagate-Msg properties. We assume that procedure Propagate-Msg propagates
messages in $1$ round with $\mathcal{O}(n^{2})$ message complexity. This is
consistent with a scenario where full communication takes place and each
process sends a message to all the processes.

##  3 Weakly-Adaptive adversary

In this section we consider the fundamental result i.e. Algorithm A that
consists of two main components - a leader election procedure, and a reliable
consensus protocol. We combine them together in an appropriate way, in order
to reach consensus against a Weakly-Adaptive adversary.

###  3.1 Algorithm A

1initialize list LEADERS to an empty list;

2 $decided:=false$;

3 $value:=x_{v}$;

4 repeat

5 $\texttt{LEADERS}:=\textsc{Elect-Leader}$;

6

7 if  _LEADERS contains $v$_ then

8 Leader-Consensus(LEADERS) ;

9 if  _consensus achieved_ then

10 execute Propagate-Msg($value$) twice;

11 $decided=true$;

12 end if

13 else

14 wait for two rounds;

15 end if

16

17 end if

18 else

19 idle for $T_{LC}$ rounds;

20 if  _heard the same consensus value $CV_{w}$ twice from some process $w$_
then

21 $value:=CV_{w}$;

22 $decided=true$;

23

24 end if

25 if  _heard consensus value $CV_{w}$ once from some process $w$_ then

26 $value:=CV_{w}$;

27 end if

28

29 end if

30 clear list LEADERS;

31

32until  _$decided$_ ;

33

Algorithm 1 Algorithm A,  pseudocode for process $v$

1$\texttt{coin}:=\frac{1}{n-f}$;

2 initialize list LEADERS to an empty list;

3 toss a coin with the probability coin of heads to come up;

4 if  _heads came up in the previous step_ then

5 Propagate-Msg(“$v$”) to all other processes;

6 add $v$ to list LEADERS;

7 end if

8 fill in list LEADERS with elected leaders’ identifiers from received
messages;

9 return LEADERS;

Algorithm 2 Elect-Leader,  pseudocode for process $v$

Algorithm A has an iterative character and begins with a leader election
procedure in which we expect to elect $\mathcal{O}(\frac{n}{n-f})$ leaders
simultaneously. The leaders run Leader-Consensus procedure in which they are
expected to reach consensus within their own group. We call this a small
consensus. If they do so this fact is propagated to all the processes via
Propagate-Msg so that they know about reaching the small consensus and set
their consensus values accordingly. Communicating this fact, implies reaching
consensus by the whole system.

Let us follow Algorithm 1 from the perspective of some process $v$. At the
beginning of the protocol every process takes part in Elect-Leader procedure
and process $v$ tosses a coin with probability of success equal
$\frac{1}{n-f}$ and either is chosen to the group of leaders or not. If it is
successful, then it communicates this fact to all processes.

Process $v$ takes part in Leader-Consensus together with other leaders in
order to reach a small consensus and if the consensus value is fixed $v$ tries
to convince other processes to this value twice. This is because if some
process $w\neq v$ receives the consensus value in the latter round, then it
may be sure that other processes received this value from $v$ as well in the
former round (so in fact every process has the same consensus value fixed).
Process $v$ could not propagate its value for the second time if it was not
successful in propagating this value to every other process for the first time
- if just one process did not receive this value this would be consistent with
a crash of $v$.

If process $v$ was not chosen a leader then it listens the channel for an
appropriate amount of time and afterwards tries to learn the consensus value
twice. If it is unable to hear a double-consensus, then it idles for two
rounds for the purpose of synchronization. If consensus is not reached, then
the protocol starts again with electing another group of leaders.
Nevertheless, if process $v$ hears a consensus value once, it holds and
assigns it as a candidate consensus value. This guarantees continuity of the
protocol.

The idea standing behind Algorithm A is built on the fact that if just one
fault-resistant process is elected to the group of leaders then the adversary
is unable to crash it in the course of an execution. If additionally, the
small consensus protocol works well and all messages are propagated properly,
then consensus is achieved after a certain number of rounds.

###  3.2 Analysis of Algorithm A

We begin with a lemma stating that Elect-Leader is likely to elect
$\mathcal{O}(\frac{n}{n-f})$ leaders.

######  Lemma 1.

Let $L$ denote the number of leaders elected by Elect-Leader.
$L<6\frac{n}{n-f}$ at least with probability $\frac{9}{10}$.

######  Lemma 2.

Procedure Elect-Leader elects at least one sustainable, fault-resistant leader
with probability at least $\frac{6}{10}$.

######  Theorem 1.

The following hold for Algorithm A against the Weakly-Adaptive adversary:

a) Algorithm A reaches consensus in the expected number of rounds equal
$\mathcal{O}\left(T_{LC}\left(\frac{n}{n-f}\right)\right)$, satisfying
termination, agreement and validity.

b) Expected work per process of Algorithm A is
$\frac{1}{n-f}\;\mathcal{O}\left(T_{LC}\left(\frac{n}{n-f}\right)\right)$.

c) For some fixed $\epsilon>0$, Algorithm A reaches consensus in
$\mathcal{O}\left(\log\left(\frac{1}{\epsilon}\right)\;T_{LC}\left(\frac{n}{n-f}\right)\right)$
rounds and with work per process
$\frac{1}{n-f}\;\mathcal{O}\left(\log\left(\frac{1}{\epsilon}\right)\;T_{LC}\left(\frac{n}{n-f}\right)\right)$
with probability $1-\epsilon$.

###### Proof.

Let us describe three events and their corresponding probabilities:

\- (Lemma 1) Elect-Leader chooses less than $6\frac{n}{n-f}$ leaders, with
prob. bigger than $\frac{9}{10}$.

\- (Lemma 2) Elect-Leader chooses at least one fault-resistant leader, with
prob. greater than $\frac{6}{10}$.

\- (c.f. Section 2) Leader-Consensus finishes the small consensus within its
expected time $T_{LC}(\frac{6n}{n-f})$ , with probability $\frac{9}{10}$.

Let us define the conjunction of these events as the success of the algorithm
and denote it as $Z$. Since for any events $A$ and $B$ we have that
$\mathbb{P}(A\cap B)\geq\mathbb{P}(A)+\mathbb{P}(B)-1$, it is easy to observe
that $Z$ happens with probability at least $\frac{2}{5}$.

a) If $Z$ holds then Algorithm A reaches consensus in time
$\mathcal{O}(T_{LC}(\frac{6n}{n-f}))$. In what follows since $Z$ takes place
with probability $\frac{2}{5}$, then $\frac{5}{2}$ is the expected number of
iterations of Algorithm A until reaching consensus. Consequently Algorithm A
reaches consensus in the expected number of rounds equal
$\mathcal{O}(T_{LC}(\frac{6n}{n-f}))$.

Because the termination condition is satisfied by Leader-Consensus and the
expected number of iterations of Algorithm A is a constant, Algorithm A also
meets the termination condition.

The validity condition is also satisfied, by the validity of the Leader-
Consensus protocol and the fact that Algorithm A does not change values held
by processes.

In order to prove the agreement condition let us suppose to the contrary that
in some execution $\mathcal{A}$ there is process $v$ that reached consensus
with value $1$ and process $w$ that reached consensus with value $0$. Process
$v$ did set value $1$ as a result of the small consensus reached by the
Leader-Consensus procedure. So did process $w$ with value $0$. This
contradicts the agreement condition of Leader-Consensus.

∎

######  Corollary 1.

Instantiating Leader-Consensus with SynRan from [12] results in:

a) $\mathcal{O}\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ expected
rounds to reach consensus by Algorithm A,

b) expected work per process equal
$\mathcal{O}\left(\sqrt{\frac{n}{(n-f)^{3}\log(n/(n-f))}}\right)$,

c)
$\mathcal{O}\left(\log\left(\frac{1}{\epsilon}\right)\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$
rounds to reach consensus by Algorithm A with probability $1-\epsilon$, for
$\epsilon>0$.

Algorithm A is designed in the way that most of the processors wait until the
consensus value is decided and propagated through the communication medium.
Expected work per process value leads to an observation that, considering more
practical scenarios, most of the processors can take care about different
processes, while only a subset is responsible for actually reaching consensus.

###  3.3 Improving message complexity

The expected number of point-to-point messages sent by processes during the
execution of Algorithm A could be as large as the expected time
$\mathcal{O}\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ multiplied by
${\mathcal{O}}(n^{2})$ messages sent each round by the communication procedure
Propagate-Msg, which in the rough calculation could yield
$\mathcal{O}\left(n^{2}\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$ of total
point-to-point messages sent. Estimating more carefully, each round of
Propagate-Msg outside the Leader-Consensus execution costs
${\mathcal{O}}(n^{2})$ point-to-point messages, and each message exchange
inside the Leader-Consensus costs
${\mathcal{O}}\left(\frac{n^{2}}{(n-f)^{2}}\right)$ with constant probability,
which gives a more precise upper bound
$\mathcal{O}\left(n^{2}+\sqrt{\frac{n^{5}}{(n-f)^{5}\log(n/(n-f))}}\right)$ on
the expected number of point-to-point messages.

In order to improve message complexity, we modify Algorithm A in the following
way – we call the resulting protocol Algorithm B. Each communication round is
implemented by using a gossip protocol from [18], which is a deterministic
protocol guaranteeing successful exchange of messages between processes which
are non-faulty at the end of this protocol in $O(\log^{3}n)$ rounds using
$O(m\log^{4}n)$ point-to-point messages, where $m\leq n$ is the known upper
bound on the number of participating processes. This gives
${\mathcal{O}}(n\log^{4}n)$ point-to-point messages per execution of
Propagate-Msg outside of Leader-Consensus procedure, and
${\mathcal{O}}\left(\frac{n\log^{4}n}{n-f}\right)$ point-to-point messages,
with constant probability, in each exchange during the execution of Leader-
Consensus. Therefore, Algorithm B accomplishes consensus in
$\mathcal{O}\left(\sqrt{\frac{n\log^{5}n}{(n-f)}}\right)$ expected rounds
using
$\mathcal{O}\left(\left(\frac{n}{n-f}\right)^{3/2}\log^{7/2}n+n\log^{4}n\right)$
point-to-point messages in expectation. In particular, for large range of
crashes $f=n-\Omega(\sqrt{n})$, Algorithm B is nearly optimal (i.e., with
respect to a polylogarithm of $n$) in terms of both expected time and message
complexity. For a discussion about lower bounds see Section 3.4.

###  3.4 Lower bound

######  Theorem 2.

The expected number of rounds of any consensus protocol running against a
Weakly-Adaptive or a Non-Adaptive adversary causing up to $f$ crashes is
$\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$.

###### Proof.

Consider a consensus algorithm. We partition $n$ processes into
$m=\frac{n}{n-f}$ groups of size $n-f$ and treat each group as a distributed
entity similar as in the proof of the impossibility result for consensus
against at least third part of Byzantine processes, c.f., [9].

We assume that entities are described by a tuple, where each position in the
tuple corresponds to a certain processor and the elements of the tuple
describe processors’ states. Furthermore, we assume that communication between
entities is by sending concatenated messages of all the processes gathered in
a particular round.

Bar-Joseph and Ben-Or showed in [12] that the expected number of rounds of any
consensus protocol running against a Strongly-Adaptive adversary causing up to
$m/2$ crashes on $m$ processes is $\Omega\left(\sqrt{m/\log m}\right)$. We
call this adversary the Bar-Joseph and Ben-Or adversary, for reference. It
automatically implies, by Markov inequality, that with probability at least
$3/4$ an execution generated by the Bar-Joseph and Ben-Or adversary has length
$\Omega\left(\sqrt{m/\log m}\right)$. We apply this to the above mentioned
system of $m$ groups. This leads us to a class of executions that we denote
$\mathcal{A}_{s}$, generated by the Strongly-Adaptive adversary that simulates
all the executions of given algorithms until half of the entities remain
operational. We consider a class $\mathcal{A}_{s}$ as an execution tree that
we define as follows.

Let us assume that the execution tree of an algorithm is a tree where each
path from the root to the leaves represents the number of rounds a particular
execution takes. What is more, nodes are labeled with random bits and the
status of entities (which of them are operational) at a particular round of
the execution. Note that possible system configurations at round $i$ are
represented as nodes at level $i$ of the tree. This may lead to an enormously
huge tree, with each path/node having its probability of occurrence; yet we
assume that the adversary has sufficient computational power to build such a
structure.

We call such an execution _long_ if it has length $\Omega\left(\sqrt{m/\log
m}\right)$. Recall that the probability of an event that an execution against
the Bar-Joseph and Ben-Or adversary is in class $\mathcal{A}_{s}$ and is long
is at least $3/4$.

The tree is built along paths (corresponding to specific executions) until
half of the entities remain operational, hence there is an entity (i.e.,
group) $E$ that remained operational in at least half of these executions (or
more precisely, in executions which occur with probability at least $1/2$),
again by using a pigeonhole type of arguments with respect to the remaining
groups and executions. It follows that with probability at least $3/4-1/2=1/4$
a long execution in $\mathcal{A}_{s}$ contains group $E$.

Let us now consider a Weakly-Adaptive adversary that chooses $E$ as the group
of $n-f$ fault-resistant processes, before the execution of the algorithm. We
consider a class of executions $\mathcal{A}_{w}$ generated by the Weakly-
Adaptive adversary of Bar-Joseph and Ben-Or, by simulating the same executions
(until possible) as the Strongly-Adaptive one considered above. Note that such
adversary crashes whole groups. With probability at least $1/4$ there is an
execution containing $E$ (therefore, the Weakly-Adaptive adversary does not
stop it before the Strongly-Adaptive does) and of length
$\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$. This implies the
expected length of an execution caused by the Weakly-Adaptive adversary not
failing group $E$ to be at least
$1/4\cdot\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)=\Omega\left(\sqrt{\frac{n}{(n-f)\log(n/(n-f))}}\right)$.

In order to extend this bound into the model with Non-Adaptive adversary, we
recall that in the proof of the lower bound in [12], in each round a suitable
set of crashes could be done with probability $1-O(1/\sqrt{m})$. Therefore, by
a union bound over $\Theta(\sqrt{m/\log m})$ rounds, there is a path in the
tree used in the first part of this proof which leads to $\Theta(\sqrt{m/\log
m})$ rounds without consensus, with probability at least $1-1/\log m$. The
adversary selects this path, corresponding to the schedule of crashes of
subsequent groups on the path in consecutive rounds, prior the execution. This
assures that in the course of the execution consensus is not achieved within
the first $\Theta(\sqrt{m/\log m})$) rounds, with probability at least
$1-1/\log m$, thus also in terms of the expected number of rounds. ∎

Note that the lower bound on the expected number of point-to-point messages is
$\Omega(n)$ even for weaker non-adaptive adversaries, as each process has to
receive a message to guarantee agreement in case of potential crashes, c.f.,
[30] for references.

##  4 $k$-Chain-Ordered and $k$-Ordered adversaries

In this section we present Algorithm C \- a modification of Algorithm A
specifically tailored to run against the $k$-Chain-Ordered adversary.  Then we
also show that it is capable of running against a $k$-Ordered adversary. We
begin with a basic description of the algorithm.

###  4.1 Algorithm C

1Algorithm A with Elect-Leader substituted by Gather-Leaders;

2

Algorithm 3 Algorithm C,  pseudocode for process $v$

1initialize variable $n^{*}$;

2 $n^{*}:=\textsc{Count-Processes}$;

3 $i=\lfloor n/n^{*}\rfloor$;

4 $\texttt{coin}:=\frac{k}{2^{i-1}n^{*}}$;

5 initialize list LEADERS to an empty list;

6 toss a coin with the probability coin of heads to come up;

7 if  _heads came up in the previous step_ then

8 Propagate-Msg(“$v$”) to all other processes;

9 add $v$ to list LEADERS;

10 end if

11 fill in list LEADERS with elected leaders’ identifiers from received
messages;

12

13return LEADERS;

Algorithm 4 Gather-Leaders,  pseudocode for process $v$

1Propagate-Msg(“$v$”) to all other processes;

2 return the number of ID’s heard ;

3

Algorithm 5 Count-Processes,  pseudocode for process $v$

The algorithm begins with electing a number of leaders in Gather-Leaders.
However, as the adversary models its pattern of crashes into $k$ disjoint
chains then we would like to elect approximately $k$ leaders.

It may happen that the adversary significantly reduces the number of processes
and hence the leader election procedure is unsuccessful in electing an
appropriate number of leaders. That is why we adjust the probability of
success by approximating the size of the network before electing leaders. If
the initial number of processes was $n$ and the drop in the number of
processes after estimating the size of the network was not significant (less
than half the number of the approximation) then we expect to elect $\Theta(k)$
leaders.

Otherwise, if the number of processes was reduced by more than half, the
probability of success is changed and the expected number of elected leaders
is reduced. This helps to shorten executions of Leader-Consensus because a
smaller number of leaders executes the protocol faster. In general if there
are $\frac{n}{2^{i}}$ processes, we expect to elect
$\Theta\left(\frac{k}{2^{i}}\right)$ leaders.

Elected leaders are expected to be placed uniformly in the adversary’s order
of crashes. If we look at a particular leader $v$, then he will be present in
some chain $k_{i}$. What is more, his position within this chain is expected
to be in the middle of $k_{i}$.

Leaders execute the small consensus protocol Leader-Consensus. If they reach
consensus, then they communicate this fact twice to the rest of the system.
Hence, if the adversary wants to prolong the execution, then it must crash all
leaders. Otherwise, the whole system would reach consensus and end the
protocol.

If leaders are placed uniformly in the adversary’s order, then the adversary
must preserve the pattern of crashes that it declared at first. In what
follows, if there is a leader $v$ that is placed in the middle of chain
$k_{i}$, then half of the processes preceding $v$ must also be crashed.

When the whole set of leaders is crashed then another group is elected and the
process continues until the adversary spends all its possibilities of failing
processes.

######  Theorem 3.

The following hold Algorithm C against the $k$-Chain-Ordered adversary:

a) Algorithm C reaches consensus in the expected number of rounds equal
$\mathcal{O}(T_{LC}(k)\log(n/k))$, satisfying termination, agreement and
validity.

b) Expected work per process of Algorithm C is
$\frac{k}{n}\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$.

c) Algorithm C reaches consensus in the number of rounds equal
$\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$ and with work
per process $\frac{k}{n}\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$ at least with
probability $1-e^{-\frac{k^{1/4}}{24}+\log\log k^{2}}$.

######  Corollary 2.

Instantiating Leader-Consensus with SynRan from [12] results in:

a) $\mathcal{O}\left(\sqrt{\frac{k}{\log k}}\log(n/k)\right)$ expected number
of rounds to reach consensus by Algorithm C,

b) expected work per process equal
$\frac{k}{n}\log\left(\frac{n}{k}\right)\mathcal{O}\left(\sqrt{\frac{k}{\log
k}}\log(n/k)\right)$,

c) $\mathcal{O}\left(\sqrt{\frac{k}{\log k}}\log(n/k)\right)$ rounds to reach
consensus by Algorithm C with probability $1-e^{-\frac{k^{1/4}}{24}+\log\log
k^{2}}$.

###  4.2 Algorithm C against the adversary limited by an arbitrary partial
order

Let us consider the adversary that is limited by an arbitrary partial order
$P=(P,\succ)$. Two elements in this partially ordered set are incomparable if
neither $x\succ y$ nor $y\succ x$ hold. Translating this into our model, the
adversary may crash incomparable elements in any sequence during the execution
of the algorithm.

######  Theorem 4.

Algorithm C reaches consensus in expected $\mathcal{O}(T_{LC}(k)\log(n/k))$
number of rounds, against the $k$-Ordered adversary, satisfying termination,
agreement and validity.

###  4.3 Lower bound

######  Theorem 5.

For any reliable randomized algorithm solving consensus in a message-passing
model and any integer $0<k\leq f$, there is a $k$-Ordered adversary that can
force the algorithm to run in $\Omega(\sqrt{k/\log k})$ expected number of
rounds.

###### Sketch.

The adversary takes the order consisting of $n/k$ independent chains, and
follows the analysis for Strongly-Adaptive adversaries in [12], with the
following modification: if the analysis enforces crashing a process $v$, the
adversary crashes the whole chain to which $v$ belongs. Since there are $k$
chains and $k-1$ possible chain-crashes, by replacing $n$ by $k$ in the
formula obtained in [12] we get $\Omega(\sqrt{k/\log k})$ expected number of
rounds. ∎

##  5 Conclusions and open problems

In this work we showed time and message efficient randomized consensus against
the Weakly-Adaptive, Non-Adaptive and Ordered adversaries generating crashes.
We proved that  all these classes of Constrained adaptive adversaries are
weaker than the Strongly-Adaptive one. Our results also extend the state-of-
the-art of the study of popular Non-Adaptive adversaries.

## References

  * [1] Karl Abrahamson.  On achieving consensus using a shared memory.  In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’88, pages 291–302, New York, NY, USA, 1988. ACM.
  * [2] Eugene S. Amdur, Samuel M. Weber, and Vassos Hadzilacos.  On the message complexity of binary byzantine agreement under crash failures.  Distributed Computing, 5(4):175–186, Apr 1992.
  * [3] James Aspnes.  Lower bounds for distributed coin-flipping and randomized consensus.  J. ACM, 45(3):415–450, May 1998.
  * [4] James Aspnes.  Randomized protocols for asynchronous consensus.  Distrib. Comput., 16(2-3):165–175, September 2003.
  * [5] James Aspnes, Hagit Attiya, and Keren Censor.  Randomized consensus in expected $\mathcal{O}(n\log n)$ individual work.  In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, pages 325–334, New York, NY, USA, 2008. ACM.
  * [6] James Aspnes and Maurice Herlihy.  Fast randomized consensus using shared memory.  J. Algorithms, 11:441–461, 1990.
  * [7] James Aspnes and Orli Waarts.  Randomized consensus in expected $\mathcal{O}(n\log^{2}n)$ operations per processor.  SIAM J. Comput., 25(5):1024–1044, October 1996.
  * [8] Hagit Attiya and Keren Censor.  Tight bounds for asynchronous randomized consensus.  J. ACM, 55(5):20:1–20:26, November 2008.
  * [9] Hagit Attiya and Jennifer Welch.  Distributed Computing: Fundamentals, Simulations and Advanced Topics.  John Wiley & Sons, Inc., USA, 2004.
  * [10] Yonatan Aumann.  Efficient asynchronous consensus with the weak adversary scheduler.  In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’97, pages 209–218, New York, NY, USA, 1997. ACM.
  * [11] Yonatan Aumann and Michael A. Bender.  Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler.  Distributed Computing, 17:191–207, 03 2005.
  * [12] Ziv Bar-Joseph and Michael Ben-Or.  A tight lower bound for randomized synchronous consensus.  In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, pages 193–199, New York, NY, USA, 1998. ACM.
  * [13] Michael Ben-Or.  Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols.  In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC ’83, pages 27–30, New York, NY, USA, 1983. ACM.
  * [14] Gabriel Bracha and Ophir Rachman.  Randomized consensus in expected $\mathcal{O}(n^{2}\log n)$ operations.  In Proceedings of the 5th International Workshop on Distributed Algorithms, WDAG ’91, pages 143–150, Berlin, Heidelberg, 1992. Springer-Verlag.
  * [15] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  J. ACM, 32(4):824–840, October 1985.
  * [16] Tushar Deepak Chandra.  Polylog randomized wait-free consensus.  In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’96, pages 166–175, New York, NY, USA, 1996. ACM.
  * [17] Bogdan S. Chlebus and Dariusz R. Kowalski.  Robust gossiping with an application to consensus.  J. Comput. Syst. Sci., 72(8):1262–1281, December 2006.
  * [18] Bogdan S. Chlebus and Dariusz R. Kowalski.  Time and communication efficient consensus for crash failures.  In Distributed Computing, 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18-20, 2006, Proceedings, pages 314–328, 2006\.
  * [19] Bogdan S. Chlebus and Dariusz R. Kowalski.  Locally scalable randomized consensus for synchronous crash failures.  In Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures, SPAA ’09, pages 290–299, New York, NY, USA, 2009. ACM.
  * [20] Bogdan S. Chlebus, Dariusz R. Kowalski, and Michal Strojnowski.  Fast scalable deterministic consensus for crash failures.  In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC ’09, pages 111–120, New York, NY, USA, 2009. ACM.
  * [21] Benny Chor, Michael Merritt, and David B. Shmoys.  Simple constant-time consensus protocols in realistic failure models.  J. ACM, 36(3):591–614, July 1989.
  * [22] R. P. Dilworth.  A decomposition theorem for partially ordered sets.  Annals of Mathematics, 51(1):161–166, 1950.
  * [23] Danny Dolev and Rüdiger Reischuk.  Bounds on information exchange for byzantine agreement.  J. ACM, 32(1):191–204, January 1985.
  * [24] Pesech Feldman and Silvio Micali.  An optimal probabilistic protocol for synchronous byzantine agreement.  SIAM J. Comput., 26(4):873–933, August 1997.
  * [25] Michael J. Fischer and Nancy A. Lynch.  A lower bound for the time to assure interactive consistency.  Information Processing Letters, 14(4):183 – 186, 1982.
  * [26] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of distributed consensus with one faulty process.  J. ACM, 32(2):374–382, April 1985.
  * [27] Juan A. Garay and Yoram Moses.  Fully polynomial byzantine agreement in t + 1 rounds.  In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC ’93, pages 31–41, New York, NY, USA, 1993. ACM.
  * [28] Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski.  On the complexity of asynchronous gossip.  In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, pages 135–144, New York, NY, USA, 2008. ACM.
  * [29] Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski.  On the message complexity of indulgent consensus.  In Andrzej Pelc, editor, Distributed Computing, pages 283–297, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
  * [30] Seth Gilbert and Dariusz R. Kowalski.  Distributed agreement with optimal communication complexity.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 965–977, 2010.
  * [31] Vassos Hadzilacos and Joseph Y. Halpern.  Message-optimal protocols for byzantine agreement.  Mathematical systems theory, 26(1):41–102, Jan 1993.
  * [32] Dan Holtby, Bruce M. Kapron, and Valerie King.  Lower bound for scalable byzantine agreement.  Distributed Computing, 21(4):239–248, Oct 2008.
  * [33] Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee.  Towards secure and scalable computation in peer-to-peer networks.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages 87–98, Washington, DC, USA, 2006. IEEE Computer Society.
  * [34] Marek Klonowski, Dariusz R. Kowalski, and Jarosław Mirek.  Ordered and delayed adversaries and how to work against them on a shared channel.  Distributed Computing, Sep 2018.
  * [35] Dariusz R. Kowalski and Miguel A. Mosteiro.  Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 156:1–156:14, 2018.
  * [36] Michael C Loui and Hosame H Abu-Amara.  Memory requirements for agreement among unreliable asynchronous processes.  Advances in Computing research, 4(163-183):31, 1987.
  * [37] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, New York, NY, USA, 2005.
  * [38] Yoram Moses and Sergio Rajsbaum.  A layered analysis of consensus.  SIAM Journal on Computing, 31(4):989–1021, 2002.
  * [39] Michael O. Rabin.  Randomized byzantine generals.  24th Annual Symposium on Foundations of Computer Science (FOCS 1983), pages 403–409, 1983.
  * [40] Peter Robinson, Christian Scheideler, and Alexander Setzer.  Breaking the $\Omega(\sqrt{n})$ barrier: Fast consensus under a late adversary.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pages 173–182, 2018.

## Appendix

##  Appendix A Additional related work and open problems

#### Additional related work.

Fisher, Lynch and Paterson [26] showed that for the message passing model
consensus cannot be solved deterministically in the asynchronous settings,
even if only one process may crash. Loui and Abu-Amara [36] showed a
corresponding result for shared memory. These impossibility results can be
circumvented when randomization is used and the consensus termination
condition does not hold with probability $1$.

Bracha and Toueg [15] observed that it is impossible to reach consensus by a
randomized algorithm in the asynchronous model with crashes if the majority of
processes are allowed to crash. Ben-Or [13] gave the first randomized
algorithm solving consensus in the asynchronous message passing model under
the assumption that the majority of processes are non-faulty. For the strong
adversary Abrahamson [1] gave the first randomized solution in the shared
memory model, which had exponential work, and Aspnes and Herlihy [6] gave the
first polynomial-work algorithm for the same adversary. Aspnes and Waarts [7],
Bracha and Rachman [14], and Aspnes, Attiya and Censor [5] gave solutions with
${\mathcal{O}}(n\,{\mbox{polylog}}n)$ work per process. Aspnes [3] showed that
this was best possible up to a poly-logarithmic factor by showing that any
algorithm for the strong adversary requires $\Omega(f^{2}/\log^{2}f)$ work by
proving that these many coin flips were needed. Attiya and Censor [8] resolved
the work complexity of randomized consensus in shared memory against the
strong adversary by showing that $\Theta(n^{2})$ total work is both sufficient
and necessary, building on the work of Aspens and Herlihy [6], Bar-Joseph and
Ben-Or [12], and Moses and Rajsbaum [38]. Research on weak adversaries [10,
11, 16], that may observe coin flips and the content of shared registers,
resulted in scalable algorithms of ${\mathcal{O}}(n\,{\mbox{polylog}}n)$ total
work and ${\mathcal{O}}({\mbox{polylog}}n)$ work per process.

Deterministic consensus solutions operating in time ${\mathcal{O}}(f)$ with
sub-quadratic message complexities usually rely on gossiping procedures, as
given for instance in [17, 18, 29]. All such algorithms send $\Omega(n^{2})$
bits in messages in the worst case, by the nature of gossiping. Solutions
given in [18, 29] are _early stopping_ i.e. they terminate in
${\mathcal{O}}(f)$ rounds where $f\leq n$ is the number of failures that
actually occur in a given execution. Georgiou, Gilbert, Guerraoui and Kowalski
[28] gave a randomized solution for asynchronous message passing systems with
processes prone to crashes which sends $o(n^{2})$ messages, but their
algorithm has $\omega(n^{2})$ bit complexity.

Deterministic Byzantine consensus requires $\Omega(fn)$ message complexity,
which can be improved with the use of randomization. A Byzantine consensus
algorithm achieves _consensus with loss $h(f)$_ if at least $n-h(f)$ non-
faulty processes eventually decide on a common value when up to $f$ processes
are corrupted. An _almost-everywhere consensus_ means consensus with loss
$h(f)$ for some function $h(f)\leq cf$, where $c<1$ is a constant. The first
randomized solutions for almost-everywhere Byzantine consensus and leader
election scalable with respect to bit communication complexity were given by
King, Saia, Sanwalani and Vee [33]. A tradeoff between the time required to
solve an almost everywhere Byzantine consensus by a randomized scalable
solution and the magnitude of loss was proved by Holtby, Kapron and King [32].
They showed that if $f$ is a constant fraction of $n$ then a scalable solution
requires $\Omega(n^{1/3})$ rounds.

The consensus problem has been recently considered against different
adversarial scenarios. Robinson, Scheideler and Setzer [40] considered the
synchronous consensus problem under a late $\epsilon$-bounded adaptive
adversary, whose observation of the system is delayed by one round and can
block up to $\epsilon n$ nodes in the sense that they cannot receive and send
messages in a particular round.

#### Open problems.

Three main open directions emerge from this work. One is to improve message
complexity for the whole range of the number of crashes $f$, especially those
close to $n$ by less than $\sqrt{n}$. Another open direction could pursue a
study of complexities of other important distributed problems and settings
against Weakly-Adaptive and Ordered adversaries,  which are more realistic
than the Strongly-Adaptive one and more general than the Non-Adaptive one,
commonly used in the literature. Finally, there is a scope of proposing and
studying other intermediate types of adversaries, including further study of
recently proposed delayed adversaries [34] and adversaries tailored for
dynamic distributed and parallel computing [35].

##  Appendix B Algorithm A flow diagram

Figure 1: Algorithm A flow diagram for process $v$.

##  Appendix C Proof of Lemma 1

###### Proof.

Let $X$ be a random variable such that $X=X_{1}+\cdots+X_{n},$ where
$X_{1},\cdots,$ $X_{n}$ are Poisson trials and

$X_{i}=\left\\{\begin{array}[]{ll}1&\textrm{if process i chosen a leader,}\\\
0&\textrm{otherwise.}\end{array}\right.$

We know that
$\mu=\mathbb{E}X=\mathbb{E}X_{1}+\cdots+\mathbb{E}X_{n}=\frac{n}{n-f}.$ To
estimate the probability that the number of leaders lies within the expected
interval we will use the following Chernoff’s inequality: $\mathbb{P}[X\geq
R]\leq 2^{-R}$, where $R\geq 6\mu.$

Let $R=6\frac{n}{n-f}$. Then $\mathbb{P}\left[X\geq 6\frac{n}{n-f}\right]\leq
2^{-6\frac{n}{n-f}}\leq\frac{1}{2^{6}}\leq\frac{1}{10}.$ In what follows with
probability $\frac{9}{10}$ the number of leaders is less than
$6\frac{n}{n-f}$. ∎

##  Appendix D Proof of Lemma 2

###### Proof.

There are $n$ processes out of which $f$ are prone to crashes. Hence the
system contains $n-f$ fault-resistant processes. The probability that a fault-
resistant one will respond in the election procedure is $\frac{1}{n-f}$. We
estimate the probability of electing at least one fault-resistant leader by a
complementary event that none of the fault-resistant processes responded
during the election procedure:
$\left(1-\left(1-\frac{1}{n-f}\right)^{n-f}\right)\geq(1-e^{-1})\geq\frac{6}{10}.$

∎

##  Appendix E Proof of Theorem 1 b) and c)

###### Proof.

b) In each iteration of Algorithm A a process either becomes a leader or stays
idle, waiting to hear and adopt the consensus value decided by leaders. This
leads to an observation that the actual work is done by processes taking part
in Leader-Consensus. We know that $\frac{5}{2}$ is the expected number of
iterations of Algorithm A and each process becomes a leader in each iteration
with probability $\frac{1}{n-f}$. The expected number of rounds in each
iteration is $\mathcal{O}(T_{LC}(\frac{6n}{n-f}))$, hence by applying Wald’s
equation ([37], Theorem 12.3) we have that
$\frac{1}{n-f}\;\mathcal{O}(T_{LC}(\frac{6n}{n-f}))$ is the expected work per
process.

c) We know that $\mathbb{P}(Z)\geq\frac{2}{5}$. Let $\epsilon>0$ be fixed and
$X\sim Geo\left(\frac{2}{5}\right)$. We have that $\mathbb{P}(X\geq
i)=\left(1-\frac{2}{5}\right)^{i-1}$.

Taking $i=\frac{5}{2}\log\left(\frac{1}{\epsilon}\right)+1$, we have that
$\mathbb{P}\left(X\geq\frac{5}{2}\log\left(\frac{1}{\epsilon}\right)+1\right)\leq
e^{-\log\left(\frac{1}{\epsilon}\right)}=\epsilon$. Thus,
$\mathbb{P}\left(X<\frac{5}{2}\log\left(\frac{1}{\epsilon}\right)+1\right)>1-\epsilon$.

Applying this to the results from points a) and b) of the proof gives the
desired result.

∎

##  Appendix F Proof of Theorem 3

In order to prove Theorem 3 we need the following Lemma

######  Lemma 3.

Let $L$ denote the number of leaders elected by Gather-Leaders, $n^{*}$ be the
number of operational processes and $k$ denote the number of chains in the
adversary’s order and $l$ denote the number of leaders that the protocol would
like to elect, where $l=\frac{k}{2^{i}}$ for $0\leq i\leq\log k$. Then
$l/4<L<3l/4$ at least with probability $1-2e^{-l/24}$.

###### Proof.

Let $X$ be a random variable such that $X=X_{1}+\cdots+X_{n^{*}},$ where
$X_{1},\cdots,$ $X_{n^{*}}$ are Poisson trials and

$X_{j}=\left\\{\begin{array}[]{ll}1&\textrm{if process i chosen a leader,}\\\
0&\textrm{otherwise.}\end{array}\right.$

Since the number of operational processes is $n^{*}$ and the probability of
success is set to at most $\frac{l}{2n^{*}}$ in the Gather-Leaders procedure,
we know that
$\mu\leq\mathbb{E}X=\mathbb{E}X_{1}+\cdots+\mathbb{E}X_{n^{*}}=\frac{l}{2}.$
To estimate the probability that the number of leaders lies within the
expected interval we use the following Chernoff’s inequalities:

  1. 1.

$\mathbb{P}[X\geq(1+\delta)\mu]\leq e^{-\mu\delta^{2}/3},$ for $0<\delta\leq
1$.

  2. 2.

$\mathbb{P}[X\leq(1-\epsilon)\mu]\leq e^{-\mu\epsilon^{2}/2},$ for
$0<\epsilon<1$.

Taking $\delta=\epsilon=\frac{1}{2}$, we have that
$\mathbb{P}\left[X\geq\frac{3l}{4}\right]\leq e^{-l/24}$ and
$\mathbb{P}\left[X\leq\frac{l}{4}\right]\leq e^{-l/16}$. Hence
$\mathbb{P}\left[X<\frac{3l}{4}\right]>1-e^{-l/24}$ and
$\mathbb{P}\left[X>\frac{l}{4}\right]>1-e^{-l/16}$. In what follows
$l/4<L<3l/4$ at least with probability $1-2e^{-l/24}$.

∎

We now proceed with the proof of Theorem 3

###### Proof.

a) Algorithm C is structured as a repeat loop at the beginning of which a
leader election procedure is executed. Gather-Leaders approximates the size of
the network in the first place by a very simple procedure Count-Processes in
order to adjust the coin values appropriately.

After the number of processes is counted it may happen that the adversary
crashes some of the processes, so that their number drops significantly i.e.
by more than half the number returned by Count-Processes. We will, however,
firstly analyze the opposite situation when the drop is not significant to
explain the basic situation and calculate the resulting time for the algoritm
to succeed. Then we will proceed to the analysis of the situation when the
adversary reduces the number of operational processes significantly and
calculate a union bound over all such cases.

According to Lemma 3 Gather-Leaders returns $\Theta(k)$ leaders. In what
follows the expected number of rounds required to reach small consensus by
Leader-Consensus is $\mathcal{O}(T_{LC}(k))$.

Note that the adversary has to crash all the leaders at some point of the
Leader-Consensus protocol to prolong the execution. Otherwise, there would be
a processe that would reach small consensus and inform all other processes
about the consensus value.

According to the adversary’s partial order there are initially $k$ chains,
where chain $j$ has length $l_{j}$. If a leader is elected then it belongs to
one of the chains. We show that it is expected that the chosen leader is
placed in the middle of that chain.

Let $X$ be a random variable such that $X_{j}=i$ where $i$ represents the
position of the leader in chain $j$. We have that
$\mathbb{E}X_{j}=\sum_{i=1}^{l_{j}}\frac{i}{l_{j}}=\frac{1}{l_{j}}\frac{(1+l_{j})}{2}l_{j}=\frac{(1+l_{j})}{2}.$

If the leader is crashed, this implies that half of the processes forming the
chain are also crashed. If at some other points of time, the leaders will also
be elected from the same chain, then by simple induction we may conclude that
this chain is expected to be all crashed after $\mathcal{O}(\log(n/k))$ steps
in average.

In what follows if there are $k$ chains and we expect to elect $\Theta(k)$
leaders, then after at most $\mathcal{O}(\log(n/k))$ steps this process ends,
as the adversary runs out of all the possibilities of crashing. Assuming that
the adversary crashes the last leader just before it is to communicate the
consensus value we may estimate that each such step needs
$\mathcal{O}(T_{LC}(k))$ time for running Leader-Consensus. Hence, the
expected time for Algorithm C to reach consensus is
$\mathcal{O}(T_{LC}(k)\log(n/k))$.

Let us now proceed to the situation when the adversary crashes a significant
number of processes (i.e. more than half of them). In such case procedure
Gather-Leaders changes the probability of success of electing the leaders as
well as reduces the expected number of leaders that should be elected in the
next iteration of the algorithm.

Once again, according to Lemma 3, we expect procedure Gather-Leaders to return
$\Theta(k/2^{i})$ leaders for some $0\leq i\leq\log k$, since the number of
such drops is bounded by $\log k$. Calculating the time required to reach
consensus over all cases gives us $\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\log\left(\frac{n}{2^{i}k}\right)\right)=\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$.

Altogether we have that Algorithm C requires
$\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$ expected number
of rounds to reach consensus, where termination, validity and agreement are
satisfied because of the same arguments as in Theorem 1.

b) Similarly as in the proof of Theorem 1, if there are $n^{*}$ operational
processes, and there were no significant drops in this number, we know that
$\log\left(\frac{n}{k}\right)$ is the expected number of iterations of
Algorithm C and each process becomes a leader in each iteration with
probability $\frac{k}{n^{*}}$. The expected number of rounds in each iteration
is $\mathcal{O}(T_{LC}(k))$, hence by applying Wald’s equation ([37], Theorem
12.3) we have that $\frac{k}{n^{*}}\;\mathcal{O}(T_{LC}(k))$ is the expected
work per process.

However assuming that significant drops may happen while Leader-Consensus
procedure, we need to calculate a union bound over all the cases, which for
each $0\leq i\leq\log k$ gives us $\log\left(\frac{n}{2^{i}k}\right)$ expected
number of iterations of Algorithm C and the probability that each process
becomes a leader equal $\frac{k}{2^{i}\frac{n}{2^{i}}}$. The expected number
of rounds in each iteration for a particular $i$ is
$\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$. Summing this
altogether we have that the expected work per process is equal
$\sum_{i=0}^{\log
k}\frac{k}{n}\;\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)\log\left(\frac{n}{2^{i}k}\right)=\frac{k}{n}\log\left(\frac{n}{k}\right)\sum_{i=0}^{\log
k}\mathcal{O}\left(T_{LC}\left(\frac{k}{2^{i}}\right)\right)$.

c) The success of the algorithm depends on successful leader election through
all the cases of significant drops in the number of operational processes.
According to Lemma 3 for each $0\leq i\leq\log k$ the probability that Leader-
Consensus is successful in returning $\Theta\left(\frac{k}{2^{i}}\right)$
leaders is $1-2e^{-\frac{k}{2^{i}}\frac{1}{24}}$. We want to calculate the
probability that Leader-Consensus is successful over all cases. Let $A_{i}$ be
an event that is was successful in the $i$’th case. We have that
$\mathbb{P}\left(\bigcap_{i=1}^{\log k}A_{i}\right)=\bigcap_{i=1}^{\log
k}\left(1-2e^{-\frac{k}{2^{i}}\frac{1}{24}}\right)\geq\bigcap_{i=1}^{\log
k}\left(1-2e^{-\frac{k}{2^{\log k}}\frac{1}{24}}\right).$ Since $2^{\log
k}=e^{\log 2\log k}=e^{\log k^{\log 2}}=k^{\log 2}$ and $\frac{1}{2}<\log
2<1$, thus $\bigcap_{i=1}^{\log k}\left(1-2e^{-\frac{k}{2^{\log
k}}\frac{1}{24}}\right)\geq\bigcap_{i=1}^{\log
k}\left(1-2e^{-\frac{k^{1/4}}{24}}\right)=\left(1-2e^{-\frac{k^{1/4}}{24}}\right)^{\log
k}.$ Using the Bernoulli inequality we continue having
$\left(1-2e^{-\frac{k^{1/4}}{24}}\right)^{\log k}\geq 1-2\log
k\;e^{-\frac{k^{1/4}}{24}}=1-e^{-\frac{k^{1/4}}{24}+\log\log k^{2}}.$ Applying
the result above to points a) and b) finishes the proof.

∎

Since, similarly as in the analysis of Algorithm A we would like to
instantiate procedure Leader-Consensus with algorithm SynRan from [12], we
introduce the following fact, allowing us to sum the time complexity
appropriately in Corrollary 2.

######  Fact 1.

Let $n,k\in\mathbb{N}$, where $0\leq k\leq n$. Then $\sum_{m=0}^{\log
k}\sqrt{\frac{k}{2^{m}\log\left(\frac{k}{2^{m}}\right)}}\log\left(\frac{n}{2^{m}k}\right)=c\;\sqrt{\frac{k}{\log
k}}\log\left(\frac{n}{k}\right),$ for some constant $c$.

###### Proof.

We have that $\sum_{m=0}^{\log
k}\sqrt{\frac{k}{2^{m}\log\left(\frac{k}{2^{m}}\right)}}\log\left(\frac{n}{2^{m}k}\right)\leq\log\left(\frac{n}{k}\right)\sum_{m=0}^{\log
k}\sqrt{\frac{k}{2^{m}\log\left(\frac{k}{2^{m}}\right)}}.$ Since $m\leq\log
k$, then $\log\left(\frac{k}{2^{m}}\right)\geq\log\left(\frac{k}{2^{\log
k}}\right)=\log(k^{1-\log 2})=(1-\log 2)\log k\geq\frac{1}{4}\log k,$ because
$2^{\log k}=e^{\log 2\log k}=e^{\log k^{\log 2}}=k^{\log 2}$ and
$\frac{1}{2}<\log 2<1$. Hence $\log\left(\frac{n}{k}\right)\sum_{m=0}^{\log
k}\sqrt{\frac{k}{2^{m}\log\left(\frac{k}{2^{m}}\right)}}\leq
2\log\left(\frac{n}{k}\right)\sum_{m=0}^{\log k}\sqrt{\frac{k}{2^{m}\log
k}}\leq 2\sqrt{\frac{k}{\log k}}\log\left(\frac{n}{k}\right)\sum_{m=0}^{\log
k}2^{-m/2}\leq c\;\sqrt{\frac{k}{\log k}}\log\left(\frac{n}{k}\right)$.

∎

##  Appendix G Proof of Theorem 4

###### Proof.

We assume that crashes forced by the adversary are constrained by some partial
order $P$. Let us recall the following lemma.

######  Lemma 4.

(Dilworth’s theorem [22]) In a finite partial order, the size of a maximum
anti-chain is equal to the minimum number of chains needed to cover all
elements of the partial order.

The $k$-Ordered adversary is constrained by an arbitrary order of thickness
$k$. The adversary by choosing some $f$ processes to be crashed cannot
increase the size of the maximal anti-chain. Thus using Lemma 4 we consider
the coverage of the crash-prone processes by at most $k$ disjoint chains and
any dependencies between chains’ elements create additional constraints to the
adversary comparing to the $k$-Chain-Ordered one. Hence we fall into the case
concluded in Theorem 3 that completes the proof.

∎