# Practical Byzantine Reliable Broadcast on
Partially Connected Networks

Silvia Bonomi1, Jérémie Decouchant2, Giovanni Farina1, Vincent Rahli3,
Sébastien Tixeuil4  1Sapienza Università di Roma, 2Delft University of
Technology,
3University of Birmingham, 4Sorbonne University, CNRS, LIP6
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the Byzantine reliable broadcast problem on
authenticated and partially connected networks. The state-of-the-art method to
solve this problem consists in combining two algorithms from the literature.
Handling asynchrony and faulty senders is typically done thanks to Gabriel
Bracha’s authenticated double-echo broadcast protocol, which assumes an
asynchronous fully connected network. Danny Dolev’s algorithm can then be used
to provide reliable communications between processes in the global fault
model, where up to f processes among N can be faulty in a communication
network that is at least 2f+1-connected. Following recent works that showed
that Dolev’s protocol can be made more practical thanks to several
optimizations, we show that the state-of-the-art methods to solve our problem
can be optimized thanks to layer-specific and cross-layer optimizations. Our
simulations with the Omnet++ network simulator show that these optimizations
can be efficiently combined to decrease the total amount of information
transmitted or the protocol’s latency (e.g., respectively, -25% and -50% with
a 16B payload, N=31 and f=4) compared to the state-of-the-art combination of
Bracha’s and Dolev’s protocols.

###### Index Terms:

Byzantine reliable broadcast, partially connected networks, synchronous or
asynchronous communications

##  I Introduction

At their very core, distributed systems consist of autonomous computing
entities (or processes) that _communicate_ to globally solve non-trivial
tasks. Over the years, distributed systems became ubiquitous and increased the
possibility that some of the processes fail in some unpredictable manner. The
most general fault model is the Byzantine model, that allows a process to
simply exhibit arbitrary behavior. Byzantine processes are opposed to correct
processes, that trustfully follow their prescribed algorithm. In this context,
communicating reliably may become difficult, especially when processes have to
rely on other (possibly Byzantine) processes to convey the information they
want to send (that is, the network is partially connected).

Two useful global communication abstractions have been defined in this
context. First, the _reliable communication_ (RC) abstraction requires that:
_(i)_ when a correct process broadcasts a message, this message is then
delivered by all correct processes, and _(ii)_ when a message originating from
a correct process is delivered, it was indeed sent by this correct process.
Reliable communication is also referred to as _reliable broadcast with honest
dealer_ , outlining that the source of a message is always correct. Second,
the _reliable broadcast_ abstraction considers the additional case where the
sender of a message may be arbitrarily faulty. In this case, all correct
processes are supposed to deliver the same message. Reliable broadcast, often
abbreviated as BRB (Byzantine Reliable Broadcast), guarantees stronger
properties than reliable communication, yet both abstractions can be
implemented in a fully asynchronous network. Recently, protocols that rely on
Byzantine reliable broadcast have been used to implement Blockchain consensus
[1] and payments [2].

The most well known asynchronous BRB protocol is probably Gabriel Bracha’s
algorithm, which is sometimes named double echo authenticated broadcast [3].
This protocol assumes a fully connected network of $N$ processes (among which
at most $f{<}N/3$ are Byzantine) and authenticated network links.

Questioning whether it is possible to remove the full connectivity assumption
in an asynchronous setting leads to Danny Dolev’s RC algorithm [4], as long as
the network is "sufficiently well connected" (a necessary and sufficient
condition for RC in arbitrary networks is that the connectivity of the network
is at least $2f+1$, where $f$ is the number of Byzantine processes). However,
Dolev’s algorithm does not solve BRB, as it does not prevent a Byzantine
faulty process from causing correct processes to _not all_ deliver the same
message. Nevertheless, Bracha’s and Dolev’s protocols can be combined to solve
BRB in sufficiently well-connected synchronous or asynchronous network
topologies [5].

In this paper, we start from this state-of-the-art solution to the BRB problem
in partially connected networks, and make the following contributions (code
available online111https://github.com/jdecouchant/BRB-on-partially-connected-
networks):
(i) We describe how state-of-the-art optimizations of Dolev’s RC algorithm [6]
can be extended to the BRB combination of Bracha’s and Dolev’s algorithms.
(ii) We present a total of 12 novel modifications that can be applied to the
BRB combination of Bracha’s and Dolev’s algorithms, some of them being cross-
layer.
(iii) We evaluate the impact of each modification on the protocol latency and
throughput using Omnet++ simulations in a large variety of settings.
(iv) We detail how these modifications should be combined depending on the
network asynchrony and connectivity, and on the payload size to optimize
latency and/or throughput.

The remainder of this paper is organized as follows. Sec. II discusses the
related work. Sec. III describes the system model and the BRB problem. Sec. IV
provides some background on BRB algorithms on asynchronous partially connected
networks. Sec. V explains how we modify the interface of the Bracha-Dolev
protocol to include state-of-the-art improvements of Dolev’s protocol, and to
add functionalities. Sec. VI and Sec. VII respectively present our latency and
throughput modifications of the Bracha-Dolev protocol, which we call MBD.1 to
MBD.12. Sec. VIII details our performance evaluation. Finally, Sec. IX
concludes the paper.

##  II Related Work

The first protocol to consider the Byzantine Reliable Broadcast (BRB) problem
assumed authenticated links222Let us recall that authenticated links guarantee
that the identity of the sender cannot be forged and can be implemented
without cryptography [7]..

Bracha and Toueg formalized the Reliable Broadcast problem [8, 9] and then
Bracha described the first BRB protocol for asynchronous and fully connected
reliable networks (i.e., networks where each process is able to communicate
with any other in the system and where messages cannot be lost) and the
proposed solution is able to tolerate $f$ Byzantine nodes (where $f<N/3$ and
$N$ is the number of processes in the system) [3]. This protocol is
characterized by three different all-to-all communication phases (namely,
_send_ , _echo_ and _ready_) and processes progress in the algorithm as soon
as they have heard from a quorum of nodes in a given phase.

This protocol assumes a fully connected communication network and thus its
applicability in general networks (like the ones considered in this paper) is
not directly possible but requires some adaptation.

Concerning generic networks where full connectivity cannot be assumed, Dolev
[4] showed that correct processes can reliably communicate in presence of $f$
Byzantine nodes if, and only if, the network graph is $(2f{+}1)$-connected.

In particular, Dolev’s algorithm allows a process $p_{i}$ to deliver a message
when it receives it through at least $f+1$ disjoint paths on which processes
behaved correctly (which is made possible when it flows through at least
$2f+1$ disjoint paths). In order to do that, it requires to solve a maximum
disjoint paths problem. Also in this case, the solution assumes authenticated
and reliable point-to-point communication links.

Despite its theoretical correctness, Dolev’s solution is not practical in
large networks due to its worse-case complexity both in terms of messages and
computational complexity.

Bonomi et al. [6] proposed several optimizations that improve the performance
of Dolev’s algorithm on unknown topologies. Indeed, a few modifications allow
to save messages, making the algorithm more appealing from a practical point
of view even if its worst-case complexity still remains high. Maurer et al.
[10] considered the reliable communication problem in settings where the
topology can vary with time. In Maurer et al.’s protocol, a process needs to
solve the minimum vertex cut problem instead of the not equivalent (in dynamic
networks) maximum disjoint paths problem.

Instead of assuming the global fault model, Koo presented a broadcast
algorithm under the $t$-locally bounded fault model [11], which was later
coined CPA (Certified Propagation Algorithm) [12]. Tseng et al. provided a
necessary and sufficient condition for CPA to work correctly on a given
topology [13]. Several authors have defined weaker reliable communication
primitives for improved scalability [14, 15].

All the aforementioned works [4, 6, 10, 13, 11, 12] solve a weaker problem
than BRB, indeed they guarantee that all correct processes eventually deliver
messages diffused by a correct source but no agreement in case of a faulty
one.

More recently, BRB on partially connected networks has been achieved by
combining Bracha’s and Dolev’s algorithms333One can also combine Bracha and
CPA, but the different local Byzantine conditions yields a stronger
requirement to be satisfied.. For example, Wang and Wattenhoffer used this
method to design a randomized Byzantine agreement protocol [5]. We show in
this work that the two protocols can be combined in a more efficient way. We
evaluate the impact of our modifications to the combination of Bracha’s
algorithm with Bonomi et al. [6]’s improved version of Dolev’s algorithm. Our
new modifications apply to Bracha’s and Dolev’s protocols, and the cross-layer
combination of the two protocols.

Other approaches have assumed authenticated processes (i.e., processes can use
digital signatures) instead of authenticated communication channels [16].
Relying on cryptography provides integrity and authenticity properties that
simplify the algorithms. In particular, weaker connectivity is required to
solve the BRB problem. However, cryptography has a computational cost and
requires a trusted public key infrastructure (PKI). From a theoretical point
of view, cryptography-based approaches are limited to the case of
computationally bounded adversaries (e.g., that cannot generate hash
collisions). Also, having a trusted agent (TA) that is never Byzantine
trivializes the BRB problem (the sender can simply send its message to the TA,
and every correct node can then reliably collect it from there). By contrast,
we aim at solutions that can cope with computationally unbounded adversaries.

Recently, Contagion [17] replaced quorums by smaller stochastic samples, and
described an abstraction whose properties can be violated with a probability
that depends on the size of the samples. Differently, RT-ByzCast [18] and
PISTIS [19] aimed at providing real-time guarantees in probabilistically
synchronous and reliable networks. The idea of using pseudo-randomized message
dissemination has been used to tolerate malicious or selfish behaviors in
several works [20, 21], which however only provide probabilistic guarantees,
while we target exact deterministic guarantees.

##  III System Model and Problem Statement

Processes. We assume a set $\Pi=\\{p_{1},p_{2},\dots,p_{N}\\}$ of $N$
processes, uniquely identified by an ID, which are interconnected. We assume
that up to $f<\left\lfloor N/3\right\rfloor$ of the $N$ processes are
Byzantine, i.e., that they can behave arbitrarily or maliciously. Processes
know about the number $N$ of processes, the IDs of the processes in the
system, and the fault threshold $f$.

Communications. The processes are interconnected by a communication network,
which can be represented by an undirected graph $G=(V,E)$ where each node
represents a process $p_{i}\in\Pi$ (i.e., $V=\Pi$), and each edge represents a
communication channel. Two processes can directly communicate with each other
if and only if they are connected by an edge. Otherwise, processes have to
rely on others to relay their messages and communicate. Intermediary nodes
might be Byzantine, i.e., drop, modify or inject messages. We assume that
communication channels are authenticated, i.e., that messages received by a
node $p_{i}$ on the link interconnecting it with a node $p_{j}$ always come
from $p_{j}$. Communication channels can be synchronous or asynchronous, but
they are reliable, i.e., a message cannot be lost. We assume that the
communication network is at least $2f{+}1$ connected. Fig. 1 illustrates a
3-vertex-connected communication network. We assume that the network topology
is unknown to processes.

Figure 1: A reliable communication graph with $N=10$ and $f=1$.

We assume that processes broadcast payload data, which can be of variable
size, and that they might have to broadcast the same payload data at different
times during the system’s life. To do so, processes use a header that uniquely
identifies the payload data and contains control information.

Byzantine Reliable Broadcast. We consider the following Byzantine Reliable
Broadcast (BRB) abstraction. Its interface is as follows: nodes initiate
broadcasts using Broadcast events, while a Deliver event indicates that a
message has been delivered by a node. Moreover, this abstraction guarantees
the following properties:

[BRB-Validity] If a correct process $p$ broadcasts $m$, then some correct
process eventually delivers $m$.

[BRB-No duplication] No correct process delivers message $m$ more than once.

[BRB-Integrity] If a correct process delivers a message $m$ with correct
sender $p_{i}$, then $m$ was previously broadcast by $p_{i}$.

[BRB-Agreement] If some correct process delivers $m$, then every correct
process eventually delivers $m$.

Reliable Communication. In addition to the BRB abstraction, we also consider
the weaker Reliable Communication (RC) abstraction, which has the same
interface as BRB, and guarantees the same properties, except BRB-Agreement,
which is only guaranteed when the sender is correct.

##  IV Background: BRB on asynchronous and Partially Connected Networks

In this section we first recall Bracha’s and Dolev’s algorithms and we then
present how they can be used to provide BRB in asynchronous partially
connected networks.

###  IV-A Bracha’s Algorithm for BRB in Asynchronous and Fully Connected
Networks

Bracha’s algorithm (sometimes called _authenticated double-echo broadcast_)
describes the first BRB protocol for asynchronous and authenticated
communication networks [3]. Let us recall that this protocol assumes a fully
connected network made of reliable and authenticated point-to-point links and
it tolerates up to $f$ Byzantine processes (where $f<N/3$ and $N$ is the
number of processes in the network).

The protocol works in three phases. When a process $p_{i}$ wants to BRB-
broadcast some payload data, it sends a SEND message along with the payload
data to all nodes in the system (phase 1). Upon receiving a SEND message, a
process sends an ECHO message to all the nodes in the system (along with the
payload data) and moves to phase 2 where it remains waiting for a quorum of
ECHO messages. Upon receiving $\left\lceil\frac{N+f+1}{2}\right\rceil$ ECHO
messages for a given payload, a process sends a READY message to other nodes
and moves to phase 3. Let us note that a READY message can also be sent upon
receiving $f{+}1$ READY messages as it will ensure that al least one correct
process is moving to phase 3 and thus it is safe to broadcast a READY message
and to move to phase 3 as well. Finally, upon receiving $2f{+}1$ READY
messages, a process can BRB-deliver the payload data by concluding the
procedure.

For the sake of completeness, we report in Algo. 1 the pseudo-code of the
algorithm.444We extract, and refer the reader to the pseudo-code from [22] and
[23].

Algorithm 1 BRB in asynchronous and fully connected networks (Bracha’s
protocol) at process $p_{i}$

1:Parameters:

2: $\Pi$: the set of all processes.

3: $N$: total number of processes.

4: $f<N/3$: maximum number of Byzantine processes.

5:Uses: Auth. async. perfect point-to-point links, instance al.

6:

7:upon event $\langle Bracha,\texttt{Init}\rangle$ do

8: $sentEcho=sentReady=delivered=\textbf{False}$

9: $echos=readys=\emptyset$

10:

11:upon event $\langle Bracha,\texttt{Broadcast}\ |\ m\rangle$ do

12: forall $q\in\Pi$ do $\\{$ trigger $\langle al,\texttt{Send}\ |\
q,[\texttt{SEND},m]\rangle$ $\\}$

13:

14:upon event $\langle al,\texttt{Deliver}\ |\ p,[\texttt{SEND},m]\rangle$ and
not $sentEcho$ do

15: $sentEcho=\textbf{True}$

16: forall $q\in\Pi$ do $\\{$ trigger $\langle al,\texttt{Send}\ |\
q,[\texttt{ECHO},m]\rangle$ $\\}$

17:

18:upon event $\langle al,\texttt{Deliver}\ |\ p,[\texttt{ECHO},m]\rangle$ do

19: $echos.\texttt{insert}(p)$

20:

21:upon event
$echos.\texttt{size}()\geq\left\lceil\frac{N+f+1}{2}\right\rceil$ and not
$sentReady$ do

22: $sentReady=\textbf{True}$

23: forall $q\in\Pi$ do $\\{$ trigger $\langle al,Send\ |\
q,[\texttt{READY},m]\rangle$ $\\}$

24:

25:upon event $\langle al,\texttt{Deliver}\ |\ p,[\texttt{READY},m]\rangle$ do

26: $readys.\texttt{insert}(p)$

27:

28:upon event $readys.\texttt{size}()\geq f+1$ and not $sentReady$ do

29: $sentReady=\textbf{True}$

30: forall $q\in\Pi$ do $\\{$ trigger $\langle al,\texttt{Send}\ |\
q,[\texttt{READY},m]\rangle$ $\\}$

31:

32:upon event $readys.\texttt{size}()\geq 2f+1$ and not $delivered$ do

33: $delivered=\textbf{True}$

34: trigger $\langle Bracha,\texttt{Deliver}\ |\ s,m\rangle$

###  IV-B Dolev’s Algorithm for Reliable Communication in
($2f\\!+\\!1$)-Connected Networks

Dolev’s protocol provides reliable communication if processes are
interconnected by reliable and authenticated communication channels, and if
the communication network is at least $(2f+1)$-connected [4].

Dolev’s protocol leverages the authenticated channels to collect the labels of
processes traversed by a content. Processes use those labels to compute the
maximum number of node-disjoint paths among all the paths received for a
particular content. A process delivers a content as soon as it has verified
its authenticity, i.e., as soon as it has received the content through at
least $f{+}1$ node-disjoint paths. The keystone of Dolev’s proof is that by
Menger’s theorem, if the communication network is $(2f{+}1)$-connected then
there are at least $2f{+}1$ node-disjoint paths between any two processes in
the network [24], and since at most $f$ processes are faulty, according to the
pigeonhole principle, a process will receive a message sent by another process
through at least $f{+}1$ disjoint paths.

Depending on whether the processes know the network topology or not, Dolev
presented two variants of its protocol, which respectively use predefined
routes between processes, or flooding. We focus on the unknown topology
version of Dolev’s algorithm, whose pseudo-code is presented in Algo. 2.

Dolev’s algorithm made practical. Let us note that the worst case complexity
of Dolev’s algorithm is high (both in terms of number of messages and
complexity to verify if a specific content can be safely delivered). Bonomi et
al. presented several modifications that reduce the number of messages
transmitted along with their size [6] in practical executions555Let us stress
that the proposed modifications do not improve the worst case theoretical
complexity of the protocol, but the authors showed, through experimental
evaluations, that in several practical settings, the performance gain is
significant.. We recall these modifications in the following.

[MD.1] If a process $p$ receives a content directly from the source $s$, then
$p$ directly delivers it.

[MD.2] If a process $p$ has delivered a content, then it can discard all the
related paths and relay the content only with an empty path to all of its
neighbors.

[MD.3] A process $p$ relays path related to a content only to the neighbors
that have not delivered it.

[MD.4] If a process $p$ receives a content with an empty path from a neighbor
$q$, then $p$ can abstain from relaying and analyzing any further path related
to the content that contains the label of $q$.

[MD.5] A process $p$ stops relaying further paths related to a content after
it has been delivered and the empty path has been forwarded.

Algorithm 2 Reliable communication in $(2f\\!+\\!1)$-connected networks
(Dolev’s protocol) at process $p_{i}$

1:Parameters:

2: $f$ : max. number of Byzantine processes in the system.

3:Uses: Auth. async. perfect point-to-point links, instance al.

4:

5:upon event $\langle Dolev,\texttt{Init}\rangle$ do

6: $delivered=\textbf{False}$

7: $paths=\emptyset$

8:

9:upon event $\langle Dolev,\texttt{Broadcast}\ |\ m\rangle$ do

10: forall $p_{j}\in\texttt{neighbors}(p_{i})$ do

11: trigger $\langle al,\texttt{Send}\ |\ p_{j},[m,[\ ]]\rangle$

12: $delivered=\textbf{True}$

13: trigger $\langle Dolev,\texttt{Deliver}\ |\ m\rangle$

14:

15:upon event $\langle al,\texttt{Deliver}\ |\ p_{j},[m,path]\rangle$ do

16: $paths.\texttt{insert}(path+[p_{j}])$

17: forall $p_{k}\in\texttt{neighbors}(p_{i})\setminus(path\cup\\{p_{j}\\})$
do

18: trigger $\langle al,\texttt{Send}\ |\ p_{k},[m,path+[p_{j}]]\rangle$

19:

20:upon event ($p_{i}$ is connected to the source through $f+1$ node-disjoint
paths contained in $paths$) and $delivered=\texttt{False}$ do

21: trigger $\langle Dolev,\texttt{Deliver}\ |\ m\rangle$

22: $delivered=\textbf{True}$

###  IV-C BRB in ($2f+1$)-connected networks

The state-of-the-art method to implement the BRB abstraction in a partially
connected network consists in combining Bracha’s algorithm with a second
algorithm that is in charge of providing the abstraction of a reliable point-
to-point link (i.e., with a protocol ensuring Reliable Communications on
generic networks). For that purpose, one can either use Dolev’s algorithm,
CPA, or even topology specific protocols [25], depending on the assumptions
one is willing to make regarding the communication network. In the global
fault model and without additional network assumptions, one has to rely on
Dolev’s algorithm. The combination of Bracha’s and Dolev’s algorithms has
recently been used to design a randomized Byzantine agreement protocol on
partially connected networks [5].

In practice, Bracha’s and Dolev’s protocols can be combined by replacing each
send-to-all operation at process $p_{i}$ (i.e, forall $q\\!\in\\!\Pi$ do
$\\{\textbf{trigger}\langle al,\texttt{Send}\,|\,q,[mType,m]\rangle\\}$) in
Algo. 1 (lns. 12, 16, 23, 30) by a $\langle
Dolev,\texttt{Broadcast}\,|\,[mType,m]\rangle$ operation, where
$mType\\!\in\\!\\{\texttt{SEND},\texttt{ECHO},\texttt{READY}\\}$. In addition,
one has to replace
$\langle\mathit{al},\texttt{Deliver}\mid{q},[msgType,m]\rangle$ in Algo. 1
(lns. 14, 18, 25) by
$\langle\mathit{Dolev},\texttt{Deliver}\mid[msgType,m]\rangle$, where $q$ is
the source of the $f{+}1$ disjoint paths identified to trigger a Dolev-deliver
in Algo. 2, ln. 20. The resulting protocol stack is illustrated in Fig. 2,
which also shows the interface of each module. This combination can be made
more practical by applying modifications MD.1–5. However, given that the
number of messages generated by Bracha’s and Dolev’s protocols are
respectively $\mathcal{O}(N^{2})$ and $\mathcal{O}(N!)$, and that Dolev’s
algorithm requires solving a problem with exponential complexity (i.e.,
finding disjoint paths in a unknown network), the combination of these two
protocols does not scale well with the number of processes.

Figure 2: Composition of Bracha’s and Dolev’s algorithms to implement BRB on
partially connected networks.

##  V Cross-layer Bracha-Dolev Implementation and Functional Modifications

In the following, we describe how Bracha’s and Dolev’s protocols can be
combined and leverage modifications MD.1-5.

Protocol stack and interfaces. Fig. 3 illustrates the interface of our
combination of Bracha’s and Dolev’s protocols, modified to support
modifications MD.1–5 and repeatable broadcasts. We detail below the fields
used in this interface, and Sec. VI-C shows how some of those fields can be
made optional.

Repeatable broadcast. Across the system’s life, we assume that a process might
broadcast several times the same payload data. For example, this would be
required for sensing applications (e.g., temperature monitoring). We then
assume that a broadcast message contains the payload data $m$, the ID of its
source process $s$, and a broadcast ID $bid$ (a sequence number) that the
source process monotonically increases after each broadcast. If the source is
correct, the source and broadcast IDs of a broadcast message uniquely identify
a payload data. A Byzantine process might reuse a broadcast ID for several
payload data, in which case all processes will agree on delivering at most one
payload and ignore the others.

We therefore modify the interface of the BRB protocol so that Broadcast and
Deliver operations include the $s$ and $bid$ fields:
$\langle\mathit{BD},\texttt{Broadcast}\,|\,[(s,bid),m]\rangle$ and
$\langle\mathit{BD},\texttt{Deliver}\,|\,[(s,bid),m]\rangle$. This
modification limits the Byzantine processes’ ability to replay messages. Each
process maintains a transmission graph for each message it receives that is
uniquely identified by the broadcasting process ID, the broadcast ID, the
message type, the sending process ID and the payload (which is necessary to
handle Byzantine senders).

Applying modifications MD.1–5. For MD.1–5 to be used in the combination of
Bracha’s and Dolev’s algorithms, the format of the ECHO and READY messages has
to be slightly modified to contain the ID of their original sender, so that
ECHO or READY messages that are broadcast by different processes can be
distinguished. Using the original specification of Dolev’s protocol, one could
rely on the full paths received along with messages to identify the sender of
an ECHO or READY message. However, optimization MD.2 of Dolev’s protocol
replaces a path by an empty path upon delivery of a message, which then
prevents the identification of the original sender of the message from its
path. For this reason, ECHO and READY messages must contain an additional
field that identifies their sender. For example, an ECHO message generated by
process $p_{i}$ would then have the format
$[\texttt{ECHO},p_{i},(s,bid),m,path]$.

In the following, to avoid repetitions, we will use BD to refer to the Bracha-
Dolev protocol combination; BDopt to refer to the version of BD optimized with
the modifications MD.1–5; and name our novel modifications MBD.1–12.

Figure 3: Interfaces in a cross-layer combination of Bracha’s and Dolev’s
protocols to implement BRB on partially connected networks.

##  VI Optimizing for Latency

###  VI-A Limiting payload transmissions

Bracha’s and Dolev’s protocols make processes include the payload data (i.e.,
the content they wish to broadcast) in each message sent to their neighbors.
However, when the payload data is large, and because of the large number of
messages generated, it is worthwhile to reduce the number of times the payload
data is exchanged. Some Byzantine-resilient protocols replace the payload by
hashes or signatures for this purpose. These methods could be used in the
Bracha-Dolev combination too. However, we aim at avoiding the use of
cryptographic methods to contain the computational overhead of the protocol
but also to tolerate computationally unbounded adversaries.

Modification [MBD.1] We modify the protocol as follows. Upon receiving a
message that contains a previously unknown payload data, a process $p_{i}$
associates it to a unique local ID. Note that simply replacing a payload data
by its source ID and sequence number would not allow this modification in
asynchronous settings, because Byzantine processes might send several payloads
with the same sequence number and because messages might be reordered during
their transmission, which would threaten the BRB-Agreement property. When
sending a message to its neighbors related to this payload data for the first
time, the process then includes the local ID it chooses. In later messages,
$p_{i}$ only sends the local ID of that payload data. A neighbor of $p_{i}$,
say $p_{j}$, might generate its own local ID for a given payload before
receiving $p_{i}$’s local ID. This is not a problem, and $p_{i}$ can either
use its local ID or the one received from $p_{j}$ to interact with $p_{j}$.

Because of the asynchrony of communications, a process might actually receive
the message that contains the payload data after subsequent messages that only
use the local ID. In that case, we modified the protocol so that a process
stores the messages that mention an unknown payload in a queue, before
processing them all when the payload data is finally received.

In the worst case, our method requires a process to receive a given payload
data once from each of its neighbors. In practice, the size of local IDs
should be decided in an ad-hoc manner so that a process does not run out of
available IDs.

###  VI-B Bracha phase transitions

Processes receive and forward Send, Echo and Ready messages that have been
created according to Bracha’s protocol, following a dissemination that Dolev’s
protocol determines. In the following, we describe several modifications that
processes can implement when they create messages, following the reception of
a message that has been delivered using Dolev’s algorithm. These modifications
reduce the total number of messages exchanged, and the overall bandwidth
consumption.

Echo and Ready amplifications. In Bracha’s protocol, it is known (and
necessary) that the reception of $f+1$ Readys in Bracha’s protocol allows a
process to generate its own ready message, if it has not done so already [22,
23]. This situation can happen in Bracha’s protocol because the links are
asynchronous. However, we also observe that the delivery of $f+1$ Echos allows
a process to generate its own Echo message, and send it if it was not sent
before because the original Send message has not yet been delivered. Our
modification MBD.2 of Send messages into single-hop messages makes this
amplifications of Echos necessary.

Single-hop Send messages [MBD.2]. In the default combination of Bracha’s and
Dolev’s protocols, the Send messages that a correct process creates reach all
the processes. We modify the protocol so that upon receiving a Send message, a
neighbor of the source stops disseminating it, and creates instead an Echo
message that it relays to all its neighbors. When a process $p_{i}$ Dolev-
delivers a $[\texttt{SEND},(s,bid),m,path]$ message that it received from a
neighbor $p_{j}$, the combination of Bracha’s and Dolev’s algorithms makes it
forward a modified Send message to its neighbors not included in $path$, i.e.,
$[\texttt{SEND},(s,bid),m,path{+}[p_{j}]]$. A process can avoid generating and
forwarding the modified Send message without loss of information. A Send
message is therefore a single-hop message and does not need to carry a $path$.

  * Proof.

Bonomi et al. proved that upon Dolev-delivery of a message
$[\texttt{SEND},(s,bid),m,path]$ a process $p_{i}$ can send a
$[\texttt{SEND},(s,bid),m,[\,]\,]$ message instead of the
$[\texttt{SEND},(s,bid),m,path\\!+\\![p_{j}]\,]$ message to its neighbors not
included in $path$ (MD.2 in Sec. IV-B). This modification decreases the size
of the forwarded Send message. Following Bracha’s algorithm, after having
validated a Send message, process $p_{i}$ should also send an
$[\texttt{ECHO},p_{i},(s,bid),m,[\,]\,]$ message to all its neighbors.
However, upon receiving an $[\texttt{ECHO},p_{i},(s,bid),m,path]$ message,
processes can extract the $[\texttt{SEND},(s,bid),m,path]$ message they should
have received in the unmodified protocol and process it.

Echo to Echo transitions [MBD.3]. When a process $p_{i}$ receives an
$[\texttt{ECHO},p_{k},(s,bid),m,path]$ from a neighbor $p_{j}$ that makes
$p_{i}$ Dolev-deliver the message, according to Dolev’s protocol and MD.2,
$p_{i}$ forwards $[\texttt{ECHO},p_{j},(s,bid),m,[\,]\,]$ to its neighbors not
included in $\mathit{path}$. As a result of delivering the Echo message,
process $p_{i}$ might also send an $[\texttt{ECHO},p_{i},(s,bid),m,[\,]\,]$
message to all its neighbors (after having delivered the Send message of the
source, or received $f+1$ Echos - using the Echo amplification).

These two messages can be merged into a single one, in particular because they
both have to be transmitted using empty paths (the first one because it was
delivered, due to MD.2, and the second one because it has just been created).
For that purpose, we introduce a new message type Echo_Echo formatted as
$[\texttt{ECHO\\_ECHO},p_{i},p_{j},(s,bid),m,path]$, where $p_{i}$ is the ID
of the process whose Echo message was received, while $p_{j}$ is the ID of the
process whose Echo was delivered by $p_{i}$ and triggered the emission of the
Echo message by $p_{i}$. We explain below how these messages are handled.

Finally, a process $p_{i}$ can decide to which neighbors it should send the
Echo_Echo message, and to which it should only send its own Echo message (cf.
MD.3, IV-B): (i) $[\texttt{ECHO\\_ECHO},p_{i},p_{j},(s,bid),m,[\,]\,]$ is sent
to the neighbors that have not yet Dolev-delivered
$[\texttt{ECHO},p_{j},(s,bid),m]$ and are not included in the received path;
and (ii) $[\texttt{ECHO},p_{i},(s,bid),m,[\,]\,]$ is sent to the remaining
neighbors.

  * Proof.

Upon receiving an $[\texttt{ECHO\\_ECHO},p_{i},p_{j},$ $(s,bid),m,[\,]\,]$
message, a process can extract $[\texttt{ECHO},p_{j},(s,bid),m,[\,]\,]$ and
$[\texttt{ECHO},p_{i},(s,bid),m,[\,]\,]$ messages. It is correct for $p_{i}$
to forward the Echo message with an empty path (MD.2, IV-B). In addition,
$p_{i}$ does not have to forward the $[\texttt{ECHO},p_{j},(s,bid),m,[\,]\,]$
message to its neighbors that have delivered the
$[\texttt{ECHO},p_{j},(s,bid),m]$ message (MD.3, IV-B), which justifies the
use of an Echo message instead of an Echo_Echo message.

Echo to Ready transitions [MBD.4]. When a process $p_{i}$ Dolev-delivers an
$[\texttt{ECHO},p_{j},(s,bid),m,path]$ message that it received from a
neighbor $p_{k}$, the standard Bracha-Dolev protocol combination makes $p_{i}$
forward a modified Echo message to its neighbors not included in $path$, i.e.,
$[\texttt{ECHO},p_{j},(s,bid),m,path\\!+\\![p_{k}]\,]$, while MD.2 makes
$p_{i}$ forward an empty path to those neighbors. As a result of delivering
the Echo message, process $p_{i}$ might also send a
$[\texttt{READY},p_{i},(s,bid),m,[\,]\,]$ message to all its neighbors (after
having Dolev-delivered $2f+1$ Echo messages).

We introduce a second novel message type Ready_Echo associated to messages of
the format $[\texttt{READY\\_ECHO},p_{i},p_{j},(s,bid),m,path]$, where $p_{i}$
is the ID of the process whose Ready was received, while $p_{j}$ is the ID of
the process whose Echo was delivered by $p_{i}$ and triggered the emission of
the Ready message by $p_{i}$. The $path$ field of a Ready_Echo message
describes an empty path upon creation, but this is not the case if the message
is relayed. As for Echo_Echo messages, process $p_{i}$ decides whether to send
a Ready_Echo, Ready, Echo, or no message at all for each of its neighbors
depending on whether or not it has transmitted an empty path for the Echo or
the Ready.

  * Proof.

Upon receiving a $[\texttt{READY\\_ECHO},p_{i},p_{j},$ $(s,bid),m,[\,]\,]$
message, a process can extract $[\texttt{ECHO},p_{j},(s,bid),m,[\,]\,]$ and
$[\texttt{READY},p_{i},(s,bid),m,[\,]\,]$ messages. It is correct for $p_{i}$
to forward the Echo message with an empty path (MD.2, IV-B). In addition,
$p_{i}$ does not have to forward the $[\texttt{ECHO},p_{j},(s,bid),m,[\,]\,]$
message to its neighbors that have delivered the
$[\texttt{ECHO},p_{j},(s,bid),m]$ message (MD.3, IV-B), which justifies the
use of a Ready message instead of a Ready_Echo message for those neighbors.

Algorithm 3 READY_ECHO message reception at process $p_{i}$

1:upon event $\langle$ $al$, Deliver | $p_{l}$, [READY_ECHO, $p_{r}$, $p_{e}$, (s, bid), m, path] $\rangle$ do

2: insert $path\\!+\\![p_{l}]$ in $[\texttt{ECHO},p_{e},(s,bid)]$’s graph

3: insert $path\\!+\\![p_{l},p_{e}]$ in $[\texttt{READY},p_{r},(s,bid)]$’s
graph

4:

5: // $\texttt{Dolev-delivered}(\mathit{msg})$ checks whether $\mathit{msg}$
has already been

6: // Dolev-delivered prior to this event (MD.5)

7: $sendEcho\\!=\,!\texttt{Dolev-delivered}([\texttt{ECHO},p_{e},(s,bid)])$

8: $sendReady\\!=\,!\texttt{Dolev-delivered}([\texttt{READY},p_{r},(s,bid)])$

9:

10: // actOnEchos and actOnReadys create and send Echo/Ready

11: // messages if necessary, according to Bracha’s algorithm

12: // $\texttt{Dolev-delivering}(\mathit{msg})$ checks whether $\mathit{msg}$
is being

13: // Dolev-delivered at this event (MD.2)

14: ($\texttt{Dolev-delivering}([\texttt{ECHO},p_{e},(s,bid)]))?$
$\\{\texttt{actOnEchos}(s,bid,p_{e});$ $epath\\!=\\![\,]\\}:$
$epath\\!=\\!path\\!+\\![p_{l}]$

15: ($\texttt{Dolev-delivering}([\texttt{READY},p_{r},(s,bid)]))?$
$\\{\texttt{actOnReadys}(s,bid,p_{r});$ $rpath\\!=\\![\,]\\}:$
$rpath\\!=\\!path\\!+\\![p_{l}]$

16:

17: // Avoiding the neighbors that sent empty paths (MD.3)

18: $NDE=\texttt{neighborsThatDelivered}([\texttt{ECHO},p_{e},(s,bid)])$

19: $NDR=\texttt{neighborsThatDelivered}([\texttt{READY},p_{r},(s,bid)])$

20:

21: if $sendEcho$ and $!sendReady$ then

22: forall
$x\in\texttt{neighbors}(p_{i})\setminus(NDE\\!\cup\\!path\\!\cup\\!\\{p_{l}\\})$

23: trigger
$\langle{al},\texttt{Send}\mid{x},[\texttt{ECHO},p_{e},(s,bid),m,epath])\rangle$

24: else if $!sendEcho$ and $sendReady$ then

25: forall
$x\in\texttt{neighbors}(p_{i})\setminus(NDR\\!\cup\\!path\\!\cup\\!\\{p_{l}\\})$

26: trigger
$\langle{al},\texttt{Send}\mid{x},[\texttt{READY},p_{r},(s,bid),m,rpath])\rangle$

27: else

28: forall $x\in NDR\setminus(NDE\\!\cup\\!path\\!\cup\\!\\{p_{l}\\})$

29: trigger
$\langle{al},\texttt{Send}\mid{x},[\texttt{ECHO},p_{r},(s,bid),m,rpath])\rangle$

30: forall $x\in NDE\setminus(NDR\\!\cup\\!path\\!\cup\\!\\{p_{l}\\})$

31: trigger
$\langle{al},\texttt{Send}\mid{x},[\texttt{READY},p_{r},(s,bid),m,rpath])\rangle$

32: forall $x\in
neighbors(p_{i})\setminus(NDE\\!\cup\\!NDR\\!\cup\\!path\\!\cup\\!\\{p_{l}\\})$

33: if $epath==rpath$ then

34:
$\textbf{trigger}\,\langle{al},\,\texttt{Send}\,|\,x,\\![\texttt{READY\\_ECHO},\\!$
$p_{e},\\!$ $p_{r},\\!$ $(s,bid),\\!m,\\!epath]\rangle$

35: else

36:
$\textbf{trigger}\,\langle{al},\texttt{Send}\mid{x},[\texttt{ECHO},p_{e},(s,bid),m,epath]\rangle$

37:
$\textbf{trigger}\,\langle{al},\\!\texttt{Send}\mid{x},[\texttt{READY},p_{r},(s,\\!bid),m,rpath]\rangle$

38: end if

39: end if

40:

Reception of Echo_Echo and Ready_Echo messages. We detail here how processes
handle Ready_Echo messages (Echo_Echos are handled similarly). Upon receiving
a $[\texttt{READY\\_ECHO},p_{i},p_{j},(s,bid),m,path]$ message, we have seen
that processes can extract $[\texttt{ECHO},p_{j},(s,bid),m,path]$ and
$[\texttt{READY},p_{i},(s,bid),m,path]$ messages. However, it might not always
be necessary for processes to forward the Ready_Echo message to their
neighbors, as a Dolev dissemination would dictate. Indeed, some of these
neighbors might have already delivered the Echo or the Ready message (MD.3,
IV-B), or neighbors that have delivered can be included in the received path
(MD.4, IV-B). Algo. 3 provides the pseudocode that processes use to handle the
Ready_Echo messages they receive.

Empirical lessons. We observed that the system’s latency is lower when
processes first forward a message they have received before sending the
message they might have created. In addition, one might also remark that we
have not mentioned the possibility for a received Ready message to trigger the
emission of a Ready message, which might be exploited to create a Ready_Ready
message. Similarly, one could say that receiving an Echo_Echo message might
trigger the emission of an Echo message, which would justify the need to
create a message type that would carry three Echos. In practice, we have not
observed that these phenomena appeared sufficiently often to justify this
implementation.

###  VI-C Optimized messages [MBD.5]

So far, we have assumed that messages in the Bracha-Dolev protocol combination
contain, besides the payload data, a payload ID $(s,bid)$, a message type
$mType\in\\{\texttt{SEND},\texttt{ECHO},\texttt{READY}\\}$, the ID of the
process that generated the message, and a list of process IDs to indicate the
path the message followed in the topology. We now detail several observations
that allow these messages to be more concisely transmitted without loss of
information.

Send messages. As we have seen in the previous section, Send messages are
single-hop messages. Therefore, they do not have to carry the source ID in the
payload’s ID $(s,bid)$, because communication links are authenticated. Send
messages also always carry the payload data along with the local ID that was
chosen by the source. Send messages therefore have the following format:
$[\texttt{SEND},bid,\mathit{localPayloadID},\mathit{payloadSize},\mathit{payload}]$.

Optional fields. We now consider the other types of message we have mentioned:
Echo, Ready, Echo_Echo, and Echo_Ready. A process receives a message in a
buffer, and decodes the information it encloses according to a header that
contains the message type, and several bits that indicate the fields to be
read in the message.

First, messages might contain or not the payload data, which is indicated by a
bit $\mathit{payloadBit}$. If $\mathit{payloadBit}$ is set, a process expects
to read the ID of the payload data $(s,bid)$, the local ID selected by the
sending process $\mathit{localPayloadID}$, and the payload data. If
$\mathit{payloadBit}$ is not set, a process only expects to read
$\mathit{localPayloadID}$.

Second, the ID of the source that generates a message is originally included
in the path of a message, and therefore does not always have to be transmitted
in a message. However, when processes replace a propagation path by an empty
path (using MD.2), this is not the case anymore, and processes therefore
restore the sender field in their message. To handle both situations, we add a
bit $\mathit{senderBit}$ that indicates whether the sender ID is included in
the message.

Finally, if the creator of the message is not the neighbor from which it is
received (indicated by the authenticated link), a message contains a path,
which is decoded using a $\mathit{pathLen}$ field that indicates the number of
process IDs to be read, followed by a list $path$ that contains the process
IDs.

For example, an Echo message can have the following format
$[\texttt{ECHO},\mathit{payloadBit}{=}1,$ $\mathit{senderId}{=}1,$ $(s,bid),$
$\mathit{echoSenderID},$
$\mathit{localPayloadID},\mathit{payloadSize},\mathit{payload},\mathit{pathLen},path]$
at most once between any pair of processes for a given sender. In a more
positive situation, an Echo message can be transmitted as
$[\texttt{ECHO},\mathit{payloadBit}{=}0,\mathit{senderId}{=}0,\mathit{localPayloadID}]$,
which happens every time a process generates its own Echo.

##  VII Optimizing for Throughput

###  VII-A Handling asynchrony

We present several optimizations that can be implemented when the Bracha part
of the protocol generates novel messages while the Dolev propagation of a
received message has to continue. These optimizations reduce the overall
amount of information exchanged over the network. Ignore Echos received after
Dolev-delivering the corresponding Ready [MBD.6]. If a process $p_{i}$ Dolev-
delivers a Ready message that was sent by a process $p_{j}$ then $p_{i}$ can
stop disseminating and discard any Echo message emitted by $p_{j}$.

  * Proof.

If $p_{i}$ Dolev-delivered the Ready message of a process $p_{j}$, it means
that $p_{i}$ verified that $p_{j}$ did send the Ready message. The Echo
message that $p_{j}$ sent contains less information and reflects an old state
of $p_{j}$.

Ignore Echos received after delivering the content [MBD.7]. If a process
$p_{i}$ Bracha-delivers a content (because it has Dolev-delivered $2f{+}1$
Readys), then it can stop disseminating and discard all Echo messages it might
receive that are related to this content.

  * Proof.

If $p_{i}$ Bracha-delivered a message, then $p_{i}$ has Dolev-delivered Ready
messages from $2f{+}1$ distinct processes and at least $2f{+}1$ processes are
reliably exchanging the related Ready messages. Thus, all processes will
eventually Bracha-deliver the message and the Echo message is not needed.

Receiving Readys before transmitting Echos [MBD.8]. If a node $p_{i}$ has
Dolev-delivered the Ready message of its neighbor $p_{j}$, it can avoid
sending any future Echo message it receives to $p_{j}$. Note that this happens
as soon as $p_{j}$’s Ready is received, since it is transmitted with an empty
path and therefore immediately delivered.

  * Proof.

If $p_{j}$ is faulty, whether or not it transmits a message to $p_{j}$ will
not impact the protocol’s guarantees. If $p_{j}$ is correct, it has Dolev-
delivered $\lceil\frac{N+f+1}{2}\rceil$ Echos, or $f{+}1$ Readys, before
sending its Ready, and each of these Echos or Readys have been forwarded with
empty paths. These messages will eventually be Dolev-delivered by all
processes.

Avoiding neighbors that delivered [MBD.9]. If a node $p_{i}$ has received
$2f{+}1$ Readys (generated by $2f{+}1$ different processes) with empty paths
that are related to the same content from a neighbor $p_{j}$, then $p_{i}$ can
avoid sending any message related to that content to $p_{j}$ in the future.

  * Proof.

If $p_{j}$ is correct it sent $2f{+}1$ Readys with an empty path to all its
neighbors (MD.2). These neighbors will eventually receive these $2f{+}1$
Readys and be able to deliver independently from $p_{i}$’s message
transmissions through $p_{j}$. Again, if $p_{j}$ is faulty, it will not make a
difference for the protocol’s properties whether or not it receives messages
from $p_{i}$.

Ignore messages whose path is a superpath of a message previously received
[MBD.10]. If a node $p_{i}$ receives a message $m_{1}$ (e.g., an Echo from
process $p_{0}$) with path ${path}_{1}$, for which a previous message $m_{0}$
with ${path}_{0}$ was received (and which only differs from $m_{1}$ by its
path) and such that ${path}_{0}$ is a subpath of ${path}_{1}$, then $p_{i}$
can ignore $m_{1}$.

  * Proof.

The path ${path}_{1}$ does not help $p_{i}$ identify $2f{+}1$ disjoint paths
towards the source, because ${path}_{0}$ contains a subset of the processes
that are included in ${path}_{1}$. Similarly, it is not useful to forward the
received message with a modified path equal to ${path}_{1}\\!+\\![p_{i}]$,
because a subpath such as ${path}_{0}\\!+\\![p_{i}]$ or $[\ ]$ has already
been transmitted.

Upon receiving a message, a process checks whether a subpath has been
previously received, and if so discard the message, otherwise the received
path is saved. Processes represent paths using bit arrays, and store them in a
list. The observed performance impact of this method does not justify the use
of more efficient data structures.

###  VII-B Non-tight cases

We introduce several modifications that decrease the number of processes that
participate in various phases of the Bracha-Dolev protocol combination when
the number of processes in the network is larger than $3f+1$.

Reduced number of messages in Bracha [MBD.11]. To implement this method, we
assume that processes know the ID of all processes in the system. The
processes with the $\lceil\frac{N+f+1}{2}\rceil\\!+\\!f$ smallest IDs generate
Echos, while the processes with the $2f\\!+\\!1\\!+\\!f$ smallest IDs generate
Readys. The other processes simply relay the messages they receive. All
processes deliver when they have collected $2f\\!+\\!1$ Readys.

  * Proof.

To realize this, one has to reason starting from the end of Bracha’s protocol.
A process needs $2f+1$ Readys to deliver, therefore only $3f+1$ processes are
required to send a Ready, since there are at most $f$ faulty processes in the
system, and there are no message losses. To be able to send a Ready, a process
needs to receive $\lceil\frac{N+f+1}{2}\rceil$ Echos. Therefore,
$\lceil\frac{N+f+1}{2}\rceil\\!+\\!f$ processes are required to send an Echo.
Finally, the source needs to transmit its Send message to
$\lceil\frac{N+f+1}{2}\rceil+f$ processes. Note that when $N=3f+1$, the number
of processes that are chosen to participate in each phase is always equal to
$3f+1$, as indicated by Bracha’s protocol.

Send messages in Bracha-Dolev. [MBD.12] If the source has more than $2f{+}1$
neighbors, it can transmit its Send message to $2f{+}1$ of its neighbors,
instead of to all of them.

  * Proof.

If the source sends its Send message to $2f+1$ of its neighbors, it means that
at least $f+1$ correct neighbors will eventually receive the Send message.
These correct neighbors will then initiate a Dolev-broadcast of their Echo
message (cf. Send to Echo transition) to all other nodes in the system. Since
every pair of processes are connected through at least $2f+1$ disjoint paths,
every process in the system will eventually receive at least $f+1$ Echo
messages. Using the Echo amplification, each of these processes will then send
their own Echo, which means that every correct process will have delivered the
original Send message of the source.

Discussion. Those modifications decrease the number of exchanged messages
drastically. However, they also often increase the protocol’s latency. Indeed,
the processes selected to generate Echo/Ready messages might be located far
from each other in the network. Without these modifications all processes send
their Echo/Ready messages, which allows processes to collect the required
numbers of Echos/Readys faster.

##  VIII Performance evaluation

###  VIII-A Settings

We use the Omnet++ network simulator v.5.6.2 [26], which runs C++ code. We use
an Intel Xeon E5-4650 CPU (2.10GHz) machine. We evaluate the impact of
modifications MBD.1–12 on BDopt, the state-of-the-art combination of Bracha’s
algorithm with Dolev’s algorithm modified with Bonomi et al.’s improvements
[6].

TABLE I: Message fields. Msg field | Description | Size
---|---|---
$mtype$ | Message type | 4 bits
$s$ | ID of the source process | 32 bits
$bid$ | Message ID | 32 bits
$data\\_size$ | Payload data size in Bytes | 32 bits
$data$ | Payload data | 16B/16KB
${erId}_{1}$ | ECHO/READY sender ID | 32 bits
${erId}_{2}$ | Embedded ECHO/READY sender ID | 32 bits
$path_{s}ize$ | Path length (number of processes) | 16 bits
$path$ | List of process IDs | Variable

We vary the number $N$ of processes, the number $f$ of Byzantine processes,
and the network connectivity $k$, so that $N\geq 3f{+}1$ and $k\geq 2f{+}1$.
For each experiment with a $(N,k,f)$ tuple, we generate a regular random graph
[27] using the NetworkX Python library [28], and report the average of 5 runs.
The latency and throughput of each network link are set to 0.5ms and 1Mbps,
respectively. We measure the protocols’ latency as the time when all correct
processes have delivered the broadcast message. Note that further messages
might still be exchanged after this point. We consider payloads of 16B and
16KB, to represent small and large messages. We simulate the protocol
execution for a single broadcast message (i.e., only one process broadcasts a
message), and make all processes participate to maximize the bandwidth
consumption. Table I details the size of the message fields. In plots,
vertical bars indicate the minimum and maximum observed values.

###  VIII-B Impact of individual modifications

TABLE II: Impact of the modifications with random graphs and synchronous communications. | Small payload (16B) | Large payload (16KB)
---|---|---
MBD | Layer |  Lat. var. % |  Useful when |  # bits var. |  Useful when |  Lat. var. % |  Useful when |  # bits var. |  Useful when
1 | B |  $[-22,4.3]$ |  always |  $-63$ |  always |  $[-93,-78]$ |  always |  $-97$ |  always
2 | BD |  $[-21,62]$ |  large k |  $[-1.8,9]$ |  small f $\\!\lor\\!$ large k |  $[-15.4,107]$ |  large k |  $[-4.3,0.4]$ |  always
3 | BD |  $[-21,99]$ |  large k |  $[-1.8,12]$ |  large k |  $[-17,104]$ |  large k |  $[-4.3,0.4]$ |  large k
4 | BD |  $[-25,5]$ |  large k |  $[-1.4,19.7]$ |  f=1 $\lor$ large k |  $[-50,1.2]$ |  always |  $[-1.3,0.8]$ |  f=1 $\lor$ large k
5 | BD |  $[-5.3,9.4]$ |  small f and k |  $[15,19]$ |  never |  $[-4.1,4.5]$ |  small f and k |  $[-0.9,0]$ |  always
6 | B |  $[-5.3,1.6]$ |  - |  $[-9.6,0]$ |  always |  $[-4,4.5]$ |  - |  $[-0.9,0.13]$ |  always
7 | B |  $[-3,1.4]$ |  - |  $[-13.2,-1.4]$ |  always |  $[-2,5.4]$ |  - |  $[-5.8,0.07]$ |  always
8 | B |  $[-8.7,3.8]$ |  - |  $[-12.8,-3.1]$ |  always |  $[-3.6,2]$ |  - |  $[-4.9,0.07]$ |  always
9 | BD |  $[-5.7,3.0]$ |  - |  $[-43,0]$ |  always |  $[-3.9,1.9]$ |  - |  $[-38,0]$ |  always
10 | D |  $[-5.1,1.3]$ |  small f and k |  $[-1.9,0]$ |  always |  $[-4.2,6.2]$ |  small f and k |  $[-1.5,0]$ |  always
11 | B |  $[-25,149]$ |  small f $\\!\land\\!$ large k |  $[-66,-16]$ |  always |  $[-31,240]$ |  small f $\\!\land\\!$ large k |  $[-66,-16]$ |  always
12 | B |  $[-15,27]$ |  large k |  $[-2.7,2.6]$ |  small f and k |  $[-17,57]$ |  large k |  $[0.26,4.7]$ |  never

We evaluated the impact of each modification on BDopt’s latency and network
consumption with a large set of parameters. Table II summarizes the protocol
layer on which a modification is applied, and its impact on latency and
throughput for small and large payload sizes. We observed that one can decide
whether a modification should be used to improve either latency or the network
consumption based on the payload size and the network connectivity k. We
illustrate some modifications when $N=31$ and a 16KB payload. Fig. 4 shows
that MBD.4 almost always improves latency (from -50% to 1.2%), and is more
effective when k increases or f decreases. Figs. 5 and. 6 show MBD.11’s impact
on latency and on the network consumption, respectively. MBD.11 limits the
number of processes that generate Echo/Ready messages while the others only
relay messages. MBD.11 decreases the network consumption (-66% to -16%) but
also often increases latency (-31% to +240%). Larger payloads lead to larger
performance improvements.

Figure 4: MBD.4’s latency impact - $N=31$, 16KB payload. Figure 5: MBD.11’s
latency impact - $N=31$, 16KB payload. Figure 6: MBD.11’s bandwidth
consumption impact - $N=31$, 16KB payload.

###  VIII-C CPU and memory consumption

We measured the total processing time per process during an experiment where
$N\\!=\\!31$, $f\\!=\\!4$ and a 16KB payload. This time decreases when the
network connectivity increases for all combinations of modifications from 6s
to 0.5s. Processing times cannot be directly associated with the protocol’s
latency. First, because processes continue to treat messages after they have
delivered a content. And second, because Omnet++ does not advance the
simulation time when messages are processed. Compared to real deployments this
effect would create differences only when several messages are simultaneously
received. We partially compensate it so that, at creation time, messages are
delayed by a time that corresponds to the processing time of the message that
triggered their emission. Latencies measured in a real-deployment would
probably be slightly higher than those we observed. However, the effect of our
modifications on latency and bandwidth would be the same since the processing
times were not significantly impacted by our modifications. The modifications
have a very small impact on memory usage, since the most costly ones require
storing a boolean per process.

###  VIII-D Latency vs. Network Consumption

Based on the observed impact of our modifications, we compare the latency and
network consumption improvements of three combinations of modifications to
BDopt that respectively contain: (i) lat.: only the modifications that
decrease latency; (ii) bdw.: only the modifications that decrease bandwidth
consumption; and (iii) lat. & bdw.: only the modifications that decrease both
latency and bandwidth consumption. Figs. 7 and 8 respectively show the latency
decrease and the network consumption of these configurations with
$(N,f)\\!=\\!(31,4)$ and a 16B payload. Configurations lat. and lat. & bdw.
always decrease latency (from -25% to 0%), while bdw. almost always increase
it (up to 130%), because of MBD.11. However, bdw. decreases the network
consumption the most (from 25 to around 12KB in average, i.e., around -50%),
while lat. and lat. & bdw. have a similar impact (from 25 to around 20KB in
average, i.e., -20%). These results show that there is no single best
configuration to optimize both latency and network consumption. In the same
settings with 16KB payload, the latency is decreased between -93% and -83%,
while the bandwidth consumption is decreased by -99.4% to -97%.

Figure 7: Latency impact of the configurations - $(N,f)\\!=\\!(31,4)$, 16B
payload. Figure 8: Bandwidth consumption per configuration -
$(N,f)\\!=\\!(31,4)$, 16B payload.

###  VIII-E Evolution with the number of processes

In this experiment, we considered graphs that include 25, 31, 40, and 73
processes. We chose the average possible $f$ value for each $N$ value.
Simulating systems with larger $N$ values is challenging because of the
exponential number of messages, memory and computing time that processes
require to execute the Bracha-Dolev protocol combination. Figs. 9 and 10
respectively show the bandwidth and latency improvement of the lat. and bdw.
configurations over BDopt with a 16B payload. We omit configuration lat. &
bdw. in those figures for clarity. As one can see, configurations bdw. and
lat. improve the bandwidth consumption respectively by -80% to -70%, and by
-63% to -38%. Configuration lat. also improves the latency (-50% to +2%).
However, bdw. increases the latency by up to 400% when k is small, which goes
out of the plot, but otherwise also manages to improve latency down to -40%.
Latency and network consumption improvements are even higher with the larger
16KB payload (resp. at least -97.6% and -97.3%).

Figure 9: Bandwidth consumption improvement over BDopt - 16B payload. Figure
10: Latency improvement over BDopt - 16B payload.

###  VIII-F Asynchronous networks

In addition to the above experiments, we also performed experiments with links
whose transmission delays were computed per message using a normal
distribution centered around 5ms with a standard deviation of 20ms truncated
between 0 and 80ms. With these settings, messages were frequently reordered
during their transmission. Using the three sets of optimizations obtained for
synchronous networks, we observed a latency decrease of 10%, and a network
consumption decrease of 50% with 16KB messages and $N=31$. This suggests that
overall, our modifications also perform well in asynchronous networks, but
also that the configurations might have to be fine tuned to improve
performance.

##  IX Conclusion

In this paper, we discussed the Byzantine reliable broadcast problem on
unknown partially connected topologies. This problem can be solved by
combining two seminal protocols, Dolev’s and Bracha’s algorithms. We first
explained how recent improvements of Dolev’s algorithms can be used in this
protocol combination. We then described a total of 12 new modifications one
can apply to this protocol combination to optimize latency and/or bandwidth
consumption. We benchmarked the impact of each modification using the Omnet++
network simulator on random graphs. When simultaneously applied, our
modifications allow the BRB problem to be solved with a lower latency and/or
bandwidth consumption, e.g., respectively down to -25% and -50% with a 16B
payload when $N{=}31$ and $f{=}4$. Future works include to also consider the
local fault model used for example in the CPA line of work [11, 12, 13].

## References

  * [1] Jiangshan Yu, David Kozhaya, Jeremie Decouchant and Paulo Esteves-Verissimo  “Repucoin: Your reputation is your power”  In _IEEE Transactions on Computers_ 68.8, 2019, pp. 1225–1237
  * [2] Daniel Collins et al.  “Online payments by merely broadcasting messages”  In _DSN_ , 2020
  * [3] Gabriel Bracha  “Asynchronous Byzantine Agreement Protocols”  In _Inf. Comput._ 75.2, 1987, pp. 130–143  DOI: 10.1016/0890-5401(87)90054-X
  * [4] Danny Dolev  “Unanimity in an unknown and unreliable environment”  In _FOCS_ , 1981  IEEE
  * [5] Ye Wang and Roger Wattenhofer  “Asynchronous Byzantine Agreement in Incomplete Networks”  In _AFT_ ACM, 2020  URL: https://arxiv.org/pdf/2005.12725.pdf
  * [6] Silvia Bonomi, Giovanni Farina and Sébastien Tixeuil  “Multi-hop Byzantine reliable broadcast with honest dealer made practical”  In _Journal of the Brazilian Computer Society_ 25.1 Springer, 2019, pp. 9:1–9:23
  * [7] Kai Zeng, Kannan Govindan and Prasant Mohapatra  “Non-cryptographic authentication and identification in wireless networks”  In _IEEE Wireless Communications_ 17.5 IEEE, 2010, pp. 56–62
  * [8] Gabriel Bracha  “An asynchronous [(n-1)/3]-resilient consensus protocol”  In _PODC_ , 1984
  * [9] Gabriel Bracha and Sam Toueg  “Asynchronous Consensus and Broadcast Protocols”  In _J. ACM_ 32.4, 1985, pp. 824–840  DOI: 10.1145/4221.214134
  * [10] Alexandre Maurer, Sébastien Tixeuil and Xavier Defago  “Communicating reliably in multihop dynamic networks despite byzantine failures”  In _SRDS_ , 2015
  * [11] Chiu-Yuen Koo  “Broadcast in radio networks tolerating byzantine adversarial behavior”  In _PODC_ , 2004, pp. 275–282
  * [12] Andrzej Pelc and David Peleg  “Broadcasting with locally bounded byzantine faults”  In _Information Processing Letters_ 93.3 Elsevier, 2005, pp. 109–115
  * [13] Chris Litsas, Aris Pagourtzis and Dimitris Sakavalas  “A graph parameter that matches the resilience of the certified propagation algorithm”  In _AdHoc-Now_ , 2013  URL: https://www.researchgate.net/profile/Aris_Pagourtzis/publication/259597281_A_Graph_Parameter_That_Matches_the_Resilience_of_the_Certified_Propagation_Algorithm/links/546dd7b80cf26e95bc3d02a0/A-Graph-Parameter-That-Matches-the-Resilience-of-the-Certified-Propagation-Algorithm.pdf
  * [14] Alexandre Maurer and Sébastien Tixeuil  “Byzantine broadcast with fixed disjoint paths”  In _Journal of Parallel and Distributed Computing_ 74.11, 2014, pp. 3153–3160
  * [15] Alexandre Maurer and Sébastien Tixeuil  “Containing byzantine failures with control zones”  In _IEEE TPDS_ 26.2, 2014, pp. 362–370
  * [16] Miguel Castro and Barbara Liskov  “Practical Byzantine Fault Tolerance”  In _OSDI_ , 1999  DOI: 10.1145/296806.296824
  * [17] Rachid Guerraoui et al.  “Scalable Byzantine Reliable Broadcast”  In _DISC_ , 2019
  * [18] David Kozhaya, Jérémie Decouchant and Paulo Esteves-Verissimo  “RT-ByzCast: Byzantine-Resilient Real-Time Reliable Broadcast”  In _IEEE ToC_ 68.3 IEEE, 2018, pp. 440–454
  * [19] David Kozhaya, Jeremie Decouchant, Vincent Rahli and Paulo Esteves-Verissimo  “PISTIS: An Event-Triggered Real-time Byzantine Resilient Protocol Suite”  In _IEEE Transactions on Parallel and Distributed Systems_ IEEE, 2021
  * [20] Sonia Ben Mokhtar, Jérémie Decouchant and Vivien Quéma  “Acting: Accurate freerider tracking in gossip”  In _SRDS_ , 2014
  * [21] Jérémie Decouchant, Sonia Ben Mokhtar, Albin Petit and Vivien Quéma  “Pag: Private and accountable gossip”  In _ICDCS_ , 2016
  * [22] Christian Cachin, Rachid Guerraoui and Luís E.. Rodrigues  “Introduction to Reliable and Secure Distributed Programming”  Springer, 2011  DOI: 10.1007/978-3-642-15260-3
  * [23] Michel Raynal  “Fault-tolerant message-passing distributed systems: an algorithmic approach”  Springer, 2018
  * [24] Karl Menger  “Zur allgemeinen kurventheorie”  In _Fundamenta Mathematicae_ 10.1 Institute of Mathematics Polish Academy of Sciences, 1927, pp. 96–115
  * [25] Jonathan Behrens, Sagar Jha, Ken Birman and Edward Tremel  “RDMC: A reliable RDMA multicast for large objects”  In _DSN_ , 2018
  * [26] “Omnet++ Discrete Event Simulator”  URL: https://omnetpp.org/
  * [27] Angelika Steger and Nicholas C Wormald  “Generating random regular graphs quickly”  In _Combinatorics, Probability and Computing_ 8.04, 1999, pp. 377–396
  * [28] Aric Hagberg, Pieter Swart and Daniel S Chult  “Exploring network structure, dynamics, and function using NetworkX”, 2008


# Classical Computer, Quantum Computer, and the Gödel’s theorem

Biao Wu<EMAIL_ADDRESS>International Center for Quantum Materials, School
of Physics, Peking University, Beijing 100871, China  Wilczek Quantum Center,
School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai
200240, China  Collaborative Innovation Center of Quantum Matter, Beijing
100871, China

###### Abstract

I show that the cloneability of information is the key difference between
classical computer and quantum computer. As information stored and processed
by neurons is cloneable, brain (human or non-human) is a classical computer.
Penrose argued with the Gödel theorem that human brain is not classical. I
demonstrate with an example why his argument is flawed. At the end, I discuss
how to go beyond quantum computer.

Galileo wrote in 1623, “Philosophy is written in this grand book - I mean the
universe - which stands continually open to our gaze, but it cannot be
understood unless one first learns to comprehend the language in which it is
written. It is written in the language of mathematics, and its characters are
triangles, circles, and other geometric figures, without which it is humanly
impossible to understand a single word of it; without these, one is wandering
about in a dark labyrinth. ” Galilei (1960) This was a remarkably bold and
visionary statement at the time when there were only a few accurate
mathematical descriptions of physical phenomena, such as free fall and
pendulum. Currently there is no doubt that the universe is written in the
language of mathematics. A physical process is literally a demonstration of a
mathematical solution. As computation is a process of finding mathematical
solutions, a physical process can be regarded as a computation of a
mathematical equation. Or simply, physics is computational. How about the
reverse, is computation physical? The answer had been ‘No’ until the discovery
of quantum computer Manin (1980); Feynman (1982); Deutsch (1985, 1989). It is
now widely accepted that computation is physical. Different models of
computation correspond to different physical laws. Classical physics underlies
Turing machine and other models of classical computer; quantum physics is
behind quantum computer.

However, it is not obvious at all why classical computer is classical and
quantum computer is quantum. Neither is there the Newton’s equations of motion
explicitly in classical computer nor is there the Schrödinger equation
explicitly in quantum computer. There is even no Planck constant $\hbar$ in
theoretical models of quantum computer. It turns out that being classical and
being quantum are concepts more fundamental than equations of motion. The
nature of a computer is determined by the cloneability of the information
processed by the computer. If the information is cloneable, the computer is
classical; if it is uncloneable, the computer is quantum. As the information
processed in neurons are cloneable, brains (human or non-human) are classical
computers. Penrose argued that the Gödel theorem implies that human brains
(not all brain) are not classical Penrose (1994). I shall show that this is
due to his misunderstanding of the theorem. The Gödel theorem in fact implies
that there are innumerable mathematical statements so that human
mathematicians, who have only finite physical resources, cannot prove all of
them true or false. An example is constructed to demonstrate it. In the end, I
shall give an example on how to construct theoretical models of computing that
are more powerful than quantum computer He et al. (2021). To do this, the
information processed by the computer has to be different from both classical
computer and quantum computer.

##  I Classical computer and quantum computer

There are many different models of classical computer, such as the famed
Turing machine and the conventional digital computer. They are all equivalent
in terms of theoretical computing power Nielson and Chuang (2000). I shall use
the reversible classical computer to illustrate the essential features of
classical computer. The primary reason is that quantum computer can be viewed
as a straightforward extension or quantization of reversible classical
computer.

A reversible classical computer has one universal logic gate, the Tofolli
gate, along with an array of bits. Each bit has only two values, 0 and 1. The
Tofolli gate, as shown in Fig.1B, has two control bits and one target bit.
Only when both the control bits are 1, the target bit switches between 0 and 1
Nielson and Chuang (2000).

(A)  @C=1.8em @R=2.4em a & 1 a  b 1 b  c c⊕ab  (B)  @C=1.8em @R=2.4em 1 & 1 1
b 1 b c c⊕b

Figure 1: (A) the Toffoli gate; (B) CNOT gate constructed from the Tofolli
gate. The inputs $a,b,c$ are Boolean variables.

On top of the reversible classical computer, if we add two more logic gates
and replace bits with qubits, we have the standard circuit model of quantum
computer. The two additional gates are the Hadamard gate $H$ and $\pi/8$ gate
$T$ Nielson and Chuang (2000),

$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}~{}\,,~{}~{}~{}~{}~{}T=\frac{1}{\sqrt{2}}\begin{pmatrix}1&0\\\
0&e^{i\pi/4}\end{pmatrix}~{}\,.$ (1)

The usual universal quantum gate, CNOT gate, can be easily constructed from
the Tofolli gate as shown Fig.1(B). The key difference between qubit and bit
is that a qubit can be in a superposition state

$\ket{\psi}=\alpha\ket{0}+\beta\ket{1}\,.$ (2)

The states of a bit correspond to two special cases, $\alpha=1,\beta=0$ and
$\alpha=0,\beta=1$.

The Hadamard gate is the key in quantum computer. It is the only universal
gate that is capable of generating a superposition state out of a non-
superposition state, for example,

$H\ket{0}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\,.$ (3)

Only with Hadamard gates will we be able to generate more superposition terms,
change the superposition amplitudes, and facilitate interference in the course
of computation. This shows that quantum computer can be viewed as a
quantization of reversible classical computer. The quantization is achieved
primarily with the Hadamard gate and additionally with $\pi/8$ gate $T$, but
remarkably without Planck constant. A classical computer with $n$ bits have
exactly $2^{n}$ states,

$\ket{J}=\ket{J_{1},J_{2},\cdots,J_{k},\cdots,J_{n}}$ (4)

where $J_{k}$ is the $k$th binary digit of $J$ ($J=0,1,2,\cdots,2^{n}-1$). In
contrast, a quantum computer with $n$ qubits has infinite states that live in
a Hilbert space spanned by $\ket{J}$’s. In general, a quantum computer is in a
superposition state as

$\ket{\Psi}=\sum_{J=0}^{2^{n}-1}a_{J}\ket{J}\,.$ (5)

##  II Cloneable states and uncloneable states

The reversible classical computer is clearly not quantum as it does not allow
generation of superposition. But why is it classical? Why is Turing machine
classical? The conventional digital computer is also regarded classical even
it is irreversible. What do these models of classical computer have in common
with classical mechanics? Similarly, why is the model of quantum computer
described above quantal? There is even no Planck constant in the model.

To answer these questions, let us review dynamical systems in general. A
dynamical system has a configuration space and an evolution rule (or a set of
evolution rules). Its state is a point in the configuration space. The system
can start at any point in the configuration space. The evolution rule dictates
it to evolve deterministically from one state to another. Classical mechanics
is a dynamical system. The configuration space is the phase space and the
evolution rule is the Newton’s equations of motion. Quantum mechanics is a
dynamical system. The configuration space is the Hilbert space and the
evolution rule is the Schrödinger equation. Mathematically, classical
mechanics and quantum mechanics, are essentially the same type of dynamical
systems. Koopman and von Neumann formulated classical mechanics mathematically
as quantum systems Koopman (1931); von Neumann (1932). And Heslot converted
the Schrödinger equation mathematically into a set of Newton’s equations of
motion Heslot (1985).

This shows that the equations of motion are not what makes classical mechanics
classical and quantum mechanics quantal. The key difference is how their
states, the points in their configuration spaces, are related to physical
reality. The coordinates of a point in the phase space are momenta and
positions, which can be directly measured and cloned. In contrast, a point in
a Hilbert space, usually called wave function, is not directly observable and
can not be cloned in general. To relate a wave function to physical reality,
one has to first select a complete set of orthonormal basis, which are usually
the eigenfunctions of a physical quantity such as momentum, position or
angular momentum. This selection of basis is outside of the configuration
space and the equations of motion, and is done independently. When the wave
function is expanded in the basis, the expansion coefficients ( or the
coordinates) are not measurable, and thus not cloneable. Upon measurement, the
observed is the basis vector and its corresponding eigenvalue, not the
coefficients ( or the coordinates). To distinguish this crucial difference, we
call classical state ( a point in phase space ) cloneable and quantum state (a
vector in Hilbert space) uncloneable. It is this cloneability of their states
that separates a classical system from a quantum system, not its equations of
motion. This cloneability is related to the well-known no-cloning theorem for
quantum statesPark (1970); Wootters and Zurek (1982). According to this
theorem, all the states $\ket{J}$ of bits can be cloned but not their
superpositions, such as the states in Eq.(5).

The states of a classical particle are cloneable. Its position and momentum
can be measured and recorded directly, ultimately cloned faithfully with
negligible errors. The states $\ket{J}$ of bits are cloneable not only
theoretically but also in practice: the two states, 0 or 1, of a bit, often
represented by voltages, can be measured and observed directly, and cloned
faithfully. It is this common feature with a classical particle that makes
bits classical. This is the key reason that any computer with bits, such as
the Turing machine, the conventional digital computer, and the reversible
computer are classical. In contrast, the states of qubits are vectors in the
Hilbert space just as the wave functions in quantum mechanics. Upon
measurement, only partial information of these states can be recorded; they
can not be cloned faithfully with negligible errors. As a result, computers
with qubits are quantum computer. It is now clear. Classical computer is
classical because its states (or information) are cloneable. Quantum computer
is quantal is because its states (or information) are uncloneable. One can
force the quantum states be cloneable. This is exactly what happens when we
simulate a quantum system on a classical computer. The price to pay is that
the memory size of a classical computer would have to grow exponentially with
the size of the quantum system. It is precisely what motivated the conception
of quantum computer Manin (1980); Feynman (1982). Note that one can also
repeat measurements on a given quantum state and ultimately clone it
faithfully. Unfortunately, the number of measurements needed grows
exponentially with the system size Hu and You (2021).

##  III Brain and the Gödel’s theorem

Brain (human or non-human) is clearly a classical computer because the states
of each neuron are cloneable. A neuron state is marked by electrical pulses
(usually called action potential) passing through the axon, opening of ion
channels, sodium and potassium concentrations, activation of chemical or
electric signals at synapses. These physical and chemical states can be
measured and recorded directly, and cloned faithfully at least in principle.
Technically, it is challenging to clone faithfully the functions of a single
neuron, not to mention a network of neurons (brain) . But it is an issue of
technology, not an issue of theoretical principles. Technically, we are still
far away building a machine that moves in a jungle as adeptly as monkeys.
Nevertheless, the monkey’s brain, muscle, and other body parts function
classically.

That human brain is a classical computer is also evident in the process of a
mathematician proving a theorem. When a mathematician proves a theorem, axioms
or assumptions are inputs, mathematical inductions are logical gates, known
theorems or lemmas are subroutines. A completed proof is essentially a
classical algorithm because all the symbols and induction rules can be written
down without any ambiguity, and be cloned faithfully from mathematician to
mathematician. In other words, they are cloneable just as the states of bits.

However, Penrose argued the contrary that human brain is not a classical
computer and may be of quantum nature Penrose (1994). He believes that this is
implied in the Gödel’s incomplete theorem, which states that there are
statements in any consistent formal system $F$ which can neither be proved nor
disproved in $F$. Let me first summarize Penrose’s arguments or proof Penrose
(1994). He listed all the computations $C_{q}(n)$ that take a natural number
$n$ as its input. $C_{q}(n)$ is the $q$th algorithm that computes on the input
$n$. $A(q,n)$ of two inputs $q$ and $n$ is an algorithm that intends to
ascertain whether $C_{q}(n)$ will stop: if $A(q,n)$ stops, $C_{q}(n)$ does not
stop. With Cantor’s diagonalization argument, Penrose arrives at the statement
(M): if $C_{k}(k)$ stops, $C_{k}(k)$ does not stop. This leads him to conclude
that

> Human mathematicians are not using a knowably sound algorithm in order to
> ascertain mathematical truths.

This means that human brain is not a classical computer. For me, (M) is simply
a self-contradictory statement and means that at least one of the assumptions
made at the start of Penrose’s proof is wrong. In fact, Penrose implicitly
assumed that all the algorithms $C_{q}(n)$ are countable and therefore can be
listed. This assumption is certainly wrong. In Cantor’s proof that the real
numbers are innumerable, he first assumed that the real numbers are countable
and can be listed. With the diagonalization argument, he found a real number
outside of the list. A contradiction so that the assumption that the real
numbers are countable is wrong. Cantor’s proof also implies that irrational
numbers can not be exhausted by a finite number of different operations with
finite symbols. In contrast, all rational numbers can be obtained by one
operation (division) with 10 digits (0,1,2,3,4,5,6,7,8,9).

Similarly, it is wrong to assume that algorithms are countable. Here is an
example that demonstrates that there are innumerable algorithms. A number is
said embedded in $\pi$ if its decimal digits can be found in $\pi$ in the
sequential order. For example, 1.23456 is embedded in the first 50 decimal
digits of $\pi$,

$3.\underline{\bm{1}}4159\underline{\bm{2}}65\underline{\bm{3}}589793238\underline{\bm{4}}62643383279\underline{\bm{5}}028841971\underline{\bm{6}}939937510...$
(6)

$R^{(n)}(x)$ is an operation that repeats $n$ times each decimal digit of $x$.
For example, $R^{(1)}(1.23456)=1.23456$ and
$R^{(3)}(1.23456)=111.222333444555666$. For every real number $x$, we
construct a list of mathematical statements $E^{(n)}(x)$: $R^{(n)}(x)$ is
embedded in $\pi$. The statement $E^{(1)}(\sqrt{2})$ is probably true. Its
first twelve decimal digits are embedded in the first 100 digits of $\pi$.

$\displaystyle
3.\underline{\bm{1}}\underline{\bm{4}}\underline{\bm{1}}592653589793238\underline{\bm{4}}6\underline{\bm{2}}643383279502884\underline{\bm{1}}97169\underline{\bm{3}}9937\underline{\bm{5}}10$
$\displaystyle
582097494459230781\underline{\bm{6}}406\underline{\bm{2}}862089986280\underline{\bm{3}}482534211\underline{\bm{7}}0679...$
(7)

Its thirteenth digit is $3$ and will be found in the rest digits of $\pi$,
similarly its fourteenth digit $0$, and so on. The statement
$E^{(2)}(\sqrt{2})$ is no longer as obvious. Here is the situation for the
fist 200 digits of $\pi$.

$\displaystyle 3.14159265358979323846264338327950288419716939937510$
$\displaystyle
5820974944592307816406286208998628034825342\underline{\bm{11}}70679$
$\displaystyle
821480865132823066470938\underline{\bm{44}}609550582231725359408128$
$\displaystyle
48\underline{\bm{11}}174502841027019385211055596\underline{\bm{44}}6\underline{\bm{22}}94895493038196...$
(8)

But still it is hard to believe that the next two digits $11$ never appear in
the rest digits of $\pi$, similarly $33$, and so on. $E^{(2)}(\sqrt{2})$ is
probably true. As $n$ increases, we become less confident that the statement
$E^{(n)}(\sqrt{2})$ is true. Consider $n=6$. The first string of six or more
consecutive identical digits is six 9’s starting at the 762nd decimal place of
$\pi$, the next is again six 9’s starting at position 193034, and the next is
six 8’s starting at position 222,299 Andersen .

To verify whether $E^{(n)}(x)$’s are true or not, one can set up algorithms
that simply compute every decimal digits of $x$ and $\pi$ and check them one
by one. This method can show that some statements, such as $E^{(6)}(9)$, are
true. When $x$ is irrational, this method fails. It can not even show with
100% certainty whether $E^{(1)}(\sqrt{2})$ is true because mathematicians
(including machines) have only finite resources and they can not compute
infinite number of digits. However, sometimes one does not need to compute out
all the digits of an irrational number to verify a statement true or false.
For example, one can show that $\sqrt{2}$ is irrational and $E^{(1)}(\pi)$ is
true without computing out all the digits. So, it is possible that
mathematicians can figure out a ‘clever’ way or algorithm to verify that
$E^{(1)}(\sqrt{2})$ is true. However, it is hard to imagine that ‘clever’
algorithms can be found for all irrational numbers and any $n$.

As the real numbers are innumerable, we have innumerable mathematical
statements $E^{(n)}(x)$. Each statement $E^{(n)}(x)$ is clearly also an
algorithm with two inputs $n$ and $x$, and can be identified with $C_{q}(n)$
via $q=x$. This example shows that Penrose’s assumption that $C_{q}(n)$’s are
countable is wrong.

We now face two realities: (1) there are innumerable number of mathematical
statements; (2) human mathematicians are only capable of using finite number
of symbols, finite sets of induction rules, and doing finite steps of
deductions ( similar to a finite number of logical gates in an algorithm). The
latter means that the mathematical statements that can be verified by human
mathematicians are countable and can be listed. Therefore, it is clear that
mathematicians can not prove all the mathematical statements, which are
innumerable, true or false. This is the essence of the Gödel’s theorem.
Therefore, the Gödel’s theorem has nothing to do with whether human brain is
classical or not. The theorem just shows with mathematical rigor a common
sense: it is impossible for any thinking machine (including human brain) with
finite resources to solve innumerable problems.

The Gödel’s theorem is often explained with self-referencing examples, for
example, this statement is not true. This self-referencing is made rigorous in
its proof with the diagonalization argument. It gives the theorem a mystique
appearance that obscures its essence and true implication: innumerable
problems can not be solved with finite physical resources.

There are obvious differences between brain and the conventional digital
computer. It is a mundane task for many animals, including human, to walk or
run on difficult terrains; it is declared a major achievement whenever
robots’s walking abilities have been improved in one or another aspect. It
takes a long time for a human to add two large numbers; it takes almost no
time for a digital computer to do it. This does not imply that human brain may
be a quantum computer. It is simply that we do not understand the networking
of neurons inside human brain. Just as we do not need to know every technical
details of a digital computer to know for sure that it is classical, we can be
absolutely sure that human brain is classical before we understand it
completely.

Galileo said that physics is written in the language of mathematics; Gödel
proved that mathematics is limited by physics. After all, human is physical.
All human products, including mathematical theorems, are limited by the
physical laws. What we know and will know is negligible relative to what we
will never know. This is in a sense good as we will never run out of truths to
discover.

##  IV Beyond quantum computing

Is it possible to go beyond quantum computer? According the analysis in
Section II, it is impossible in practice since we do not have any
experimentally tested theory that goes beyond quantum mechanics.
Theoretically, it is certainly possible. We only need a dynamical system whose
states in its configuration space are related to physical reality differently
from both classical mechanics and quantum mechanics.

One of such systems was discussed long time ago by Pauli Pauli (1943) who was
inspired by Dirac Dirac (1942). It was considered independently many years
later as a generalization of Bogoliubov-de Gennes equation Zhang and Wu
(2018). It was named Lorentz quantum mechanics because its dynamical evolution
is generalized Lorentz transformation. The key features of the Lorentz
mechanics are: (1) its states are vectors in a complex linear space with an
indefinite metric; (2) its dynamics is generalized Lorentz transformation; (3)
there are two sets of states, one with positive inner products and the other
with negative products. The third feature is crucial: the positive states are
regarded as physical and can be measured; the negative one are regarded
unphysical. This means that the states in the configuration space, an inner
product space with indefinite metric, are not only uncloneable and half of
them are also unphysical. This is different from both classical states and
quantum states.

We have proposed a new theoretical model of computing based on this Lorentz
quantum mechanics He et al. (2021). We find that the search algorithm designed
for this new computer model is exponentially faster than the Grover’s
algorithm Grover (1997). It shows explicitly that one can go beyond
conventional quantum computer. If in a new theory that unifies quantum theory
and gravity its states are different from both classical states and quantum
states, we would also expect to have a more powerful model of computing.

There are two computer models that were shown to be more powerful than quantum
computer Abrams and Lloyd (1998); Bacon (2004). Both add nonlinearity to
quantum mechanics and claim that nonlinearity is behind the enhancement of
computing power. It is suspicious argument. Classical mechanics is inherently
nonlinear and no one has been able to exploit its nonlinearity to enhance
computing power. It is no surprise that both models were critically questioned
from the theoretical point of viewBennett et al. (2009).

###### Acknowledgements.

I thank Zhenduo Wang, Yu Shi, and Zhuoquan Lin for helpful discussion. This
work is supported by the The National Key R&D Program of China (Grants No.
2017YFA0303302, No. 2018YFA0305602), National Natural Science Foundation of
China (Grant No. 11921005), and Shanghai Municipal Science and Technology
Major Project (Grant No.2019SHZDZX01).

## References

  * Galilei (1960) G. Galilei, _The Assayer_ (University of Pennsylvania Press, 1960).
  * Manin (1980) Y. I. Manin, _Computable and Noncomputable_ (Sov. Radio., 1980).
  * Feynman (1982) R. P. Feynman, International Journal of Theoretical Physics 21, 467 (1982).
  * Deutsch (1985) D. Deutsch, Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 400, 97 (1985).
  * Deutsch (1989) D. Deutsch, Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 425, 73 (1989).
  * Penrose (1994) R. Penrose, _Shadows of the Mind_ (Oxford University Press, New York, 1994).
  * He et al. (2021) W. He, Z. Wang, and B. Wu, arXiv:2103.10315 (2021).
  * Nielson and Chuang (2000) M. A. Nielson and I. L. Chuang, _Quantum computing and quantum information_ (Cambridge University Press, Cambridge, 2000).
  * Koopman (1931) B. O. Koopman, Proceedings of the National Academy of Sciences of the United States of America 17, 315 (1931).
  * von Neumann (1932) J. von Neumann, Annals of Mathematics 33, 587 (1932).
  * Heslot (1985) A. Heslot, Phys. Rev. D 31, 1341 (1985).
  * Park (1970) J. L. Park, Foundations of Physics 1, 23 (1970).
  * Wootters and Zurek (1982) W. K. Wootters and W. H. Zurek, Nature 299, 802 (1982).
  * Hu and You (2021) H.-Y. Hu and Y.-Z. You, arXiv:2102.10132 (2021).
  * (15) D. Andersen, _The pi searcher_ , URL https://www.angio.net/pi/bigpi.cgi.
  * Pauli (1943) W. Pauli, Rev. Mod. Phys. 15, 175 (1943).
  * Dirac (1942) P. A. M. Dirac, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 180, 1 (1942).
  * Zhang and Wu (2018) Q. Zhang and B. Wu, New Journal of Physics 20, 013024 (2018).
  * Grover (1997) L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
  * Abrams and Lloyd (1998) D. S. Abrams and S. Lloyd, Physical Review Letters 81, 3992 (1998).
  * Bacon (2004) D. Bacon, Physical Review A 70, 032309 (2004).
  * Bennett et al. (2009) C. H. Bennett, D. Leung, G. Smith, and J. A. Smolin, Phys. Rev. Lett. 103, 170502 (2009).
  * Wilczek et al. (2020) F. Wilczek, H.-Y. Hu, and B. Wu, Chinese Physics Letters 37, 050304 (2020).
  * Wu et al. (2020) B. Wu, H. Yu, and F. Wilczek, Phys. Rev. A 101, 012318 (2020).
  * Yu et al. (2021) H. Yu, F. Wilczek, and B. Wu, Chinese Physics Letters 38, 030304 (2021).