# Self-stabilizing Byzantine Fault-tolerant Repeated Reliable Broadcast

Romaric Duvignau 111Chalmers University of Technology, Sweden
<EMAIL_ADDRESS>Michel Raynal 222Institut Universitaire de France
IRISA, France<EMAIL_ADDRESS>Elad Michael Schiller ∗

###### Abstract

We study a well-known communication abstraction called Byzantine Reliable
Broadcast (BRB). This abstraction is central in the design and implementation
of fault-tolerant distributed systems, as many fault-tolerant distributed
applications require communication with provable guarantees on message
deliveries. Our study focuses on fault-tolerant implementations for message-
passing systems that are prone to process-failures, such as crashes and
malicious behavior. At PODC 1983, Bracha and Toueg, in short, BT, solved the
BRB problem. BT has optimal resilience since it can deal with $t<n/3$
Byzantine processes, where $n$ is the number of processes. The present work
aims at the design of an even more robust solution than BT by expanding its
fault-model with self-stabilization, a vigorous notion of fault-tolerance. In
addition to tolerating Byzantine and communication failures, self-stabilizing
systems can recover after the occurrence of _arbitrary transient-faults_.
These faults represent any violation of the assumptions according to which the
system was designed to operate (provided that the algorithm code remains
intact). We propose, to the best of our knowledge, the first self-stabilizing
Byzantine fault-tolerant (BFT) solution for repeated BRB in signature-free
message-passing systems (that follows BT’s problem specifications). Our
contribution includes a self-stabilizing variation on a BT that solves a
single-instance BRB for asynchronous systems. We also consider the problem of
recycling instances of single-instance BRB. Our self-stabilizing BFT recycling
for time-free systems facilitates the concurrent handling of a predefined
number of BRB invocations and, by this way, can serve as the basis for self-
stabilizing BFT consensus.

##  1 Introduction

Fault-tolerant distributed systems are known to be hard to design and verify.
High-level communication primitives can facilitate such complex challenges.
These high-level primitives can be based on low-level ones, such as the one
that allows processes to send a message to only one other process at a time.
Hence, when an algorithm wishes to broadcast message $m$ to all processes, it
can send $m$ individually to every other process. Note that if the sender
fails during this broadcast, it can be the case that only some of the
processes have received $m$. Even in the presence of network-level support for
broadcasting or multicasting, failures can cause similar inconsistencies. In
order to simplify the design of fault-tolerant distributed algorithms, such
inconsistencies need to be avoided. Many examples show how fault-tolerant
broadcasts can significantly simplify the development of fault-tolerant
distributed systems, _e.g.,_ State Machine Replication [42] and Set-
Constrained Delivery Broadcast [4]. The weakest variant, named _Reliable
Broadcast_ , lets all non-failing processes agree on the set of delivered
messages. This set includes all the messages broadcast by the non-failing
processes. Stronger reliable broadcasts variants specify additional
requirements on the delivery order. Such requirements can simplify the design
of fault-tolerant distributed consensus, which allows reaching, despite
failures, a common decision based on distributed inputs. Reliable broadcast
and consensus (as well as message-passing emulation of read/write registers
[42]) are closely related to distributed computing problems. This work aims to
design an reliable broadcast solution that is more fault-tolerant than the
state of the art.

###  1.1 The problem

Lamport, Shostak, and Pease [33] said that a process commits a Byzantine
failure if it deviates from the algorithm instructions, say, by deferring (or
omitting) messages that were sent by the algorithm or sending fake messages.
Such malicious behavior can be the result of hardware malfunctions or software
errors as well as coordinated malware attacks. Bracha and Toueg [17, 16], BT
from now on, proposed the communication abstraction of Byzantine Reliable
Broadcast (BRB), which allows every process to invoke the
$\mathsf{brbBroadcast}(v)$ operation and raise the $\mathsf{brbDeliver}()$
event upon message arrival. Following Raynal [42, Ch. 4], we consider the
(single instance) BRB problem.

####  1.1.1 Single-instance BRB.

We require $\mathsf{brbBroadcast}(v)$ and $\mathsf{brbDeliver}()$ to satisfy
Definition 1.1.

######  Definition 1.1.

  * •

BRB-validity.  Suppose a correct process BRB-delivers message $m$ from a
correct process $p_{i}$. Then, $p_{i}$ had BRB-broadcast $m$.

  * •

BRB-integrity.  No correct process BRB-delivers more than once.

  * •

BRB-no-duplicity.  No two correct processes BRB-deliver different messages
from $p_{i}$ (who might be faulty).

  * •

BRB-Completion-1.  Suppose $p_{i}$ is a correct sender. All correct processes
BRB-deliver from $p_{i}$ eventually.

  * •

BRB-Completion-2.  Suppose a correct process BRB-delivers a message from
$p_{i}$ (who might be faulty). All correct processes BRB-deliver $p_{i}$’s
message eventually.

####  1.1.2 Repeated BRB.

Distributed systems use, over time, an unbounded number of BRB instances. We
require our solution to use, at any given point in time, a bounded amount of
memory. Thus, for the sake of completeness, we also consider the problem of
recycling an unbounded sequence of BRB invocations using bounded memory. We
require the (single-instance) BRB object, $O$, to have an operation, called
$\mathsf{recycle}()$, that allows the recycling mechanism locally reset $O$,
after all non-faulty processes had completed the delivery of $O$’s message.
Also, we require the mechanism to inform (the possibly recycled) $O$ regarding
its availability to take new missions. Specifically, the
$\mathsf{txAvailable}()$ operation returns $\mathsf{True}$ when the sender can
use $O$ for broadcasting and $\mathsf{rxAvailable}()$ returns $\mathsf{True}$
when $O$’s new transmission has arrived at the receiver.

One may observe that the problem statement does not depend on the fault model
or the design criteria. However, the proposed solution depends on all three.
To clarify, we solve the single instance BRB using the requirements presented
by Raynal [42, Ch. 4]. Then, we solve an extended version of the problem in
which each BRB instance needs to be recycled so that an unbounded number of
BRB instances can appear.

###  1.2 Fault models

Recall that our BRB solution may be a component in a system that solves
consensus. Thus, we safeguard against Byzantine failures by following the same
assumptions that are often used when solving consensus. Specifically, for the
sake of deterministic and signature-free solvability [41], we assume there are
at most $t<n/3$ crashed or Byzantine processes, where $n$ is the total number
of processes. The proposed solutions are for message-passing systems that have
no guarantees on the communication delay and without explicit access to the
clock. These systems are also prone to communication failures, _e.g.,_ packet
omission, duplication, and reordering, as long as fair communication (FC)
holds, _i.e.,_ if $p_{i}$ sends a message infinitely often to $p_{j}$, then
$p_{j}$ receives that message infinitely often. We use three different fault
models with notations following Raynal [42]:

  * •

$\mathsf{BAMP_{n,t}[FC,t<n/3]}$. This is a Byzantine Asynchronous Message-
Passing model with at most $t$ (out of $n$) faulty nodes. The array
$[FC,t<n/3]$ denotes the list of all assumptions, _i.e.,_ FC and $t<n/3$. We
use this model for studying the problem of single-instance BRB since it has no
synchrony assumptions.

  * •

$\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$. By Doudou _et al._
[25], processes commit muteness failures when they stop sending specific
messages, but they may continue to send “I-am-alive” messages. For studying
the problem of BRB instance recycling, we enrich $\mathsf{BAMP_{n,t}[FC,t<}$
$\mathsf{n/3]}$ with a muteness detector of class $\diamondsuit P_{mute}$ and
assume bounded message lifetime (BML). That is, in any unbounded sequence of
BRB invocations, at the time that immediately follows the $x$-th invocation,
the messages associated with the $(x\mathit{-}\lambda)$-th invocation (or
earlier) are either delivered or lost, where $\lambda$ is a known upper-bound.

  * •

$\mathsf{AMP_{n}[FC,BML]}$. For the sake of a simple presentation of the
repeated BRB solution, we first present a solution for the fault model,
$\mathsf{AMP_{n}[FC,BML]}$, which does not consider any node failures (before
presenting a repeated BRB solution for
$\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$).

Raynal [42] refers to an asynchronous system as time-free when it includes
synchrony assumptions, _e.g.,_ BML. Note that BML does not imply bounded
communication delay since an unbounded number of messages can be lost between
any two successful transmissions. At last, our muteness detector
implementation follows an assumption about the number, $\Theta$, of messages
that some non-faulty processes can exchange without hearing from all non-
faulty processes.

###  1.3 Self-stabilization

Dijkstra’s seminal work [18] demonstrated recovery within a finite time after
the occurrence of the last transient fault, which may corrupt the system state
in any manner (as long as the program code stays intact). Dijkstra offered an
alternative to traditional fault-tolerance, which aims at assuring that the
system, at all times, remains in a correct state under the assumption that the
system state changes only due to the algorithmic steps and specified failures.
Alas, the latter target is unattainable in the presence of failures that were
unforeseen during the algorithm design. In order to address this concern,
self-stabilization considers failures that are transient by nature and hard to
be observed. Thus, they cannot be specified by the fault model, such as the
one above, which includes process and communication failures. Therefore, self-
stabilizing systems are required to recover eventually (in the presence of all
foreseen and specified failures) after the occurrence of the last unforeseen
and transient failure.

In this paper, in addition to the faults specified above, we also aim to
recover after the occurrence of the last _arbitrary transient-fault_ [2, 19].
These transient-faults model any temporary violation of assumptions according
to which the system was designed to operate. This includes the corruption of
control variables, such as the program counter and packet payloads, as well as
operational assumptions, such as that at most $t<n/3$ processes are faulty.
Since the occurrence of these failures can be arbitrarily combined, we assume
these transient-faults can alter the system state in unpredictable ways. When
modeling the system, Dijkstra assumed that these violations can bring the
system to an arbitrary state from which a _self-stabilizing system_ should
recover [18]. _I.e.,_ Dijkstra requires the correctness proof of a self-
stabilizing system to demonstrate recovery within a finite time after the last
occurrence of a transient-fault and once the system has recovered, it must
never violate the task requirements. Arora and Gouda [3] refer to the former
property as convergence and the latter closure. Note that the stratification
of the task requirements, which is Definition 1.1 in the case of this paper,
holds only when closure is guaranteed. To say it in other words, only after
the system has finished recovering from the occurrence of the last transient
fault does a self-stabilizing system guarantees the satisfaction of the task
requirement, for details see [2, 19].

###  1.4 Related work

In the context of reliable broadcast, there are (non-self-stabilizing)
Byzantine fault-tolerant (BFT) solutions [42, 9, 31, 1] and (non-BFT) self-
stabilizing solutions [36] (even for total order broadcast [36, 37, 35, 29]).
We focus on BT [17, 16] to which we propose a self-stabilizing variation. BT
is the basis for advanced BFT algorithms for solving consensus [40] and is
based on a simpler communication abstraction by Toueg that is called no-
duplicity broadcast [43]. It includes all of Definition 1.1’s requirements
except for BRB-Completion-2. Maurer and Tixeuil [39] consider an abstract that
is perhaps simpler than no-duplicity since they only consider no-duplicity
(and none of the other requirements of Definition 1.1). They provide a single-
instance synchronous self-stabilizing BFT broadcast, whereas we consider an
asynchronous repeated BRB that follows Definition 1.1, which is taken from
Raynal [42]. Raynal studies the exact power of all the essential communication
abstractions in the area of fault-tolerant message-passing systems. We study
the more useful definition provided by Raynal since we wish to connect our
solution to all relevant protocols in the area.

Our study focuses on the BT [17, 16] solution to which we propose a self-
stabilizing variation. BT is the basis for advanced BFT algorithms for solving
consensus, such as the one by Mostéfaoui and Raynal [40]. BT is based on a
simpler communication abstraction called no-duplicity broadcast (ND-broadcast)
by Toueg [43, 42]. It includes all of the above requirements except BRB-
Completion-2.

In the broader context of self-stabilizing BFT solutions for message-passing
systems, we find solutions for topology discovery [22], storage [14, 13, 12,
11, 10], clock synchronization [24, 34, 32], approximate agreement [15],
asynchronous unison [26], communication in dynamic networks [38] to name a
few. Also, BFT state-machine replication by Binun _et al._ [6, 7] for
synchronous systems and Dolev _et al._ [20] for practically-self-stabilizing
partially-synchronous systems.

Even though Doudou _et al._ consider the consensus problem while we consider
here repeated BRB, both works share the same motivation, _i.e.,_ circumventing
known impossibilities, _e.g.,_ the one by Fischer, Lynch, and Paterson [28].

###  1.5 Our contribution

We present a fundamental module for dependable distributed systems: SSBRB, a
self-stabilizing BFT reliable broadcast for asynchronous message-passing
systems, _i.e.,_ for the model of $\mathsf{BAMP_{n,t}[FC,t<n/3]}$. We obtain
this new self-stabilizing solution via a transformation of the non-self-
stabilizing BT algorithm [17, 16] while preserving BT’s resilience optimality
of $t<n/3$.

In the absence of transient-faults, our asynchronous solution for single-
instance BRB achieves operation completion within a constant number of
communication rounds. After the occurrence of the last transient-fault, the
system recovers eventually (while assuming execution fairness among the non-
faulty processes). The amount of memory used by the proposed algorithm is
bounded and the communication costs of the studied and proposed algorithms are
similar, _i.e.,_ $\mathcal{O}(n^{2})$ messages per BRB instance. The main
difference is that our solution unifies all the types of messages sent by BT
into a single message that is repeatedly sent. This repetition is imperative
since self-stabilizing systems cannot stop sending messages [19, Chapter 2.3].

Our contribution also includes a self-stabilizing BFT recycling mechanism for
time-free systems that are enriched with muteness detectors, _i.e.,_
$\mathsf{BAMP_{n,t}[FC,}$ $\mathsf{BML,\diamondsuit P_{mute}]}$. The mechanism
is based on an algorithm that counts communication rounds. Since individual
BRB-broadcasters increment the counter independently, the algorithm is named
the _independent round counter_ (IRC) algorithm. Implementing a self-
stabilizing BFT IRC is a non-trivial challenge since this counter should
facilitate an unbounded number of increments, yet it has to use only a
constant amount of memory. Using novel techniques for dealing with integer
overflow events, the proposed solution recovers from transient faults
eventually, uses a bounded amount of memory, and has communication costs of
$\mathcal{O}(n)$ messages per BRB instance.

To the best of our knowledge, we propose the first self-stabilizing BFT
solutions for the problems of IRC and repeated BRB (that follows BT’s problem
specifications [42, Ch. 4]). As said, BRB and IRC consider different fault
models. Section 2 defines $\mathsf{BAMP_{n,t}[FC,t<n/3]}$ and self-
stabilization. The non-self-stabilizing BT algorithm for
$\mathsf{BAMP_{n,t}[FC,t<n/3]}$ is studied in Section 3. Our self-
stabilization BFT variation on BT for $\mathsf{BAMP_{n,t}[FC,}$
$\mathsf{t<n/3]}$ is proposed in Section 4. IRC is presented in two steps. A
self-stabilizing IRC for time-free node-failure-free message-passing systems
appears in Section 6. In Section 7, we revise these time-free settings into
$\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$ and propose a self-
stabilizing BFT IRC. Section 8 compares the overhead of the studied and
proposed solutions when executing $\delta$ BRB instances concurrently. This
straightforward extension is imperative for the sake of practical deployments.

Our specifications (Definition 1.1) follow the ones by Raynal [42, Ch. 4].
Thus, our SSBRB solution can serve as a building block for multivalued
consensus [27].

For the reader’s convenience, we include a Glossary just before the section of
References.

##  2 System Settings for $\mathsf{BAMP_{n,t}[FC,t<n/3]}$

This work focuses on three fault models, _i.e.,_
$\mathsf{BAMP_{n,t}[FC,t<n/3]}$, which we present in this section, as well as
the fault model of $\mathsf{AMP_{n}[FC,BML]}$ and the fault model of
$\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$, which we present in
sections 6.2 and 7, respectively. The model considered in this section is for
asynchronous message-passing systems that have no guarantees on the
communication delay. Also, the algorithm cannot explicitly access the (local)
clock (or use timeout mechanisms). The system consists of a set,
$\mathcal{P}$, of $n$ fail-prone nodes (or processes) with unique identifiers.
Any pair of nodes $p_{i},p_{j}\in\mathcal{P}$ has access to a bidirectional
communication channel, $\mathit{channel}_{j,i}$, that, at any time, has at
most $\mathsf{channelCapacity}\in{Z}^{+}$ messages on transit from $p_{j}$ to
$p_{i}$ (this assumption is due to a known impossibility [19, Chapter 3.2]).

In the _interleaving model_ [19], the node’s program is a sequence of
_(atomic) steps_. Each step starts with an internal computation and finishes
with a single communication operation, _i.e.,_ a message $send$ or $receive$.
The _state_ , $s_{i}$, of node $p_{i}\in\mathcal{P}$ includes all of $p_{i}$’s
variables and all incoming communication channels,
$\mathit{channel}_{j,i}:p_{i},p_{j}\in\mathcal{P}$. The term _system state_
(or configuration) refers to the tuple $c=(s_{1},s_{2},\cdots,s_{n})$. We
define an _execution (or run)_ $R={c[0],a[0],c[1],a[1],\ldots}$ as an
alternating sequence of system states $c[x]$ and steps $a[x]$, such that each
$c[x+1]$, except for the starting one, $c[0]$, is obtained from $c[x]$ by
$a[x]$’s execution.

###  2.1 The fault model and self-stabilization

The _legal executions_ ($LE$) set refers to all the executions in which the
requirements of task $T$ hold. In this work, $T_{\text{BRB}}$ denotes the task
of BFT Reliable Broadcast, which Section 1 specifies, and the executions in
the set $LE_{\text{BRB}}$ fulfill $T_{\text{BRB}}$’s requirements.

####  2.1.1 Benign failures

A failure occurrence is a step that the environment takes rather than the
algorithm. When the occurrence of a failure cannot cause the system execution
to lose legality, _i.e.,_ to leave $LE$, we refer to that failure as a benign
one.

$\bullet$ _Communication failures and fairness._ We focus on solutions that
are oriented towards asynchronous message-passing systems and thus they are
oblivious to the time at which the packets depart and arrive. We assume that
any message can reside in a communication channel only for a finite period.
Also, the communication channels are prone to packet failures, such as loss,
duplication, and reordering. However, if $p_{i}$ sends a message infinitely
often to $p_{j}$, node $p_{j}$ receives that message infinitely often. We
refer to the latter as the _fair communication_ assumption. As in [30], we
assume that the communication channel from a correct node eventually includes
only messages that were transmitted by the sender.

The studied algorithm assumes reliable communication channels whereas the
proposed solution does not make any assumption regarding reliable
communications. Section 4.1.2 provides further details regarding the reasons
why the proposed solution cannot make this assumption.

$\bullet$ _Arbitrary node failures._ Byzantine faults model any fault in a
node including crashes, and arbitrary malicious behaviors. Here the adversary
lets each node receive the arriving messages and calculate their state
according to the algorithm. However, once a node (that is captured by the
adversary) sends a message, the adversary can modify the message in any way,
delay it for an arbitrarily long period or even omit it from the communication
channel. The adversary can also send fake messages, _i.e.,_ not according to
the algorithm. Note that the adversary has the power to coordinate such
actions without any computational (or communication) limitation. For the sake
of solvability [33, 41, 43], the fault model that we consider limits only the
number of nodes that can be captured by the adversary. That is, the number,
$t$, of Byzantine failures needs to be less than one-third of the number, $n$,
of nodes in the system, _i.e.,_ $3t+1\leq n$. The set of non-faulty indexes is
denoted by $\mathit{Correct}$, so that $i\in\mathit{Correct}$ when $p_{i}$ is
a correct node.

####  2.1.2 Arbitrary transient-faults

We consider any temporary violation of the assumptions according to which the
system was designed to operate. We refer to these violations and deviations as
_arbitrary transient-faults_ and assume that they can corrupt the system state
arbitrarily (while keeping the program code intact). The occurrence of a
transient fault is rare. Thus, we assume that the last arbitrary transient
fault occurs before the system execution starts [19]. Also, it leaves the
system to start in an arbitrary state.

###  2.2 Dijkstra’s self-stabilization

An algorithm is _self-stabilizing_ with respect to $LE$, when every execution
$R$ of the algorithm reaches within a finite period a suffix $R_{legal}\in LE$
that is legal. Namely, Dijkstra [18] requires $\forall R:\exists
R^{\prime}:R=R^{\prime}\circ R_{legal}\land R_{legal}\in
LE\land|R^{\prime}|\in{Z}^{+}$, where the operator $\circ$ denotes that
$R=R^{\prime}\circ R^{\prime\prime}$ is the concatenation of $R^{\prime}$ with
$R^{\prime\prime}$.

###  2.3 Wait-free guarantees and transient-faults recovery assuming seldom
fairness

Wait-free algorithms guarantee that operations (that were invoked by non-
failing nodes) always complete in the presence of asynchrony and $t$ faulty
nodes. Self-stabilizing algorithms sometimes assume that their executions are
fair [19]. That is, given a step $a$, we say that $a$ is _applicable_ to
system state $c$ if there exists system state $c^{\prime}$, such that $a$
leads to $c^{\prime}$ from $c$. We say that a system execution is _fair_ when
every step of a correct node that is applicable infinitely often is executed
infinitely often and fair communication is kept. This work assumes execution
fairness during the period in which the system recovers from the occurrence of
the last arbitrary transient fault. Since the occurrence of transient faults
is rare, only seldom do our fairness assumptions needed and just for the
period of recovery. The rest of the time, _i.e.,_ in the absence of transient
faults or after the recovery from them, the execution is assumed to be
arbitrary.

##  3 The non-self-stabilizing BT algorithm

Recall that the studied algorithm, BT [17, 16], is a BRB solution for
$\mathsf{BAMP_{n,t}[FC,t<}$ $\mathsf{n/3]}$. BT is based on a simpler
communication abstraction called no-duplicity broadcast (ND-broadcast) by
Toueg [43, 42]. The ND-broadcast task includes all of the BRB requirements
(Section 1.1) except BRB-Completion-2. We review BT after studying Toueg’s ND-
broadcast algorithm.

1

2

3operation $\mathsf{ndBroadcast}(m)$ do broadcast $\mathrm{INIT}(m)$;

4

5

6upon $\mathrm{INIT}(\mathit{mJ})$ first arrival from $p_{j}$ do broadcast
$\mathrm{ECHO}(j,\mathit{mJ})$;

7

8

9upon $\mathrm{ECHO}(\mathit{k},\mathit{mJ})$ arrival from $p_{j}$ begin

10 if  _$\mathrm{ECHO}(\mathit{k},\mathit{mJ})$ received from at least
$(n\mathit{+}t)/2$ nodes_ then

11 $\mathrm{ndDeliver}(j,\mathit{mJ})$;

12

13

14

Algorithm 1 non-self-stabilizing no-duplicity broadcast (ND-broadcast); code
for $p_{i}$.

15

16

17operation $\mathsf{brbBroadcast}(m)$ do broadcast $\mathrm{INIT}(m)$;

18

19

20upon $\mathrm{INIT}(\mathit{mJ})$ first arrival from $p_{j}$ do broadcast
$\mathrm{ECHO}(j,\mathit{mJ})$;

21

22

23upon $\mathrm{ECHO}(\mathit{k},\mathit{mJ})$ arrival from $p_{j}$ begin

24 if  _$\mathrm{ECHO}(\mathit{k},\mathit{mJ})$ received from at least
$(n\mathit{+}t)/2$ nodes $\land\;\mathrm{READY}(\mathit{k},\mathit{mJ})$ not
yet broadcast_ then broadcast $\mathrm{READY}(\mathit{k},\mathit{mJ})$ ;

25

26

27

28upon $\mathrm{READY}(\mathit{k},\mathit{mJ})$ arrival from $p_{j}$ begin

29

30 if  _$\mathrm{READY}(\mathit{k},\mathit{mJ})$ received from
$(t\mathit{+}1)$ nodes $\land$ $\mathrm{READY}(\mathit{k},\mathit{mJ})$ not
yet broadcast_ then broadcast $\mathrm{READY}(\mathit{k},\mathit{mJ})$;

31

32 if  _$\mathrm{READY}(\mathit{k},\mathit{mJ})$ received from at least
$(2t\mathit{+}1)$ nodes $\land\langle\mathit{k},\mathit{mJ}\rangle$ not yet
BRB-Delivered _ then brbDeliver $(\mathit{k},\mathit{mJ})$;

33

34

35

Algorithm 2 non-self-stabilizing Byzantine Reliable Broadcast (BRB); code for
$p_{i}$.

###  3.1 No-Duplicity Broadcast

Algorithm 1 brings Toueg’s solution for ND-broadcast [43]. Algorithm 2 assumes
that every correct node invokes ND-broadcast at most once. Node $p_{i}$
initiates the ND-broadcasts of $m_{i}$ by sending $\mathrm{INIT}(m_{i})$ to
all nodes (line 1). Upon this message’s first arrival to node $p_{j}$, it
disseminates the fact that $p_{i}$ has initiated $m$’s ND-broadcast by sending
$\mathrm{ECHO}(i,m)$ to all nodes (line 1). Upon this message arrival to
$p_{k}$ from more than $(n\mathit{+}t)/2$ different nodes, $p_{k}$ is ready to
ND-deliver $\langle i,m_{i}\rangle$ (line 1).

###  3.2 Byzantine Reliable Broadcast

As explained, we present the BT solution for BRB as an extension of Toueg’s
solution for ND-broadcast. Algorithm 2 satisfies the BRB requirements (Section
1.1) assuming $t<n/3$. Note that the line numbers of Algorithm 2 continue the
ones of Algorithm 1.

The first difference between the ND and BRB algorithms is in the consequent
clause of the if-statement in line 2, where ND-delivery of $\langle
j,m\rangle$ is replaced with the broadcast of $\mathrm{READY}(j,m)$. This
broadcast indicates that $p_{i}$ is ready to BRB-deliver $\langle j,m\rangle$
as soon as it receives sufficient support, _i.e.,_ the arrival of
$\mathrm{READY}(j,m)$, which tells that $\langle j,m\rangle$ can be BRB-
delivered. Note that BRB-no-duplicity protects Algorithm 2 from the case in
which $p_{i}$ broadcasts $\mathrm{READY}(j,m)$ while $p_{j}$ broadcasts
$\mathrm{READY}(j,m^{\prime})$, such that $m\neq m^{\prime}$.

The new part of the BRB algorithm (lines 2 to 2) includes two if-statements.
The first one (line 2) makes sure that every correct node receives
$\mathrm{READY}(j,m)$ from at least one correct node before BRB-delivering
$\langle j,m\rangle$. This is done via the broadcasting of
$\mathrm{READY}(j,m)$ as soon as $p_{i}$ received it from at least
$(t\mathit{+}1)$ different nodes (since $t$ of them can be Byzantine).

The second if-statement (line 2) makes sure that no two correct nodes BRB-
deliver different pairs (in the presence of plausibly fake
$\mathrm{READY}(j,{\operatorname{-}})$ messages sent by Byzantine nodes, where
the symbol ‘${\operatorname{-}}$’ stands for any legal value). That is, the
delivery of a BRB-broadcast is done only after the first reception of the pair
$\langle j,m\rangle$ from at least $(2t\mathit{+}1)$ (out of which at most $t$
are Byzantine). The receiver then knows that there are at least $t\mathit{+}1$
correct nodes that can make sure that the condition in line 2 holds eventually
for all correct nodes.

##  4 Self-stabilizing Byzantine-tolerant Single-instance BRB

Before proposing our solution (Section 4.2), we review the challenges that we
face when transforming the non-self-stabilizing BT algorithm [17, 16] into a
self-stabilizing one (Section 4.1).

###  4.1 Challenges and approaches

We analyze the behavior of the BT algorithm in the presence of transient-
faults. We clarify that our analysis is relevant only in the context of self-
stabilization since Bracha and Toueg do not consider transient-faults.

####  4.1.1 Dealing with memory corruption and desynchronized system states

Recall that transient faults can corrupt the system state in any manner (as
long as the program code remains intact). For example, memory corruption can
cause the local state to indicate that a certain message has already arrived
(line 2) or that a certain broadcast was already performed (line 2). This
means that some necessary messages will not be broadcast. This will result in
an indefinite blocking. The proposed solution avoids such a situation by
unifying all messages into a single $\mathrm{MSG}(\mathit{mJ})$, where the
field $\mathit{mJ}$ includes all the fields of the messages of Algorithm 2.

####  4.1.2 Datagram-based end-to-end communications

Algorithm 2 assumes reliable communication channels when broadcasting in a
quorum-based manner, _i.e.,_ sending the same message to all nodes and then
waiting for a reply from $n\mathit{-}f$ nodes. Next, we explain why, for the
sake of a simpler presentation, we choose not to follow this assumption. Self-
stabilizing end-to-end communications require a known bound on the capacity of
the communication channels [19, Chapter 3]. In the context of self-
stabilization and quorum systems, we must avoid situations in which
communicating in a quorum-based manner can lead to a contradiction with the
system assumptions. Dolev, Petig, and Schiller [23] explain that there might
be a subset of nodes that are able to complete many round-trips with a given
sender, while other nodes merely accumulate messages in their communication
channels. The channel bounded capacity implies that the system has to either
block or omit messages before their delivery. Thus, the proposed solution does
not assume access to reliable channels. Instead, communications are simply
repeated by the algorithm’s do-forever loop.

36

37

38types: $\texttt{brbMSG}:=\\{\texttt{init},\texttt{echo},\texttt{ready}\\}$;

39

40variables:
$msg[\mathcal{P}][\texttt{brbMSG}]:=[[\emptyset,\ldots,\emptyset]]$ /* most
recently sent/received message */

41$wasDelivered[\mathcal{P}]:=[\mathsf{False},\ldots,\mathsf{False}]$ /*
indicates whether the message was delivered */

42

43required interfaces: $\mathsf{txAvailable}()$ and $\mathsf{rxAvailable}(k)$

44

45provided interfaces: $\mathsf{recycle}(k)$ do
$\\{(msg[k],wasDelivered[k])\leftarrow([\emptyset,\emptyset,\emptyset],\mathsf{False})\\}$;

46

47

48$\mathsf{mrg}(\mathit{mJ},j)$ begin

49 foreach  _$s\in\emph{{brbMSG}},p_{k}\in\mathcal{P}$_ do

50 if  _$s\neq\emph{{init}}\lor$ $\nexists
s=\emph{{init}},(k,m),(k,m^{\prime})\in$
$(msg[j][s]\cup\mathit{mJ}[s]):m$$\neq$$m^{\prime}$_ then $msg[j][s]$
$\leftarrow$ $msg[j][s]\cup$ $\mathit{mJ}[s]$;

51

52

53

54

55operations:

56$\mathsf{brbBroadcast}(v)$ do {if $\mathsf{txAvailable}()$ then
$\mathsf{recycle}(i)$; $msg[i][\texttt{init}]\leftarrow\\{v\\}$}

57

58$\mathsf{brbDeliver}(k)$ begin

59 if  _$\exists m:(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m)\in
msg[\ell][\emph{{ready}}]}\\}|\land\mathsf{rxAvailable}(k)$_ then

60 $wasDelivered[k]\leftarrow wasDelivered[k]\land m\neq\bot$; return _$m$_

61 else return _$\bot$_ ;

62

63

64

65$\mathsf{brbWasDelivered}(k)$ do return _$wasDelivered[k]$_ ;

66

67

68do-forever begin

69

70

71 if  _$\exists{(j,m)\in msg[i][\emph{{echo}}]}:m\notin
msg[j][\emph{{init}}]\lor\exists{(j,m)\in
msg[i][\emph{{ready}}]}:\neg((n\mathit{+}t)/2$
$<|\\{p_{\ell}\in\mathcal{P}:(j,m)\in
msg[\ell][\emph{{echo}}]\\}|\lor(t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:(j,m)\in
msg[\ell][\emph{{ready}}]\\}|)$_ then

72 $\mathsf{recycle}(i)$

73

74 foreach  _$p_{k}\in\mathcal{P}$_ do

75

76 if  _$|msg[k][\emph{{init}}]|
>1\lor\exists{s\neq\texttt{init}}:\exists{p_{j}\in\mathcal{P}}:$
$\exists{(j,m),(j,m^{\prime})\in msg[k][s]}:$ $m\neq m^{\prime}$_ then
$msg[k][s]\leftarrow\emptyset$;

77

78 if  _$\exists{m\in msg[k][\emph{{init}}]}:msg[i][\emph{{echo}}]=\emptyset$_
then $msg[i][\texttt{echo}]\leftarrow\\{(k,m)\\}$;

79

80 if  _$\exists{m}:(n\mathit{+}t)/2 <|\\{p_{\ell}\in\mathcal{P}:(k,m)\in
msg[\ell][\emph{{echo}}]\\}|$_ then

81 $msg[i][\texttt{ready}]\leftarrow msg[i][\texttt{ready}]\cup\\{(k,m)\\}$

82

83 if  _$\exists m:(t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:(k,m)\in
msg[\ell][\emph{{ready}}]\\}|$_ then

84 $msg[i][\texttt{ready}]\leftarrow msg[i][\texttt{ready}]\cup\\{(k,m)\\}$

85

86

87 broadcast $\mathrm{MSG}(\mathit{brb}I=msg[i],$
$\mathit{irc}I=\mathsf{txMSG}())$;

88

89upon $\mathrm{MSG}(\mathit{brb}J,$ $\mathit{irc}J)$ arrival from $p_{j}$
begin

90 $\mathit{mrg}(\mathit{brb}J,j)$;

91 $\mathsf{rxMSG}(\mathit{brb}J,\mathit{irc}J,j)$

92

93

94

Algorithm 3 Self-stabilizing BFT BRB with instance recycling interface;
$p_{i}$’s code

###  4.2 Self-stabilizing BFT single-instance solution

Algorithm 3 proposes our SSBRB solution for $\mathsf{BAMP_{n,t}[FC,t<n/3]}$.
The key idea is to (i) offer a variance of Algorithm 2 that its operations
always complete even when starting from a corrected state, (ii) offer
interfaces for coordinating the recycling of a given BRB object, as well as
(iii) offer interfaces for accessing the delivered value and current status of
the broadcast. This way, the recycling coordination mechanism (Section 6 and
Section 7) can make sure that no BRB object is recycled before all correct
nodes deliver its result. Also, once all correct nodes have delivered a
message, the BRB object can be recycled eventually. The line numbers of
Algorithm 3 continue the ones of Algorithm 2. The boxed code fragments in
lines 3 to 3 are irrelevant to our single-instance BRB implementation.

####  4.2.1 Types, constants, variables, and message structure.

As mentioned, the message $\mathrm{MSG}()$ unifies the messages of Algorithm
2. The array $msg[][]$ stores both the information that is sent and arrived by
these messages. Specifically, $msg_{i}[i][]$ stores the information that node
$p_{i}$ broadcasts (line 3) and for any $j\neq i$ the entry $msg_{i}[j][]$
stores the information coming from $p_{j}$ (lines 3 to 3). Also, we define the
type $\texttt{brbMSG}:=\\{\texttt{init},\texttt{echo},\texttt{ready}\\}$ (line
3) for storing information related to BRB-broadcast messages, _e.g.,_
$msg_{i}[i][\texttt{init}]$ stores the information that BRB-broadcast
disseminates of $\mathrm{INIT}()$ messages and the results of the content of
$\mathrm{READY}()$ messages appear in $msg_{i}[i][\texttt{ready}]$.

####  4.2.2 Algorithm details.

The $\mathsf{brbBroadcast}(v)$ operation (line 3) allows Algorithm 3 to invoke
BRB-broadcast instances with $v$. Such an invocation causes Algorithm 3 to
follow the logic of the BRB solution presented by Algorithm 2 in lines 3 and 3
to 3. We note that our solution also includes consistency tests at line 3.

Figure 1: Integrating the BRB (Section 4), IRC (Section 6), and $\diamondsuit
P_{mute}$ (Section 7) protocols

####  4.2.3 Interfaces for coordinating the recycling of a given BRB object.

Recall that Algorithm 3 has an interface to a recycling mechanism of BRB
instances (Section 6). The interface between the proposed BRB and recycling
mechanism includes the $\mathsf{recycle}()$, $\mathsf{txAvailable}()$, and
$\mathsf{rxAvailable}()$ operations, see Figure 1 (the interface between IRC
and $\diamondsuit P_{mute}$ is irrelevant to Algorithm 3). The function
$\mathsf{recycle}_{i}(k)$ (line 3) lets the recycling mechanism locally reset
$msg_{i}[k][]$ with the notation $f_{i}()$ denoting that $p_{i}$ executes the
function $f()$. For the single-instance BRB (without recycling), define
$\mathsf{txAvailable}()$ and $\mathsf{rxAvailable}(k)$ (line 3) to return
$\mathsf{True}$. Note that we further integrate between BRB and IRC is via the
piggybacking of their messages.

####  4.2.4 Interfaces for accessing the delivered value and current status.

Algorithms 1 and 2 inform the application layer about message arrival by
raising the events of $\mathrm{ndDeliver}()$ (line 1), and respectively,
$\mathsf{brbDeliver}()$ (line 2). Our SSBFT BRB solution takes another
approach in which the application is pulling information from Algorithm 3 by
invoking the $\mathsf{brbDeliver}()$ operation (line 3), which returns $\bot$
(line 3) when no message is ready to be delivered. Otherwise, the arriving
message is returned (line 3). Note that once
$\mathsf{brbDeliver}_{i}(k):i,k\in\mathit{Correct}$ returns a non-$\bot$
value, $\mathsf{brbDeliver}_{i}(k)$ returns a non-$\bot$ value in all
subsequent invocations. For the sake of satisfying BRB-integrity (Definition
1.1) in a self-stabilizing manner, line 3 records the fact that the non-$\bot$
message was delivered at least once by storing $\mathsf{True}$ in
$wasDelivered_{i}[k]$. The application can access the value stored in
$wasDelivered_{i}[k]$ by invoicing $\mathsf{brbWasDelivered}_{i}(k)$ (line 3).

##  5 Correctness of Algorithm 3

Definition 5.1 defines the terms active nodes and consistent executions.
Theorem 5.1 shows that consistency is regained eventually. Then, we provide a
proof of completion (Theorem 5.2) before demonstrating the closure properties
(Theorem 5.3). The closure proof (Section 5.3) shows that the proposed
solution satisfies BRB task requirements (Definition 1.1). It is based on the
assumption that BRB objects are eventually recycled after their task was
completed (Section 1.1).

Definition 5.1 considers the if-statement conditions of lines 3 and 3, see
items (brb.i) and (brb.ii). Item (brb.iii) has similar considerations as the
ones of Item (brb.i) in the context of the sent messages.

######  Definition 5.1 (Active nodes and consistent executions of Algorithm
3).

We use the term _active_ for node $p_{i}\in\mathcal{P}$ when referring to the
case of $msg_{i}[i][\emph{{init}}]$ $\neq\emptyset$. Let $R$ be an Algorithm
3’s execution, $p_{i},p_{j}\in\mathcal{P}:i\in\mathit{Correct}$, and $c\in R$.
Suppose in $c$:

  * •

(brb.i) $|msg_{i}[j][\emph{{init}}]|\leq 1$ and
$\nexists_{t\in\\{\emph{{echo}},\emph{{ready}}\\}}$
$\exists_{p_{k}\in\mathcal{P}}$ $\exists_{(k,m),(k,m^{\prime})\in
msg_{i}[j][t]}$ $m\neq m^{\prime}$.

  * •

(brb.ii) $\forall_{(k,m)\in
msg_{i}[i][\emph{{ready}}]}((n\mathit{+}t)/2<|\\{p_{\ell}\in\mathcal{P}:(k,m)\in
msg_{i}[\ell][\emph{{echo}}]\\}|\lor(t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:(k,m)\in
msg_{i}[\ell][\emph{{ready}}]\\}|)$.

  * •

(brb.iii) for any message
$\mathsf{MSG}(\mathit{brb}J=\mathit{mJ},{\operatorname{-}})$ in transient from
$p_{i}$ to $p_{j}$, it holds that for any ${p_{k}\in\mathcal{P}}$ and
${t\neq\emph{{init}}}$ there are no $(k,m),(k,m^{\prime})\in
msg_{i}[j][t]\cup\mathit{mJ}[t]:m\neq m^{\prime}$.

In this case, we say that $c$ is consistent w.r.t. $p_{i}$. Suppose every
system state in $R$ is consistent w.r.t. $p_{i}$. In this case, we say that
$R$ is consistent w.r.t. $p_{i}$ and Algorithm 3.

Note the term active (Definition 5.1) does not distinguish between the cases
in which a node is active due to the occurrence of a transient fault and the
invocation of $\mathsf{brbBroadcast}(v)$.

###  5.1 Consistency regaining for Algorithm 3

######  Theorem 5.1 (Algorithm 3’s Convergence).

Let $R$ be a fair execution of Algorithm 3 in which
$p_{i}\in\mathcal{P}:i\in\mathit{Correct}$ is active eventually. The system
eventually reaches a state $c\in R$ that starts a consistent execution w.r.t.
$p_{i}$ (Definition 5.1).

Proof of Theorem 5.1 Suppose that $R$’s starting state is not consistent
w.r.t. $p_{i}$. Specifically, suppose that either invariant (brb.i) or
(brb.ii) does not hold. _I.e.,_ at least one of the if-statement conditions in
lines 3 and 3 holds. Since $R$ is fair, eventually $p_{i}$ takes a step that
includes the execution of lines 3 to 3, which assures that $p_{i}$ becomes
consistent with respect to (brb.i) and (brb.ii). Observe that once invariant
(brb.i) and (brb.ii) hold w.r.t. $p_{i}$ in $c$, they hold in any state
$c^{\prime}\in R$ that follows $c$, cf. lines 3 to 3 and 3 to 3.

Due to the above, the rest of the proof assumes, w.l.o.g., that all correct
nodes are consistent w.r.t. $p_{i}$, (brb.i), and (brb.ii) in any state of
$R$. Let $m$ be a message that in $R$’s starting state resides in a channel
between a pair of correct nodes. Recall that $m$ can reside in that channel
only for a finite time (Section 2.1.1). Thus, by the definition of complete
iterations, the system reaches a state in which $m$ does not appear in the
communication channels eventually. Thus, (brb.iii) holds eventually, since it
is sufficient to consider only messages that were sent during $R$ from nodes
in which (brb.i) and (brb.ii) hold.
$\Box_{Theorem~{}\ref{thm:recoveryconsensusI}}$

###  5.2 Completion of BRB-broadcast

######  Theorem 5.2 (BRB-Completion-1).

Let $typ\in\texttt{brbMSG}$ and $R$ be a consistent execution of Algorithm 3
in which $p_{i}\in\mathcal{P}$ is active. Eventually, $\forall
i,j\in\mathit{Correct}:\mathsf{brbDeliver}_{j}(i)\neq\bot$.

Proof of Theorem 5.2 Since $p_{i}$ is correct, it broadcasts
$\mathrm{MSG}(\mathit{brb}J=msg_{i}[i],{\operatorname{-}})$ infinitely often.
By fair communication, every correct $p_{j}\in\mathcal{P}$ receives
$\mathrm{MSG}(\mathit{brb}J)$ $=m,{\operatorname{-}})$ eventually. Thus,
$\forall j\in\mathit{Correct}:msg_{j}[i][\texttt{init}]=\\{m\\}$ due to line
3. Also, $\forall
j\in\mathit{Correct}:msg_{j}[j][\texttt{echo}]\supseteq\\{(i,m)\\}$ since node
$p_{j}$ obverses that the if-statement condition in line 3 holds (for the case
of $k_{j}=i$). Thus, $p_{j}$ broadcasts
$\mathrm{MSG}(\mathit{brb}J=msg_{j}[j],{\operatorname{-}})$ infinitely often.
By fair communication, every correct node $p_{\ell}\in\mathcal{P}$ receives
$\mathrm{MSG}(\mathit{brb}J,{\operatorname{-}})$ eventually. Thus, $\forall
j,\ell\in\mathit{Correct}:msg_{\ell}[j][\texttt{echo}]\supseteq\\{(i,m)\\}$
(line 3). Since $n\mathit{-}t>(n\mathit{+}t)/2$, node $p_{\ell}$ observes that
$(n\mathit{+}t)/2<|\\{p_{x}\in\mathcal{P}:(i,m)\in
msg_{\ell}[x][\texttt{echo}]\\}|$ holds, _i.e.,_ the if-statement condition in
line 3 holds, and thus, $msg_{\ell}[\ell][\texttt{ready}]\supseteq\\{(i,m)\\}$
holds. Note that, since $t<(n\mathit{+}t)/2$, faulty nodes cannot prevent a
correct node from broadcasting
$\mathrm{MSG}(\mathit{brb}J=\mathit{m}J,{\operatorname{-}}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(i,m)\\}$
infinitely often, say, by colluding and sending
$\mathrm{MSG}(\mathit{brb}J=\mathit{m}J,{\operatorname{-}}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(i,m^{\prime})\\}\land
m^{\prime}\neq m$. By fair communication, every correct $p_{y}\in\mathcal{P}$
receives $\mathrm{MSG}(\mathit{brb}J=\mathit{m}J,{\operatorname{-}})$
eventually. Thus, $\forall
j,y\in\mathit{Correct}:msg_{y}[j][\texttt{ready}]\supseteq\\{(i,m)\\}$ holds
(line 3). Therefore, whenever $p_{y}$ invokes $\mathsf{brbDeliver}_{y}(i)$
(line 3), the condition
$\exists_{m}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k_{y}=i,m)\in
msg_{y}[\ell][\texttt{ready}]}\\}|$ holds, and thus, $m$ is returned.
$\Box_{Theorem~{}\ref{thm:brbTerminateSimple}}$

###  5.3 Closure of BRB-broadcast

The main difference between the completion and the closure proofs is that the
latter considers post-recycled starting system states and complete invocation
of operations (Definition 5.2).

######  Definition 5.2 (Post-recycle system states and complete invocation of
operations).

We say that system state $c$ is _post-recycle_ w.r.t.
$p_{i}\in\mathcal{P}:i\in\mathit{Correct}$ if $\forall
j\in\mathit{Correct}:msg_{j}[i]=[\emptyset,\ldots,\emptyset]$ holds and no
communication channel from $p_{i}$ to $p_{j}$ includes
$\mathrm{MSG}(\mathit{brb}J\neq[\emptyset,\ldots,\emptyset],{\operatorname{-}})$.
Suppose that execution $R$ starts in the post-recycled system state $c$ and
$p_{i}$ invokes $\mathsf{brbBroadcast}_{i}(v)$ exactly once. In this case, we
say that $R$ includes a _complete BRB invocation_ w.r.t. $p_{i}$.

Note that a post-recycled system state (Definition 5.2) is also a consistent
one (Definition 5.1).

######  Theorem 5.3 (BRB closure).

Let $R$ be a post-recycled execution of Algorithm 3 in which all correct nodes
are active eventually via the complete invocation of BRB-broadcast. The system
demonstrates in $R$ a BRB construction.

Proof of Theorem 5.3 BRB-Completion-1 holds (Theorem 5.2).

######  Lemma 5.4 (BRB-Completion-2).

BRB-Completion-2 holds.

Proof of Lemma 5.4 By line 3, $p_{i}$ can BRB-deliver $m$ from $p_{j}$ only
once $\exists_{m}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m)\in
msg_{i}[\ell][\texttt{ready}]}\\}|$ holds. During post-recycled execution,
only lines 3 to 3 and 3 can add items to $msg_{i}[i][\texttt{ready}]$ and
$msg_{i}[\ell][\texttt{ready}]$, respectively. Let $\mathrm{MSG}(\mathit{mJ})$
be such that $\mathit{mJ}[\texttt{ready}]\supseteq\\{(j,m)\\}$. Specifically,
line 3 adds to $msg_{i}[\ell][\texttt{ready}]$ items according to information
in $\mathrm{MSG}(\mathit{mJ})$ messages coming from $p_{\ell}$. This means,
that at least $t+1$ distinct and correct nodes broadcast
$\mathrm{MSG}(\mathit{mJ})$ infinitely often. By fair communication and line
3, all correct nodes, $p_{x}$, eventually receive $\mathrm{MSG}(\mathit{mJ})$
from at least $t+1$ distinct nodes and make sure that
$msg_{x}[\ell][\texttt{ready}]$ includes $(j,m)$. Also, by line 3, we know
that $msg_{x}[x][\texttt{ready}]\supseteq\\{(j,m)\\}$, _i.e.,_ every correct
node broadcast $\mathrm{MSG}(\mathit{mJ})$ infinitely often. By fair
communication and line 3, all correct nodes, $p_{x}$, receive
$\mathrm{MSG}(\mathit{mJ})$ from at least $2t+1$ distinct nodes eventually,
because there are at least $n\mathit{-}t\geq 2t\mathit{+}1$ correct nodes.
This implies that
$\exists_{m}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m)\in
msg_{i}[\ell][\texttt{ready}]}\\}|$ holds (due to line 3). Hence, $\forall
i\in\mathit{Correct}:\mathsf{brbDeliver}_{i}(j)\notin\\{\bot,\text{\char
9\relax}\\}$. $\Box_{Lemma~{}\ref{thm:brbTerminateSimple2}}$

######  Lemma 5.5.

The BRB-integrity property holds.

Proof of Lemma 5.5 Suppose $\mathsf{brbDeliver}(k)=m\neq\bot$ holds in $c\in
R$. Also, (towards a contradiction)
$\mathsf{brbDeliver}(k)=m^{\prime}\notin\\{\bot,m\\}$ holds in $c^{\prime}\in
R$, where $c^{\prime}$ appears after $c$ in $R$. _I.e.,_
$\exists_{m}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m)\in
msg_{i}[\ell][\texttt{ready}]}\\}|$ in $c$ and
$\exists_{m^{\prime}}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m^{\prime})\in
msg_{i}[\ell][\texttt{ready}]}\\}|$ in $c^{\prime}$. For any
${i,j,k\in\mathit{Correct}}$ and any ${typ\in\texttt{brbMSG}}$ it holds that
$(k,m),(k,m^{\prime})\in msg_{i}[j][\texttt{ready}]$ (since $R$ is post-
recycle, and thus, consistent). Thus, $m=m^{\prime}$, cf. invariant (brb.iii).
Also, observe from the code of Algorithm 3 that no element is removed from any
entry $msg[][][]$ during consistent executions. This means that
$msg_{i}[\ell][\texttt{ready}]$ includes both $(k,m)$ and $(k,m^{\prime})$ in
$c^{\prime}$. However, this contradicts the fact that $c^{\prime}$ is
consistent. Thus, $c^{\prime}\in R$ cannot exist and BRB-integrity holds.
$\Box_{Lemma~{}\ref{thm:brbIntegrity}}$

######  Lemma 5.6 (BRB-validity).

BRB-validity holds.

Proof of Lemma 5.6 Let $p_{i},p_{j}:i,j\in\mathit{Correct}$. Suppose that
$p_{j}$ BRB-delivers message $m$ from $p_{i}$. The proof needs to show that
$p_{i}$ BRB-broadcasts $m$. In other words, suppose that the adversary, who
can capture up to $t$ (Byzantine) nodes, sends the “fake” messages of
$msg_{j}[j][\texttt{echo}]\supseteq\\{(i,m)\\}$ or
$msg_{j}[j][\texttt{ready}]\supseteq\\{(i,m)\\}$, but $p_{i}$, who is correct,
never invoked $\mathsf{brbBroadcast}(m)$. In this case, our proof shows that
no correct node BRB-delivers $\langle i,m\rangle$. This is because there are
at most $t$ nodes that can broadcast “fake” messages. Thus,
$\mathsf{brbDeliver}(k)$ (line 3) cannot deliver $\langle i,m\rangle$ since
$t<2t\mathit{+}1$, which means that the if-statement condition
$\exists_{m}(2t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:{(k,m)\in
msg_{i}[\ell][\texttt{ready}]}\\}|$ cannot be satisfied.
$\Box_{Lemma~{}\ref{thm:brbValidity}}$

######  Lemma 5.7 (BRB-no-duplicity).

Suppose $p_{i},p_{j}:i,j\in\mathit{Correct}$, BRB broadcast
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(k,m)\\}$,
and respect.,
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(k,m^{\prime})\\}$.
We have $m=m^{\prime}$.

Proof of Lemma 5.7 Since $R$ is post-recycle, there must be a step in $R$ in
which the element $(k,{\operatorname{-}})$ is added to
$msg_{x}[x][\texttt{ready}]$ for the first time during $R$, where
$p_{x}\in\\{p_{i},p_{j}\\}$. The correctness proof considers the following two
cases.

$\bullet$ Both $p_{i}$ and $p_{j}$ add $(k,{\operatorname{-}})$ due to line 3.
Suppose, towards a contradiction, that $m\neq m^{\prime}$. Since the if-
statement condition in line 3 holds for both $p_{i}$ and $p_{j}$, we know that
$\exists_{m}(n\mathit{+}t)/2<|\\{p_{\ell}\in\mathcal{P}:(k,m)\in
msg_{i}[\ell][\texttt{echo}]\\}|$ and
$\exists_{m^{\prime}}(n\mathit{+}t)/2<|\\{p_{\ell}\in\mathcal{P}:(k,m^{\prime})\in
msg_{j}[\ell][\texttt{echo}]\\}|$ hold. Since $R$ is post-recycle, this can
only happen if $p_{i}$ and $p_{j}$ received
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{echo}]\supseteq\\{(k,m)\\}$,
and respect.,
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{echo}]\supseteq\\{(k,m^{\prime})\\}$
from $(n\mathit{+}t)/2$ distinct nodes. Note that $\exists p_{x}\in Q_{1}\cap
Q_{2}:x\in\mathit{Correct}$, where
$Q_{1},Q_{2}\subseteq\mathcal{P}:|Q_{1}|,|Q_{2}|\geq
1\mathit{+}(n\mathit{+}t)/2$ (as in [42], item (c) of Lemma 3). But, any
correct node, $p_{x}$, has at most one element in
$msg_{x}[\ell][\texttt{echo}]$ (line 3) during $R$. Thus, $m=m^{\prime}$,
which contradicts the case assumption.

$\bullet$ There is $p_{x}\in\\{p_{i},p_{j}\\}$ that adds
$(k,{\operatorname{-}})$ due to line 3.  _I.e.,_
$\exists_{m^{\prime\prime}}(t\mathit{+}1)\leq|\\{p_{\ell}\in\mathcal{P}:(k,m^{\prime\prime})\in
msg[\ell][\emph{{ready}}]\\}|\land m^{\prime\prime}\in\\{m,m^{\prime}\\}$.
Since there are at most $t$ faulty nodes, $p_{x}$ received
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(k,m^{\prime\prime})\\}$
from at least one correct node, say $p_{x_{1}}$, which received
$\mathrm{MSG}(\mathit{mJ}):\mathit{mJ}[\texttt{ready}]\supseteq\\{(k,m^{\prime\prime})\\}$
from $p_{x_{2}}$, and so on. This chain cannot be longer than $n$ and it must
be originated by the previous case in which $(k,{\operatorname{-}})$ is added
due to line 3. Thus, $m=m^{\prime}$. $\Box_{Lemma~{}\ref{thm:brbDuplicity}}$
$\Box_{Theorem~{}\ref{thm:brbClousre}}$

##  6 Self-stabilizing Recycling in Time-free Message-passing Systems

Before proposing our self-stabilizing BFT algorithm for BRB instance recycling
(Section 7), we study a non-crash-tolerant yet self-stabilizing recycling
algorithm for time-free systems. Namely, as steppingstones towards a solution
for $\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$, we present the
_independent round counter_ (IRC) task and implement $\mathsf{txAvailable}()$
and $\mathsf{rxAvailable}(k)$ (Figure 1 and Algorithm 3).

When non-self-stabilizing node-failure-free systems are considered, the
operation $\mathsf{txAvailable}()$ and the operation $\mathsf{rxAvailable}(k)$
can be implemented using prevailing mechanisms for automatic repeat request
(ARQ), which uses unbounded counters. These mechanisms are often used for
guaranteeing reliable communications by letting the sender collect
acknowledgments from all receivers. Each message is associated with a unique
message number, which the sender obtains by adding one to the previous message
number after all acknowledgments arrived. From that point in time, the
previous message number is obsolete and can be recycled. For the case of self-
stabilizing node-failure-free systems, the challenge is to deal with integer
overflow events. Specifically, when an algorithm considers the counters to be
unbounded but the studied system has bounded memory, transient faults can
trigger integer overflow events. The solution presented here shows how to
overcome this challenge via our recycling technique and a mild synchrony
assumption.

###  6.1 Independent Round Counters (IRCs)

We consider $n$ independent counters, such that each counter, $cnt_{i}$, can
be incremented only by a unique node, $p_{i}\in\mathcal{P}$, via the
innovation of the $\mathsf{increment}_{i}()$ operation, which returns the new
round number or $\bot$ when the invocation is (temporarily) disabled. Suppose
$p_{i},p_{j}\in\mathcal{P}$ are correct. Every node $p_{j}\in\mathcal{P}$ can
fetch $cnt_{i}$’s value via the invocation of the $\mathsf{fetch}_{j}(i)$
operation, which returns the most recent and non-fetched $cnt_{i}$’s value or
$\bot$ when such value is currently unavailable. We define the _Independent
Round Counters_ (IRCs) task using the following requirements.

  * •

IRC-validity.  Suppose $p_{j}$ IRC-fetches $s$ from $cnt_{i}$. Then, $p_{i}$
had IRC-incremented $cnt_{i}$ to $s$.

  * •

IRC-integrity-1.  Let $S_{i,j}=(s_{0},\ldots,s_{x}):x<B$ be a sequence of
$p_{i}$’s round numbers that $p_{j}$ fetched—we are only interested in $B$
most recent ones, where $B$ is a predefined constant. It holds that $\forall
s_{y}\in S_{i,j}:y<B-1\implies s_{y}+1\bmod B=s_{y+1}$. In other words, no
correct node IRC-fetches a value more than once from the counter of any other
correct node (considering the $B$ most recent IRC-fetches).

  * •

IRC-integrity-2.  Correct nodes that IRC-fetch numbers from $cnt_{i}$ do so in
the order in which $cnt_{i}$ was incremented (considering the $B$ most recent
IRC-fetches).

  * •

IRC-preemption.  Suppose $p_{i}$ IRC-increments $cnt_{i}$ to $s$. IRC-
increment is (temporarily) disabled until all correct nodes have fetched $s$
from $p_{i}$’s counter.

  * •

IRC-completion.  Suppose all correct nodes, $p_{j}$, IRC-fetch $p_{i}$’s
counter infinity often. Node $p_{i}$’s IRC-increment is enabled infinity
often.

Note that any algorithm that solve the IRC task can implement the interface
functions $\mathsf{txAvailable}()$ and $\mathsf{rxAvailable}(k)$ by returning
$\mathsf{increment}()\neq\bot$ and $\mathsf{fetch}(k)\neq\bot$, respectively.

###  6.2 Time-free system settings for $\mathsf{AMP_{n}[FC,BML]}$

The IRC solution proposed in this section requires time-free system settings,
which we define by revising $\mathsf{BAMP_{n,t}[FC,t<n/3]}$ into
$\mathsf{AMP_{n}[FC,BML]}$. The latter model does not consider node failures
but includes Assumption 6.1, as we explain next.

Consider a scenario in which, due to a transient fault, $p_{i}$’s copy of its
round counter is smaller than $p_{j}$’s copy of $p_{i}$’s counter, say, by
$x\in\mathbb{Z}^{+}$, thus node $p_{i}$ will have to complete $x$ rounds
before $p_{j}$ could IRC-fetch a non-$\bot$ value. The proposed IRC algorithm
overcomes is challenge by following Assumption 6.1.

######  Assumption 6.1 (Bounded message lifetime, BML).

Let $R$ be an execution in which there is a correct node $p_{i}\in\mathcal{P}$
that repeatedly broadcasts the protocol messages and completes an unbounded
number of round-trips with every correct node, $p_{j}\in\mathcal{P}$, in the
system. Suppose that $p_{j}$ receives message $m(s)$ from $p_{i}$ immediately
before system state $c\in R$, where $s\in\mathbb{Z}^{+}$ is the round number.
We assume that $cur_{i}[i]-s\leq\lambda$ in $c$, where
$\lambda\in\mathbb{Z}^{+}:\mathsf{channelCapacity}<\lambda<B/6$ is a known
upper-bound, $\mathsf{channelCapacity}$ is defined in Section 2, and $B$ is
defined by line 4.

95

96constants:

97 $B$: a predefined bound on the integer size, say, $2^{64}-1$.

98

99

100variables:

101 $cur[\mathcal{P}],nxt[\mathcal{P}]=[[-1,-1],\ldots,[-1,-1]]$: a pair of
round numbers—one pair per system node, where $cur[i]$ is $p_{i}$’s current
round number and $nxt[i]$ is the next one. Also, $cur[j]$ and $nxt[j]$ store
the most recently received, and respectively, delivered round number from
$p_{j}$;

102

103 $lbl[\mathcal{P}]=[0,\ldots,0]$: labels corresponding to $cur[i]$, where
$lbl[j]$ stores the most recently received label from $p_{j}$.

104

105required interfaces: $\mathsf{recycle}(k)$, ${\mathsf{trusted}}()$,
${\mathsf{invoc}}()$, ${\mathsf{rtComp}}(j)$;

106

107provided interface:

108$\mathsf{txAvailable}()$ do {return _$\mathsf{increment}()\neq\bot$_}

109$\mathsf{rxAvailable}(k)$ do {return _$\mathsf{fetch}(k)\neq\bot$_}

110

111macro: $\mathsf{behind}(d,s,c)$ do {return _$s\in\\{x\bmod
B:x\in\\{c-d\lambda,\ldots,c\\}\\}$_}

112

113operation $\mathsf{increment}()$ begin

/* ${\mathsf{trusted}}()=\mathcal{P}$ for the non-crash-tolerant version */

114 if  _$cur[i]=-1\lor\exists j\in{\mathsf{trusted}}():\mathit{lbl}[j]\leq
2(\mathsf{channelCapacity}+1)$_ then

115 return _$\bot$_

116 else ${\mathsf{invoc}}()$; $cur[i]\leftarrow cur[i]+1\bmod B$;
$\mathsf{recycle}(j)$; return _$cur[i]$_ ;

117

118

119

120operation $\mathsf{fetch}(k)$ begin

121 if  _$\mathsf{behind}(1,cur[k],nxt[k])$_ then return _$\bot$_ ;

122 else {$nxt[k]\leftarrow cur[k]$; return _$nxt[k]$_};

123

124

125

126operation $\mathsf{txMSG}(j)$ {return
_$(\mathsf{True},cur[i],\mathit{lbl}[j])$_}

127

128operation
$\mathsf{rxMSG}(\mathit{brb}J,\mathit{irc}J=(\mathit{a}J,\mathit{s}J,\mathit{{\ell}J}),j)$
begin

129

130 if
_$\neg\mathit{aJ}\land\mathsf{behind}(2,cur[i],\mathit{sJ})\land\mathit{lbl}[j]=\mathit{\ell}J$_
then

131 {${\mathsf{rtComp}}(j)$;
$\mathit{lbl}[j]\leftarrow\min\\{B,\mathit{\ell}J+1\\}$; return }

132

133 if  _$\neg\mathsf{behind}(1,\mathit{sJ},cur[i])$_ then

134 {$cur[j]\leftarrow\mathit{sJ}$; $\mathsf{recycle}(j)$}

135

136 $\mathbf{send}~{}\mathrm{MSG}(\mathsf{False},nxt[j],\mathit{{\ell}J})$ to
$p_{j}$;

137

138

139

140do forever broadcast
$\mathrm{MSG}(\mathit{brb}I=msg[i],\mathit{irc}I=\mathsf{txMSG}())$;

141

142upon $\mathrm{MSG}(\mathit{brb}J,\mathit{irc}J)$ arrival from $p_{j}$ begin

143 $\mathit{mrg}(\mathit{brb}J,j)$;

144 $\mathsf{rxMSG}(\mathit{brb}J,\mathit{irc}J,j)$;

145

146

Algorithm 4 time-free IRC; code for $p_{i}$

###  6.3 Self-stabilizing IRC for $\mathsf{AMP_{n}[FC,BML]}$

Algorithm 4 presents a self-stabilizing solution for crash-free message-
passing systems. _I.e.,_ it assumes that all nodes are correct. Algorithm 4
makes sure that any node that had IRC-incremented its round counter defers any
further IRC-increments until all nodes have acknowledged the latest IRC-
increment. Note that the line numbers of Algorithm 4 continue the ones of
Algorithm 3. Also, the boxed code in lines 4 and 4 are irrelevant to the IRC
solution studied in this section. We remind that the implementation of
interface function $\mathsf{recycle}()$ (line 4) is provided by Algorithm 3,
line 3. Also, for this section, let us assume that
${\mathsf{trusted}}_{i}()=\mathcal{P}$.

####  6.3.1 Constants and variables

All integers used by Algorithm 4 have a maximum value, which we denote by $B$
(line 4) and require to be large, say, $2^{64}-1$. The arrays $cur[]$ and
$nxt[]$ (line 4) store a pair of round numbers. The entry $cur[i]$ is
$p_{i}$’s current round number and $nxt[i]$ is the next one. Also, $cur[j]$
and $nxt[j]$ store the most recently received, and respectively, delivered
round numbers from $p_{j}$. The array $lbl[]$ holds labels that correspond to
the number in $cur[i]$, where $lbl[j]$ is the most recently received label
from $p_{j}$ (line 4).

####  6.3.2 The $\mathsf{increment}()$ operation

This operation allows the caller to IRC-increment the value of its round
number modulo $B$. It also returns the new round number. However, if the
previous invocation has not finished, the operation is disabled and the $\bot$
value is returned. Line 4 tests whether the round number is ready to be
incremented. In detail, recall that in this section, we assume
${\mathsf{trusted}}_{i}()=\mathcal{P}$. Now line 4 checks whether this is the
first round, _i.e.,_ a round number of $-1$, or the previous round has
finished, _i.e.,_ the labels indicate that every node has completed at least
$2(\mathsf{channelCapacity}+1)$ round trip. By exchanging at least
$2(\mathsf{channelCapacity}+1)$ labels, the proposed solution overcomes packet
loss and duplication over non-FIFO channels, see [21] for a more efficient
variation on this technique.

####  6.3.3 The $\mathsf{fetch}(k)$ operation

This operation returns, exactly once, the most recently received round number.
Line 4 tests whether a new round number has arrived. If this is not the case,
then $\bot$ is returned. Otherwise, the value of the new round number is
returned (line 4). In detail, due to Assumption 6.1, immediately after the
arrival of message $m(s)$ to $p_{j}$ from $p_{i}$, the fact that
$s\notin\\{x\bmod B:x\in\\{c-1\lambda,\ldots,c\\}\\}$ holds implies that $s$
is newer than $cur_{j}[i]$. Thus, $p_{i}$ can use
$\mathsf{behind}_{i}(1,cur_{i}[k],nxt_{i}[k])$ (line 4) for testing the
freshness of the round number stored in $cur_{i}[k]$ w.r.t. $nxt_{i}[k]$. If
case the number is indeed fresh, $\mathsf{fetch}_{i}()$ updates $nxt_{i}[k]$
with the returned round number.

####  6.3.4 The $\mathsf{txMSG}()$ and $\mathsf{rxMSG}()$ operations

The operations $\mathsf{txMSG}()$ and $\mathsf{rxMSG}()$ let the sender, and
respectively the receiver, process messages. Algorithm 4 sends via the message
$MSG()$ two fields: $\mathit{brb}J$ and $\mathit{irc}J$, where the field
$\mathit{brb}J$ is related to Algorithm 3. Recall that when a message arrives
from $p_{j}$, the receiving-side adds the suffix $J$ to the field name,
_i.e.,_ $\mathit{brb}J$ and $\mathit{irc}J$. The field $\mathit{irc}J$ is
composed of the fields $ack$, which indicates whether acknowledge is required,
$seq$, which is the sender’s round number, and $lbl$, which, during legal
executions, is the corresponding label to $seq$ that the sender uses for the
receiver.

The operation $\mathsf{txMSG}()$ is used when the sender transmits a message
(line 4). It specifies that acknowledgment is required, _i.e.,_
$ack=\mathsf{True}$ as well as includes the sender’s current round number,
_i.e.,_ $cur[i]$, and the corresponding label that the sender uses for the
receiver $p_{j}\in\mathcal{P}$, _i.e.,_ $\mathit{lbl}[j]$.

The operation $\mathsf{rxMSG}()$ processes messages arriving either to the
sender or the receiver. On the sender-side, when an acknowledgment arrives
from receiver, $p_{j}$, the sender checks whether the arriving message has
fresh round number and label (line 4). In this case, the label is incremented
in order to indicate that at least one round trip was completed. In detail,
$p_{i}$ uses $\mathsf{behind}_{i}(2,cur_{i}[j],\mathit{sJ})$ for testing
whether the arriving round number, $\mathit{sJ}$, is fresh by asking whether
$\mathit{sJ}$ is not a member of the set
$\\{cur_{j}[i]-2\lambda,\ldots,cur_{j}[i]\\}$, see Assumption 6.1. As we will
see in the next paragraph, there is a need to take into account the receiver’s
test (line 4), which can cause a non-fresh value to be a member of the set
$\\{x\bmod B:x\in\\{c-2\lambda,\ldots,c\\}\\}$, but not the set $\\{x\bmod
B:x\in\\{c-\lambda,\ldots,c\\}\\}$.

On the receiver-side, $p_{i}$ uses
$\mathsf{behind}_{i}(1,\mathit{sJ},cur_{i}[j])$ to test whether a new round
number arrived, _i.e.,_ testing whether the arriving number, $\mathit{sJ}$, is
a member of $\\{cur_{j}[i]-2\lambda,\ldots,cur_{j}[i]\\}$. In this case, the
local round number is updated (line 4) and the interface function
$\mathsf{recycle}_{i}(j)$ is called (line 3). Note that whenever the receiver
gets a message, it replies (line 4). That acknowledgment specifies that no
further replies are required, _i.e.,_ $ack=\mathsf{False}$, as well as the
most recently delivered round number, _i.e.,_ $nxt[i]$, and label,
$\mathit{{\ell}J}$.

####  6.3.5 The do forever loop and message arrival

Note that the processing of messages (for sending and receiving) is along the
lines of Algorithm 3. The do forever loop broadcasts the message
$\mathrm{MSG}()$ to every node in the system (line 4). The operation
$\mathsf{txMSG}()$ is used for setting the value of the $\mathit{irc}J$ field.
Upon message arrival, the receiver passes the arriving values to
$\mathsf{rxMSG}()$ for processing (line 4).

###  6.4 Correctness of Algorithm 4

The proof is implied by Theorem 6.2.

######  Theorem 6.2.

Let $R$ be an Algorithm 4’s execution and $i\in\mathit{Correct}$. Suppose all
correct nodes, $p_{j}$, IRC-fetch $p_{i}$’s counter infinity often and $p_{i}$
invokes IRC-increment infinity often. $R$ eventually demonstrates an IRC
construction (Section 6.1).

Proof of Theorem 6.2

######  Lemma 6.3.

The system demonstrates IRC-completion in $R$ (Section 6.1).

Proof of Lemma 6.3 Recall that $p_{i}$’s IRC-increment is enabled whenever
$\mathsf{increment}_{i}()$ can return a non-$\bot$ value (line 4), where
$p_{i}$ is a correct node. Also, the return of a non-$\bot$ value implies that
the value of $cur_{i}[i]$ changes (line 4). Thus, towards a contradiction,
assume $cur_{i}[i]=s\geq 0$ holds in every system state of $R$. The following
arguments show the contradiction by demonstrating that, for any correct node
$p_{j}$, the if-statement condition in line 4 holds eventually for any
$p_{j}$’s reply $\mathrm{MSG}({\operatorname{-}},(\mathsf{False},\bullet))$
arriving to $p_{i}$. Note that once $p_{i}$ executes line 4 at least once for
every $p_{j}$, $\mathsf{increment}_{i}()$ is enabled since the if-statement in
line 4 does not hold. To show that the predicate
$\mathsf{behind}_{i}(2,cur_{i}[i],\mathit{sJ})$ holds, we note that $p_{i}$ is
a correct node that broadcasts
$\mathrm{MSG}({\operatorname{-}},(\mathsf{True},cur_{i}[i]=s,{\operatorname{-}}))$
infinitely often (line 4). Thus, every correct node $p_{j}$ receives
$\mathrm{MSG}({\operatorname{-}},(\mathsf{True},cur_{i}[i]=s,{\operatorname{-}}))$
infinitely often (due to the communication fairness assumption). In the system
state that immediately follows this message arrival (line 4), the if-statement
condition in line 4 holds, _i.e.,_ $\mathsf{behind}_{j}(1,s,cur_{j}[i])$
holds. By the assumption that $p_{j}$ invokes $\mathsf{fetch}_{j}(i)$
infinitely often, we know that the if-statement condition in line 4 eventually
holds. _I.e.,_ $\mathsf{behind}_{j}(1,cur_{j}[i],s^{\prime})$ and
$\mathsf{behind}_{i}(2,s,s^{\prime})$ hold, where $nxt_{j}[i]=s^{\prime}$ is
the value used when $p_{j}$ sends
$\mathrm{MSG}({\operatorname{-}},(\mathsf{False},nxt_{j}[i]=s^{\prime},{\operatorname{-}}))$
to $p_{i}$. Thus, once
$\mathrm{MSG}({\operatorname{-}},(\mathsf{False},\mathit{sJ}=s^{\prime},{\operatorname{-}}))$
arrives to $p_{i}$ the predicate
$\mathsf{behind}_{i}(2,cur_{i}[i]=s,\mathit{sJ}=s^{\prime})$ holds. The proof
of $\mathit{lbl}_{i}[j]=\mathit{\ell}J$ is by fixing the value of
$lbl_{i}[j]=\ell$ and observing that the values of the messages
$\mathrm{MSG}({\operatorname{-}},(\mathsf{True},cur_{i}[i]=s,\ell))$ from
$p_{i}$ to $p_{j}$ and
$\mathrm{MSG}({\operatorname{-}},(\mathsf{False},cur_{i}[i]=s,\ell))$ from
$p_{j}$ to $p_{i}$. $\Box_{Lemma~{}\ref{thm:nonSelfIRCnoCrashX}}$

######  Lemma 6.4.

Eventually, the system demonstrates IRC-validity in $R$ (Section 6.1).

Proof of Lemma 6.4 W.l.o.g. suppose $R$ is the suffix of execution
$R^{\prime}=R^{\prime\prime}\circ R$, such that $\mathsf{increment}_{i}()$
returns a non-$\bot$ value more than $2(\lambda+1)$ times during
$R^{\prime\prime}$. We show that IRC-validity holds in $R$. _I.e.,_ suppose a
correct node $p_{j}$ IRC-fetches $s$ in step $a_{j}\in R$ from $p_{i}$’s
counter. We show that $p_{i}$ had IRC-incremented $cnt_{i}$ to $s$ in step
$a_{i}$ that appears in $R$ before $a_{j}$. Suppose, towards a contradiction,
$\nexists a_{i}\in R^{\prime}$, yet $a_{j}$ returns $s\neq\bot$ from
$\mathsf{fetch}_{j}(i)$ when executing line 4.

The starting system state of $R^{\prime}$, the
$\mathit{irc}J.\mathit{{\ell}J}$ field of the messages in the communication
channels between $p_{i}$ and $p_{j}$ and the variables $lbl_{i}[j]$ and
$\mathit{{\ell}J}$ include at most $2(\mathsf{channelCapacity}+1)$ different
labels. Since $p_{i}$ does not change $cnt_{i}[i]$ before counting the
reception of more than $2(\mathsf{channelCapacity}+1)$ labels (line 4), during
the period in which $\mathsf{increment}_{i}()$ returns non-$\bot$ values at
least twice, the messages in the channels between $p_{i}$ and $p_{j}$ and
$p_{j}$’s variables do not include values that have not changed since the
starting system state of $R^{\prime}$. Thus, $p_{i}$ completes an unbounded
number of round-trips with $p_{j}$ with values that $p_{i}$ indeed sent.

Recall that $a_{j}$ returns $s\neq\bot$ from $\mathsf{fetch}_{j}(i)$ when
executing line 4. This can only happen when $cur_{j}[i]=s\neq\bot$. Node
$p_{j}$ assigns $s$ to $cur_{j}[i]:i\neq j$ only in line 4 when it processes a
message coming from the sender $p_{i}$. However, $p_{i}$ can assign $s$ to
$cur_{i}[i]$ only at line 4, _i.e.,_ $a_{i}$ exists. We clarify the last
argument: by $\mathsf{behind}()$’s definition (line 4), there could be at most
$2\lambda$ consecutive times in which $\mathsf{behind}(2,\bullet)$ holds in
the if-statement condition in line 4 and yet, $cur_{j}[i]$ has not changed
while $cur_{i}[i]$ has. $\Box_{Lemma~{}\ref{thm:nonSelfIRCnoCrashL}}$

######  Lemma 6.5.

Eventually, the system demonstrates in $R$ an IRC construction (Section 6.1).

Proof of Lemma 6.5 Recall that lemmas 6.3 and 6.4 demonstrate IRC-completion
and IRC-validity. Thus, w.l.o.g. we can assume that IRC-validity holds
throughout $R$.

IRC-preemption.  Suppose that there is a correct node, $p_{k}\in\mathcal{P}$,
that does not IRC-fetch $s$ from $p_{i}$’s round counter during $R$ even after
$a_{i}$ (in which $p_{i}$ IRC-increment $cnt_{i}$ to $s$). Also, let
$a^{\prime}_{i}$ be a step that appears in $R$ after $a_{i}$ and includes an
IRC-increment invocation by $p_{i}$. We show that $a_{i}$’s invocation returns
$\bot$, _i.e.,_ $a_{i}$’s invocation is disabled.

By the code of Algorithm 4, the fact that there is no step in $R$ in which
$\mathsf{fetch}_{k}(i)$ returns $s$ implies that $nxt_{k}[i]\neq s$ holds in
any system state during $R$ (line 4). Therefore, $p_{k}$ does not send
$\mathrm{MSG}((\mathsf{False},nxt[j]=s,{\operatorname{-}}),{\operatorname{-}})$
to $p_{i}$. This means that, as long as $seq_{i}[i]=s$, it holds that
$\mathit{lbl}[k]=0$. Also, as long as $seq_{i}[i]=s$, whenever $p_{i}$ invokes
$\mathsf{increment}_{i}()$, the if-statement condition in line 4 holds. Thus,
$\mathsf{increment}_{i}()$ returns $\bot$ in step $a^{\prime}_{i}$.

IRC-integrity-1.  Lines 4 to 4 implies that no correct node, $p_{i}$, can IRC-
fetch the same value twice from the counter of the same node, say, $p_{j}$.

IRC-integrity-2.  Suppose $p_{j}$ IRC-fetches $s^{\prime}$ from $p_{i}$’s
counter in step $a^{\prime}_{j}$ that appears in $R$ after $a_{j}$ (in which
$p_{j}$ IRC-fetches $s^{\prime}$). We show that $p_{i}$ IRC-incremented
$cnt_{i}$ to $s$ and then to $s^{\prime}$. Step $a^{\prime}_{i}$ appears in
$R$ after $a_{j}$ (IRC-preemption) and $a_{j}$ after $a_{i}$ (IRC-validity and
line 4). Note that $s\neq s^{\prime}$, (IRC-integrity-1) _i.e.,_ $a_{i}\neq
a^{\prime}_{i}$. By line 4, $s$ was IRC-incremented before $s^{\prime}$ when
considering the $B$ IRC-increments preceding $a^{\prime}_{i}$.
$\Box_{Lemma~{}\ref{thm:nonSelfIRCnoCrashM}}$
$\Box_{Theorem~{}\ref{thm:nonSelfIRCnoCrash}}$

##  7 Self-stabilizing Byzantine-Tolerance IRC via Muteness Detection

Algorithm 4 presents our self-stabilizing BFT recycling mechanism for
$\mathsf{BAMP_{n,t}[FC,t<n/3,BML,\diamondsuit P_{mute}]}$, which we obtain by
enriching $\mathsf{BAMP_{n,t}[FC,t<n/3,BML]}$ with $\diamondsuit P_{mute}$,
which is a detector for muteness failures that we define in Section 7.1.

The proposed solution includes the boxed code lines. Algorithm 4 lets $p_{i}$
restart the local state of the muteness detector via a call to
${\mathsf{invoc}}_{i}()$ (line 4). The algorithm uses
${\mathsf{rtComp}}_{i}(j)$ (line 4) for taking into account the completion of
a round-trip between $p_{i}$ and $p_{j}$. The correctness proof shows (Theorem
7.2) that this version of the algorithm can consider
${\mathsf{trusted}}_{i}()\subseteq\mathcal{P}$ due to the properties of
$\diamondsuit P_{mute}$ (Section 7.2).

###  7.1 Muteness Failures

Let us consider an algorithm, $Alg$, that attaches a round number,
$seq\in\mathbb{Z}^{+}$, to every message, $m(seq)$ that it sends. Suppose
there is a system state $c_{\tau}\in R$ after which $p_{j}$, stops forever
replying to $p_{i}$’s messages, $m(seq)$, where $p_{i},p_{j}\in\mathcal{P}$.
In this case, we say that $p_{j}$ is _mute_ to $p_{i}$ with respect to message
$m(seq)$. We clarify that a Byzantine node is not mute if it forever sends all
the messages required by $Alg$. For the sake of a simple presentation, we
assume that the syntax of $m(seq)$ corresponds to the syntax of a message
generated by $Alg$ (since, otherwise, the receiver may simply omit messages
with syntax errors). Naturally, the data load of those messages can be wrong.
Observe that the set of mute nodes also includes all crashed nodes.

###  7.2 Muteness Detection: Specifications of $\diamondsuit P_{mute}$

We deal with mute nodes via the use of the class $\diamondsuit P_{mute}$ of
muteness detectors. In the context of self-stabilization, one has to consider
the scenario in which the muteness detector suspects a node due to a transient
fault. Thus, the muteness detector has to be restarted from time to time. In
this work takes the approach in which one restart occurs at the start of a new
round.

Muteness Strong Completeness:  Eventually, every mute node is forever
suspected w.r.t. round number $s$ by every correct node (or the round number
changes).

Eventual Strong Accuracy:  Eventually, the system reaches a state $c_{\tau}\in
R$ in which no correct node is suspected.

###  7.3 Muteness Detection: our and related solutions in a nutshell

In the context of self-stabilizing Byzantine-free (crash-prone) systems,
Beauquier and Kekkonen-Moneta [5] and Blanchard _et al._ [8] implemented
perfect failure detectors, _i.e.,_ class $P$, by letting node $p_{i}$ to
suspect any node $p_{j}\in\mathcal{P}$ whenever $p_{i}$ was able to complete
$\Theta$ round-trips with other nodes in $\mathcal{P}$ but not with $p_{j}$,
where $\Theta$ is a predefined constant.

Since the studied fault model includes Byzantine failures, we cannot directly
borrow earlier proposals, such as the ones in [5, 8]. Consider, for example, a
Byzantine node that anticipates the sender’s messages and transmits
acknowledgments before the arrival of perceptive messages. Using this attack
of speculative acknowledgments, the adversity may accelerate the (false)
completion round-trips and let the unreliable failure-detector suspect non-
faulty nodes.

As we explain next, our solution relies on an assumption (Assumption 7.1),
which facilitates the defense against the above attacks that use speculative
acknowledgments. Specifically, when testing whether the $\Theta$ threshold has
been exceeded, $p_{i}$ ignores the round-trips that were completed with the
top $t$ nodes, say w.l.g. $p_{1},\ldots,p_{t}$, that had the highest number of
round-trips with $p_{i}$. Suppose w.l.g. that nodes
$p^{byz}_{n-t},\ldots,p^{byz}_{n-1}$ are captured by the adversary. On the one
hand, the adversary aims at letting $p^{byz}_{n-t},\ldots,p^{byz}_{n-1}$ to
rapidly complete round trips with $p_{i}$. While on the other hand, if any of
the nodes $p^{byz}_{n-t},\ldots,p^{byz}_{n-1}$ complete round trips with
$p_{i}$ faster than any of the nodes $p_{1},\ldots,p_{t}$ are ignored by
$p_{i}$ when testing whether the $\Theta$ threshold has been exceeded. In
other words, any adversarial strategy that lets any of the nodes
$p^{byz}_{n-t},\ldots,p^{byz}_{n-1}$ to complete more round trips with $p_{i}$
than the nodes $p_{1},\ldots,p_{t}$ cannot cause a “haste” muteness detection
of a correct node.

147

148constants:

149$B$: a predefined bound on the integer size, say, $2^{64}-1$.

150

151variables:

152$\mathit{rt}[\mathcal{P}\setminus\\{p_{i}\\}][\mathcal{P}\setminus\\{p_{i}\\}]$:
round trip counters, initially all entries are zero;

153

154

155interface functions:

156${\mathsf{invoc}}()$ do
{$\mathit{rt}\leftarrow[[0,\ldots,0],\ldots,[0,\ldots,0]]$} ;

157

158${\mathsf{rtComp}}(j)$ begin

159 foreach  _$p_{k}\in\mathcal{P}\setminus\\{p_{i},p_{j}\\}$_ do

160 $\mathit{rt}[k][j]\leftarrow\min\\{B,\mathit{rt}[k][j]+1\\}$

161 $\mathit{rt}[j]\leftarrow[0,\ldots,0]$;

162

163${\mathsf{trusted}}()$ do return
$\\{p_{j}\in\mathcal{P}:\Theta>\sum_{x\in\mathit{withoutTopItems}(t,j)}x\\}$
where $\\{\mathit{rt}[j][\ell]\\}_{p_{\ell}\in\mathcal{P}}$ is a multi-set
with all the values in $\mathit{rt}[j][]$ and $\mathit{withoutTopItems}(t,j)$
is the same multi-set after the removal of the top $t$ values;

164

Algorithm 5 Class $\diamondsuit P_{mute}$ detector; code for $p_{i}$

####  7.3.1 Muteness Detection: Implementation

As shown in Figure 1, Algorithm 5 does not send independent messages as it
merely provides three interface functions to Algorithm 4, _i.e.,_
${\mathsf{invoc}}()$, ${\mathsf{rtComp}}(j)$, and ${\mathsf{trusted}}()$. The
algorithm’s state is based on the array $\mathit{rt}[][]$ (line 5), which
stores the number of round trips that node $p_{i}$ has completed with $p_{j}$.
Note that $\mathit{rt}[][]$ counts separately the number of round-trips
$p_{i}$ and $p_{k}$ are able to complete during any period in which $p_{i}$
and $p_{j}$ are attempting to complete a single round-trip.

The function ${\mathsf{invoc}}()$ (line 5) nullifies the value of
$\mathit{rt}[][]$. We require that, every time $p_{i}$ has completed with
$p_{j}$, it calls the ${\mathsf{rtComp}}(j)$ (line 5). This function
increments, for every $p_{k}\in\mathcal{P}\setminus\\{p_{i},p_{j}\\}$, the
counter in $\mathit{rt}_{i}[k][j]$. Then, ${\mathsf{rtComp}}(j)$ assigns zero
to every entry in $\mathit{rt}_{i}[j]$. The function ${\mathsf{trusted}}()$
returns the set of unsuspected nodes. Its implementation relies on Assumption
7.1, which answers to the above challenge (Section 7.3). As a defense against
the above attacks that use speculative acknowledgment, $p_{i}$ ignores the top
$t$ round-trip counters when testing whether the $\Theta$ threshold has been
exceeded. The correctness proof of Algorithm 5 appears in Theorem 7.2.

######  Assumption 7.1.

Let $R$ be an execution in which there is a correct node $p_{i}\in\mathcal{P}$
that repeatedly broadcasts the protocol message $m(s):s\in\mathbb{Z}^{+}$ and
completes an unbounded number of round-trips of message $m(s)$ with every
correct node in the system. Let
$\mathit{rt}_{i,c}:\mathcal{P}\times\mathcal{P}\rightarrow Z^{+}$ be a
function that maps any pair of nodes $p_{j},p_{k}\in\mathcal{P}$ with the
number of round-trips that $p_{i}$ has completed with $p_{k}$ between system
states $c^{\prime}\in R$ and $c\in R$, where $c^{\prime}$ is the first system
state that immediately follows the last time $p_{i}$ has completed a round-
trip with $p_{j}$, or the start of $R$ (in case $p_{i}$ has not completed any
round trip with $p_{j}$ between $R$’s start and $c$). Let
$\sum_{x\in\mathit{withoutTopItems}_{i,c}(t,j)}x$ be the total number of round
trips that $p_{i}$ has completed until $c$ when excluding the top $t$ values
of $\mathit{rt}_{i,c}$ that have completed with $p_{i}$ the greatest number of
round-trips. We assume that if
$\Theta\leq\sum_{x\in\mathit{withoutTopItems}_{i,c}(t,j)}x$ then $p_{j}$ is
mute to $p_{i}$ w.r.t. $m(s)$, where $\Theta$ is a predefined constant.

######  Theorem 7.2.

Let $R$ be a legal execution of algorithms 4 and 5 that satisfies Assumption
7.1. The system demonstrates in $R$ a construction of class $\diamondsuit
P_{mute}$ muteness detector (Section 7.2).

Proof of Theorem 7.2 Let us consider the sequence of values of
$\mathit{rt}_{i}[j][k]$ in the different system states $c\in R$. Note that
this sequence is defined by the function $\mathit{rt}_{i,c}(k,j)$ (Assumption
7.1). Thus, by line 5, we kt,now that $j\in{\mathsf{trusted}}_{i}()$ if, and
only if, $\Theta\leq\sum_{x\in\mathit{withoutTopItems}_{i,c}(t,j)}x$. Let
$a_{i}\in R$ be a step in which $p_{i}$ invokes $\mathsf{increment}_{i}()$ and
thus calls ${\mathsf{invoc}}_{i}()$ (line 4). We demonstrate that the
$\diamondsuit P_{mute}$ class properties hold (Section 7.2).

Muteness strong completeness: We show that, eventually, every mute node,
$p_{m}\in\mathcal{P}$, is forever suspected w.r.t. round number $s$ by every
correct node (or the round number is not $s$). Suppose that the round number
is always $s$. By the proof of Lemma 6.3, $p_{i}$ will call
${\mathsf{rtComp}}_{i}(j)$ infinitely often (line 4). _I.e.,_ for every
correct node $p_{k}\in\mathcal{P}\setminus\\{p_{i},p_{j}\\}$, the value of
$\mathit{rt}_{i}[k][j]$ will reach the upper bound $B$ eventually. Since
$B(n/3)>\Theta$, eventually $p_{j}\notin{\mathsf{trusted}}_{i}()$ holds.

Eventual Strong Accuracy: We show that eventually, the system reaches a state
$c_{\tau}\in R$ in which every correct node, $p_{\ell}\in\mathcal{P}$, appears
in ${\mathsf{trusted}}_{i}()$. Since both $p_{i}$ and $p_{\ell}$ are correct,
we know that $p_{i}$ completes round-trips with $p_{\ell}$ infinitely often.
Whenever a round trip is completed, $p_{i}$ assigns $[0,\ldots,0]$ to
$\mathit{rt}_{i}[\ell]$ (due to lines 4 and 5) and the condition
$\Theta>\sum_{x\in\mathit{withoutTopItems}_{i}(t,\ell)}x$ (line 5) hold until
the next round trip completion (Assumption 7.1).
$\Box_{Theorem~{}\ref{thm:MFD}}$

##  8 Discussion

To the best of our knowledge, this paper presents the first SSBFT algorithms
for IRC and repeated BRB (that follows Definition 1.1) for hybrid
asynchronous/time-free systems. As in BT, the SSBFT BRB algorithm takes
several asynchronous communication rounds of $\mathcal{O}(n^{2})$ messages per
instance whereas the IRC algorithm takes $\mathcal{O}(n)$ messages but
requires synchrony assumptions.

The two SSBFT algorithms are integrated via specified interfaces and message
piggybacking (Fig. 1). Thus, our SSBFT repeated BRB solution increases BT’s
message size only by a constant per BRB, but the number of messages per
instance stays similar. The integrated solution can run an unbounded number of
(concurrent and independent) BRB instances. The advantage is that the more
communication-intensive component, _i.e.,_ SSBFT BRB, is not associated with
any synchrony assumption. Specifically, one can run $\delta$ concurrent BRB
instances, where $\delta$ is a parameter for balancing the trade-off between
fault recovery time and the number of BRB instances that can be used (before
the next $\delta$ concurrent instances can start). The above extension
mitigates the effect of the fact that, for the repeated BRB problem, muteness
detectors are used and mild synchrony assumptions are made in order to
circumvent well-known impossibilities, _e.g.,_ [28]. Those additional
assumptions are required for the entire integrated solution to work. To the
best of our knowledge, there is no proposal for a weaker set of assumptions
for solving the studied problem in a self-stabilizing manner.

We note that the above extension facilitates the implementation of FIFO-
ordered delivery SSBFT repeated BRB. Here, each of the $\delta$ instances is
associated with a unqiue label $\ell\in\\{0,\ldots,\delta-1\\}$. The
implementation makes sure that no node $p_{i}$ delivers a BRB message with
label $\ell>0$ before all the BRB messages with labels in
$\\{0,\ldots,\ell-1\\}$. (For the case of $\ell=0$, the delivery is
unconditional.)

We hope that the proposed solutions, _e.g.,_ the proposed recycling mechanism
and the hybrid composition of time-free/asynchronous system settings, will
facilitate new SSBFT building blocks.

Acknowledgments.  We are grateful for the comments made by anonymous reviewers
that helped to improve the presentation of this article.

##  9 Glossary

For the reader’s convenience, we provide the following list of abbreviations.

  * •

AMP a fault model for asynchronous message-passing systems.

  * •

BAMP a fault model for Byzantine asynchronous message-passing systems.

  * •

BFT the design criteria of Byzantine fault-tolerant.

  * •

BML a synchrony assumption about bounded message lifetime, $\lambda$.

  * •

BRB the problem of Byzantine Reliable Broadcast.

  * •

BT the studied non-self-stabilizing BFT algorithm by Bracha and Toueg [17,
16].

  * •

FC the fault model-related assumption about fair communications.

  * •

IRC the problem abstraction of independent round counter, which is used for
implementing the proposed BRB-instance recycling for repeated BRB.

  * •

RB the problem of Reliable Broadcast.

  * •

SSBFT self-stabilizing Byzantine fault-tolerant.

  * •

$n$ number of nodes in the system.

  * •

$t$ an upper bound on the number of faulty nodes.

  * •

$\mathsf{channelCapacity}$ an upper bound on the number of messages in any
give communication channel.

  * •

$\delta$ a constant of concurrent BRB instances.

  * •

$\lambda$ a bound on the BML lifetime.

  * •

$\diamondsuit P_{mute}$ a class of mute failure detectors.

## References

  * [1] Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani.  Byzantine-tolerant reliable broadcast in the presence of silent churn.  In SSS, volume 13046 of LNCS, pages 21–33. Springer, 2021\.
  * [2] Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit.  Introduction to Distributed Self-Stabilizing Algorithms.  Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2019.
  * [3] Anish Arora and Mohamed G. Gouda.  Closure and convergence: A formulation of fault-tolerant computing.  In FTCS, pages 396–403. IEEE Computer Society, 1992.
  * [4] Alex Auvolat, Michel Raynal, and François Taïani.  Byzantine-tolerant set-constrained delivery broadcast.  In OPODIS, volume 153 of LIPIcs, pages 6:1–6:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [5] Joffroy Beauquier and Synnöve Kekkonen-Moneta.  Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabilizing failure detectors.  Int. J. Systems Science, 28(11):1177–1187, 1997.
  * [6] Alexander Binun, Thierry Coupaye, Shlomi Dolev, Mohammed Kassi-Lahlou, Marc Lacoste, Alex Palesandro, Reuven Yagel, and Leonid Yankulin.  Self-stabilizing Byzantine-tolerant distributed replicated state machine.  In Stabilization, Safety, and Security of Distributed Systems SSS’16, pages 36–53, 2016.
  * [7] Alexander Binun, Shlomi Dolev, and Tal Hadad.  Self-stabilizing Byzantine consensus for blockchain.  In Cyber Security Cryptography and Machine Learning CSCML’19, pages 106–110, 2019.
  * [8] Peva Blanchard, Shlomi Dolev, Joffroy Beauquier, and Sylvie Delaët.  Practically self-stabilizing Paxos replicated state-machine.  In NETYS, volume 8593 of LNCS, pages 99–121. Springer, 2014\.
  * [9] Silvia Bonomi, Jérémie Decouchant, Giovanni Farina, Vincent Rahli, and Sébastien Tixeuil.  Practical Byzantine reliable broadcast on partially connected networks.  In ICDCS, pages 506–516. IEEE, 2021.
  * [10] Silvia Bonomi, Shlomi Dolev, Maria Potop-Butucaru, and Michel Raynal.  Stabilizing server-based storage in Byzantine asynchronous message-passing systems.  In ACM Principles of Distributed Computing, PODC’15, pages 471–479, 2015.
  * [11] Silvia Bonomi, Maria Potop-Butucaru, and Sébastien Tixeuil.  Stabilizing Byzantine-fault tolerant storage.  In IEEE Parallel and Distributed Processing Symposium, IPDPS’15, pages 894–903, 2015.
  * [12] Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien Tixeuil.  Optimal mobile Byzantine fault tolerant distributed storage.  In ACM Principles of Distributed Computing, PODC’16, pages 269–278, 2016.
  * [13] Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien Tixeuil.  Optimal storage under unsynchronized mobile Byzantine faults.  In IEEE Reliable Distributed Systems, SRDS’17, pages 154–163, 2017.
  * [14] Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien Tixeuil.  Optimal self-stabilizing mobile Byzantine-tolerant regular register with bounded timestamps.  In Stabilization, Safety, and Security of Distributed Systems, SSS’18, pages 398–403, 2018.
  * [15] Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien Tixeuil.  Approximate agreement under mobile Byzantine faults.  Theor. Comput. Sci., 758:17–29, 2019.
  * [16] Gabriel Bracha and Sam Toueg.  Resilient consensus protocols.  In PODC, pages 12–26. ACM, 1983.
  * [17] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  J. ACM, 32(4):824–840, 1985.
  * [18] Edsger W. Dijkstra.  Self-stabilizing systems in spite of distributed control.  Commun. ACM, 17(11):643–644, 1974.
  * [19] Shlomi Dolev.  Self-Stabilization.  MIT Press, 2000.
  * [20] Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis, and Elad Michael Schiller.  Self-stabilizing Byzantine tolerant replicated state machine based on failure detectors.  In Cyber Security Cryptography and Machine Learning - Second International Symposium CSCML’18, pages 84–100, 2018.
  * [21] Shlomi Dolev, Ariel Hanemann, Elad Michael Schiller, and Shantanu Sharma.  Self-stabilizing end-to-end communication in (bounded capacity, omitting, duplicating and non-fifo) dynamic networks - (extended abstract).  In SSS, volume 7596 of LNCS, pages 133–147. Springer, 2012\.
  * [22] Shlomi Dolev, Omri Liba, and Elad Michael Schiller.  Self-stabilizing Byzantine resilient topology discovery and message delivery.  In Networked Systems NETYS’13, pages 42–57, 2013.
  * [23] Shlomi Dolev, Thomas Petig, and Elad Michael Schiller.  Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks.  CoRR, abs/1806.03498, 2018.
  * [24] Shlomi Dolev and Jennifer L. Welch.  Self-stabilizing clock synchronization in the presence of Byzantine faults.  In ACM Principles of Distributed Computing PODC’95, page 256, 1995.
  * [25] Assia Doudou, Benoît Garbinato, Rachid Guerraoui, and André Schiper.  Muteness failure detectors: Specification and implementation.  In EDCC, volume 1667 of LNCS, pages 71–87. Springer, 1999\.
  * [26] Swan Dubois, Maria Potop-Butucaru, Mikhail Nesterenko, and Sébastien Tixeuil.  Self-stabilizing Byzantine asynchronous unison.  J. Parallel Distributed Comput., 72(7):917–923, 2012.
  * [27] Romaric Duvignau, Michel Raynal, and Elad Michael Schiller.  Self-stabilizing Byzantine- and intrusion-tolerant consensus.  CoRR, abs/2110.08592, 2021.
  * [28] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson.  Impossibility of distributed consensus with one faulty process.  J. ACM, 32(2):374–382, 1985.
  * [29] Chryssis Georgiou, Oskar Lundström, and Elad Michael Schiller.  Self-stabilizing snapshot objects for asynchronous failure-prone networked systems.  CoRR, 2019.
  * [30] Chryssis Georgiou, Ioannis Marcoullis, Michel Raynal, and Elad Michael Schiller.  Loosely-self-stabilizing Byzantine-tolerant binary consensus for signature-free message-passing systems.  In Networked Systems - 9th International Conference, NETYS, volume 12754 of LNCS, pages 36–53. Springer, 2021.
  * [31] Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh.  Dynamic Byzantine reliable broadcast.  In OPODIS, volume 184 of LIPIcs, pages 23:1–23:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [32] Pankaj Khanchandani and Christoph Lenzen.  Self-stabilizing Byzantine clock synchronization with optimal precision.  Theory Comput. Syst., 63(2):261–305, 2019.
  * [33] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease.  The Byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.
  * [34] Christoph Lenzen and Joel Rybicki.  Self-stabilising Byzantine clock synchronisation is almost as easy as consensus.  J. ACM, 66(5):32:1–32:56, 2019.
  * [35] Oskar Lundström, Michel Raynal, and Elad M Schiller.  Self-stabilizing multivalued consensus in asynchronous crash-prone systems.  In 2021 17th European Dependable Computing Conference (EDCC), pages 111–118. IEEE, 2021.
  * [36] Oskar Lundström, Michel Raynal, and Elad Michael Schiller.  Self-stabilizing uniform reliable broadcast.  In NETYS, volume 12129 of LNCS, pages 296–313. Springer, 2020.
  * [37] Oskar Lundström, Michel Raynal, and Elad Michael Schiller.  Self-stabilizing indulgent zero-degrading binary consensus.  In Distributed Computing and Networking, ICDCN’21, pages 106–115, 2021.
  * [38] Alexandre Maurer.  Self-stabilizing Byzantine-resilient communication in dynamic networks.  In OPODIS, volume 184 of LIPIcs, pages 27:1–27:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [39] Alexandre Maurer and Sébastien Tixeuil.  Self-stabilizing Byzantine broadcast.  In 33rd IEEE International Symposium on Reliable Distributed Systems, SRDS 2014, Nara, Japan, October 6-9, 2014, pages 152–160, 2014.
  * [40] Achour Mostéfaoui and Michel Raynal.  Intrusion-tolerant broadcast and agreement abstractions in the presence of Byzantine processes.  IEEE Trans. Parallel Distributed Syst., 27(4):1085–1098, 2016\.
  * [41] Marshall C. Pease, Robert E. Shostak, and Leslie Lamport.  Reaching agreement in the presence of faults.  J. ACM, 27(2):228–234, 1980.
  * [42] Michel Raynal.  Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach.  Springer, 2018.
  * [43] Sam Toueg.  Randomized Byzantine agreements.  In Proceedings of the Third Annual ACM Principles of Distributed Computing, Vancouver, B. C., Canada, August 27-29, 1984, pages 163–178, 1984.