JAIST Repository
https://dspace.jaist.ac.jp/

Title

Tight Bound on Mobile Byzantine Agreement

Author(s)Nguyen, Thanh Dang; Bonnet, Francois; Defago,
Xavier; Potop‑Butucaru, Maria

Citation

Research report (School of Information Science,
Japan Advanced Institute of Science andTechnology), IS‑RR‑2014‑004: 1‑19

Issue Date

2014‑07‑29

TypeTechnical Report

Text version

publisher

URL

http://hdl.handle.net/10119/12203

RightsDescription

リサーチレポート（北陸先端科学技術大学院大学情報科学研究科）

Japan Advanced Institute of Science and Technology

Tight Bound on Mobile Byzantine Agreement
Thanh Dang Nguyen⋆
François Bonnet⋆
Maria Potop-Butucaru†

Xavier Défago⋆⋆†

School of Information Science, JAIST, Japan
Université Pierre & Marie Curie (UPMC) – Paris 6, France
Abstract

This paper investigates the problem of Byzantine Agreement in a synchronous
system where malicious agents can move from process to process, corrupting their
host. Earlier work on the problem are based on biased models which, as we argue
in the paper, give an unfair advantage either to the correct processes or to theadversary controlling the malicious agents.
Indeed, the earlier studies of the problem assume that, after a malicious agent
has left a process, that process, said to be cured, is able to instantly and accurately
detect the fact that it was corrupted in earlier rounds, and thus can take local
actions to recover a valid state (Garay’s model). We found no justification for thatassumption which clearly favors correct processes. Under that model, an algorithm
is known for n > 4t, where n is the number of processes and t the maximum numberof malicious agents. The tightness of the bound is unknown.
In contrast, more recent work on the problem remove the assumption on detection and assume instead that a malicious agent may have left corrupted messages
in the send queue of a cured process. As a result, the adversary controlling themalicious agents can corrupt the messages sent by cured processes, as well as thosesent by the newly corrupted ones, thus doubling the number of eﬀective faults.
Under that model, which favors the malicious agents, the problem can be solved if
and only if n > 6t.
In this paper, we refine the latter model to avoid the above biases. While a cured
process may send messages (based on a state corrupted by the malicious agent),
it will behave correctly in the way it sends those messages: i.e., send messages
according to the algorithm. Surprisingly, in this model we could derive a new
non-trivial tight bound for Byzantine Agreement. We prove that at least 5t + 1
processors are needed in order to tolerate t mobile Byzantine agents and provide
a time optimal algorithm that matches this lower bound, altogether with a formal
specification of the problem.

1

Introduction

New emergent distributed systems such as P2P, overlay networks, social networks or
clouds are inherently vulnerable to faults, insider attacks, or viruses. Faults and attacks

cannot be predicted accurately, may aﬀect diﬀerent parts of a system, and may occur
at any moment of its execution. In this work, we investigate the case where transientstate corruptions, which can be abstracted as malicious “agents,” can move throughthe network and corrupt the nodes they occupy. This models the situation where, assoon as a faulty node is repaired (e.g., by software rejuvenation), another one becomescompromised. For more than two decades, the main case study problem in this context
was Byzantine Agreement. Briefly stated, it requires processors, some of which malicious,that start the computation with an initial value to decide on the same value. When faults
are mobile the problem is known as Mobile Byzantine Agreement and requires special
attention for preserving agreement once it has been reached.
Related work. Byzantine Agreement, introduced by Lamport et al. [11, 15], has beenstudied for decades in static distributed systems under diﬀerent aspects (e.g., possibility,
complexity, cost) in various models (from synchronous [11, 15, 16] to asynchronous [4, 12],from authenticated [7] to anonymous [13]) with diﬀerent methodologies (deterministic[11,15], probabilistic [2,8]). In all these works, faults are stationary. That is, they do notchange their original location during the computation.
Santoro et al. [18, 19], and later Schmid et al. [21], investigate the agreement problem
in dynamic transmission failure models for both complete and arbitrary networks. Thesemodels assume that diﬀerent communication links may randomly fail at diﬀerent times.
Santoro and Widmayer [18] study the k-agreement problem, where the system reaches
a k-agreement if, in finite time, k processes choose the same value, either 0 or 1, withk > ⌈n/2⌉,1 where n is the total number of processes.
Based on the bivalent argument of Fischer et al. [9], they state that (⌈n/2 + 1⌉)agreement is impossible in a synchronous system if at each time there is one processor
whose messages may be corrupted. Although not explicitly stated, the impossibility
applies to the mobile Byzantine model. Thus, work on Mobile Byzantine Agreement
typically rely on the assumption that at least one process remains uncorrupted for Ω(n)rounds of communication.
Mobile Byzantine Agreement, introduced by Reischuk [17], has regained much attention recently. Research on the problem, in synchronous systems, follows two main
directions: constrained or unconstrained mobility.
Constrained mobility. This direction, studied by Buhrman et al. [3], considers thatmalicious agents move from one node to another only when protocol messages are sent(similar to how viruses would propagate). In that model, they prove a tight bound for
Mobile Byzantine Agreement (n > 3t, where t is the maximal number of simultaneously
faulty processes) and propose a time optimal protocol that matches this bound.
Unconstrained mobility. In this direction, which includes the work in this paper, themobility of malicious agents is not constrained by message exchanges [1, 10, 14, 17, 20].
Reischuk [17] proposed a first sub-optimal solution under an additional hypothesis on
the stability/stationarity of malicious agents for a given period of time. Later, Ostrovsky and Yung [14] introduced the notion of an adversary that can inject and distribute
faults in the system at a constant rate in every round and proposed solutions (mixing
randomization and self-stabilization) for tolerating the attacks of mobile viruses. Then,
1

If k ≤ ⌈n/2⌉ the k-agreement problem is trivial.

2Garay [10] and, more recently, Banu et al. [1] and Sasaki et al. [20] consider, in theirmodel, that processes execute synchronous rounds composed of three phases: send, receive, compute. Between two consecutive rounds, malicious agents can move from one
host to another, hence the set of faulty processes has a bounded size although its membership can change from one round to the next. Garay’s model is particular in that, aprocess has a limited ability to detect its own infection after the fact. More precisely,
during the first round following the leave of the malicious agent, a process enters a state,called cured, during which it can take preventive actions to avoid sending messages thatare based on a corrupted state. Under this assumption, Garay [10] proposes an algorithm
that solves Mobile Byzantine Agreement provided that n > 6t.
Notice that Garay’s model advantages the cured processes since they have the possibility of miraculously detecting the leave of malicious agents. In the same model, Banu
et al. [1] propose a Mobile Byzantine Agreement algorithm for n > 4t. However, to thebest of our knowledge, the tightness of the bound remains an open question.
Sasaki et al. [20] investigate the problem in a diﬀerent model where processes do nothave this ability to detect when malicious agents move. This is similar to our modelwith the subtle diﬀerence that cured processes have no control on the messages they
send. That is, messages are computed in the previous round (i.e., when the process was
still faulty) and the cured process cannot control the buﬀer where these messages are
stored, even though the process is no longer faulty. It follows that a cured process may
behave as a malicious one for one additional round. They propose tight bounds for Mobile
Byzantine Agreement in arbitrary networks if n > 6t and the degree of the network isd > 4t. This work extends the tight bounds (n > 3t and d > 2t) for Byzantine Agreementof Dolev [6] in arbitrary networks with static faults.
Motivation. Analyzing the results proposed in [1, 10, 20], it is clear that there is a
gap between how these models capture the power of malicious agents or cured processes.
Garay’s model [10] is biased toward the cured processes, whereas the model of Sasaki etal. [20] favors the malicious agent, as it can control the send buﬀer of a cured process eventhough it is no longer hosted by the process. Our research fills the gap by avoiding thesebiases; similarly to Sasaki’s model [20], a cured process may send corrupted messages,
but only computed based on the corrupted state left by a malicious agent. In particular,a malicious agent can corrupt neither the code nor the identity of the process it occupies,
and a cured process always executes a correct code which ensures, for instance, that it
will send the same message to all of its neighbors.
The diﬀerence between the three models are subtle (see Fig. 1) but they have important consequences (Table 1). Figure 1 depicts the eﬀects of a malicious agent on aprocess. Red areas correspond to the steps controlled by the malicious agent. In Sasaki’s
model [20] (Fig. 1b), a single malicious agent can corrupt a process for two rounds eventhough it occupies the process only for a single round. In Garay’s model [10] (Fig. 1a)a cured process is aware of its current state (cured), which is represented in green. In
our model (Fig 1c; defined in Sect. 2) malicious nodes have the same power as in Garay’s
model, but the cured processes may send messages with corrupted content as in Sasaki’s
model.

3

r−2

r
r−1
sendrec com s r c s r ccorrect

faultyr−2

rr−1
sendrec com s r c s r c

curedcorrect(a) Garay’s model [10]rr−1
sendrec com s r c s r cfaultycured(b) Sasaki et al. model [20]r−2correct

faultyr−2

rr−1
sendrec com s r c s r c

curedcorrect(c) Our model

faultycured(d) Buhrman et al. model [3]Figure 1: Graphical representation of the various fault models

Table 1: Lower and upper bounds for Byzantine Agreement with mobile faults.
Model
Garay [10]Banu et al. [1]Sasaki et al. [20]This paper
Buhrman et al. [3]Impossibility result
open question
open questionn ≤ 6tn ≤ 5tn ≤ 3tPossibility resultn > 6tn > 4tn > 6tn > 5tn > 3t4

Byzantine vs Cured Game
Advantaged Cured
Advantaged Cured
Advantaged Byzantine Agent
No one advantaged
Virus like propagation

Contribution. In this model we prove a tight bound for the agreement problem. We
prove in Section 3 that the problem has no solution if the size of the network is n < 5t
(where t is an upper bound on the number of faulty agents) and propose an algorithm
that matches this bound in Section 4. We also formalize the Mobile Byzantine Agreement problem in Section 2.2. Following the results proved in [10], our solution is also
asymptotically time optimal.

2

Model and definitions

2.1

System model

Processes. We consider a synchronous message-passing system consisting of n processes p0 , p1 , . . . , pn−1 where Π = {0, . . . , n − 1} denotes the set of process indices. Eachprocess is an automaton whose state evolves following the execution of its local algorithm.
All processes execute the same algorithm.
The network is fully connected: all pairs of processes are directly linked with a reliablebidirectional channel; i.e. there is no loss, duplication, or alteration of messages. The
system evolves in synchronous rounds and all processes start simultaneously at round
0. There is a round counter accessible to the algorithm executed by each process. Eachround consists of three steps; send, receive, and compute. Based on its current local state,a process (1) computes and sends a message to all processes (including itself); (2) receives
messages sent by all processes (including itself); and (3) computes its new state based on
its current state and the set of received message.
Mobile malicious agents. Faults are represented by malicious mobile agents that canmove from process to process between rounds. There are at most t malicious agents, witht < n, and any process can be occupied by an agent. A process is said to be faulty in agiven round if it is occupied by an agent in that round. A process which is not occupied
by a malicious agent, but was occupied in the previous round is called a cured process.
A process which is neither faulty nor cured is called a correct process. Fr , Cor , and Cur
denote respectively the set of faulty, correct, and cured processes at round r. For easeof writing, we also consider the combined sets of correct/cured processes as the set ofnon-faulty processes Cr = Cor ∪ Cur = Π \ Fr .
Malicious agents are mobile and can move between the compute step of a round andthe send step of the next round (Figure 1c). The behavior of a faulty process is controlled
by the malicious agent. In particular, the agent can corrupt the local state of its hostprocess, and force it to send arbitrary messages (potentially diﬀerent messages to diﬀerent
processes). However, a malicious agent cannot corrupt the identify of that process (i.e.,
it cannot send messages using another identity), and is unable to modify the code of thealgorithm (i.e., the process resumes executing the correct algorithm after the malicious
agent moves away). So, as suggested in [3], we assume a secure, tamper-proof read-only
memory where the identity and the code are stored.
While it is possible for each non-faulty process to rejuvenate its code at the beginningof each round, local variables may still be corrupted (and of course cannot be recovered).
Therefore, in the case of cured processes the computation may be performed using acorrupted state.
5Comparison with previous models. As explained in Section 1 and graphically depicted in Figure 1, the above model diﬀers from Garay’s [10] and Sasaki’s [20] as follows.
In Sasaki’s model [20], a single malicious agent can corrupt a process for more than around although occupying this process only for a round. In our model, once the malicious agent leaves a process, that process will execute the correct code even though
the computation will be performed on a corrupted state. Diﬀerently from the Garay’s
model [10], where a cured process has the knowledge of its cured state and exploits it in
the algorithm, in our model processes can not access and exploit this knowledge.
Notation. In the formal definitions and proofs, varir denotes the value of variable var
in process pi at the end of round r. We also use the notation #w (W) to refer to thenumber of occurrences of w in tuple W.

2.2

Mobile Byzantine Agreement problem

We now formally define the Mobile Byzantine Agreement problem introduced first by
Garay et al. [10] and refined most recently by Sasaki et al. [20]. The definition presented
here is stronger than the definition proposed by Sasaki [20] (see discussion below).
Each initially-correct process pi has an initial value wi . All processes must decide 2 avalue dec such that the following properties hold:
1. BA-Termination: Eventually, all non-faulty processes during a round terminate theround with a non-bottom decided value.
∃r,∀r′ > r∀i ∈ Cr′′decri ̸= ⊥2. BA-Agreement: No two non-faulty processes decide diﬀerent values:
)
(
)
(
′
′
∀r, r′ ∀i ∈ Cr ∀j ∈ Cr′
decri ̸= ⊥ ∧ decrj ̸= ⊥ ⇒ decri = decrj
3. BA-Validity: If all initially-correct processes propose the same value w, correct
processes can decide only w.
∀w(∀i ∈ Co0

wi = w) ⇒ (∀r∀i ∈ Crdecri ∈ {⊥, w})

Note that specification of Mobile Byzantine Agreement given in this section is actuallystronger than the definition proposed by Sasaki et al. [20]. They diﬀer in two important
aspects. Firstly, where we require that, after some time, all non-faulty processes decide avalue at every round, their definition requires a decision only from processes that are notfaulty infinitely often. Secondly, where we allow non-faulty processes to decide only on aunique non-bottom value, Sasaki’s algorithm [20] allows the variable storing the decision
to take arbitrary values for a finite number of rounds. In other words, our specification
requires perpetual consistency whereas Sasaki’s algorithm ensures eventually consistency.
2

We use a terminology consistent with the classical definition of Byzantine agreement. However, theaction “decide” does not in itself guarantee a permanent decision. Indeed, due to the mobility of themalicious agents, non-faulty processes must re-decide the decision at the end of each round.

6

We now state two lemmas, proved in earlier models [10, 18], which also apply to ourmodel. The first lemma states a necessary condition. That condition is however not
suﬃcient; as explained previously, a bound on the number of faults is also required.
Lemma 1 (stated in [10]; formal proof derivable from [18]) Mobile Byzantine Agreement requires that at least one process remains uncorrupted for Ω(n) rounds of communication.
Lemma 2 (from [10]) Every Mobile Byzantine Agreement protocol requires Ω(n) rounds
in its worst case execution.

3

Upper bound on the number of faulty processes

In this section, we prove that, in the presence of t malicious mobile agents, Mobile
Byzantine Agreement cannot be solved with 5t processes or less, even if some process
remains uncorrupted forever.
Sasaki et al. [20] proved a similar result by reduction from a well-known existingbound. From the classical bound (n ≤ 3t) on synchronous Byzantine agreement, they
could obtain their bound (n ≤ 6t) by considering both faulty and cured processes as
Byzantine.
However, we cannot use the same approach because, in sharp contrast with Sasaki’s
model [20] and as explained in Section 2, in our model, the adversary cannot entirely
control cured processes.
Theorem 1 There is no deterministic algorithm that solves Mobile Byzantine Agreement
in a synchronous five-process system in the presence of a single mobile Byzantine agent(even with a permanently correct process).
Proof: The proof is by contradiction. Given a system consisting of five processes {p0 , . . . , p4 },where at least one is permanently correct, let us suppose that there exists an algorithm
that can solve the BA problem in the presence of a single malicious mobile agent. Suppose
that, in this algorithm, processes send the same message to all processes.3 Note that,during an execution, nothing prevents a faulty processes from sending diﬀerent messages
to other processes.
General idea. We consider three executions of this algorithm. In executions E 0 and
E 1 , all correct processes propose the same value; 0 and 1 respectively. The BA properties
imply that, eventually, non-faulty processes respectively decide 0 and 1 in these two
executions. The third execution, called E 01 , brings a contradiction: some processes
decide 0 while others decide 1.
The three executions are represented on Figure 2. Red (resp. light red) arrows correspond to corrupt messages sent by faulty (resp. cured) processes. The values proposedby correct processes appear on the left. Non-correct processes do not have proposed3

If not the case, we can trivially define an algorithm that satisfies this property by combining the setof sent messages into a single message.

7m10,0p0 − ?

?

p1 − ?

s11,0

p2 − 0s02,0p3 − 0s03,0p4 − 0

s04,0

m10,1

m10,2

s10,1

m11,0

m11,1

s11,2

?

m02,0

m02,1

s02,1

m03,0

m11,2
?

m02,2

s02,2

m03,1

s03,1

m04,0

s10,3

?

m03,2

s03,2

m04,1

s04,1

s02,3
s03,3

m04,2

s04,2

s04,3

(a) Execution E 0 where initially-correct processes p2 , p3 , and p4 propose value 0.
m10,0p0 − 1s10,0p1 − 1s11,0p2 − ?

?

p3 − ?

s03,0

p4 − 1

m10,1

m10,2

s10,1

m11,0

s11,1

m02,0

s10,2

m11,1

s11,2

s11,3

m02,2

s02,3

?

m03,0

m03,1
m14,1

s14,1

m03,2

s03,2

?

s14,0

m11,2

m02,1

s02,1

m14,0

s10,3

?

m14,2

s14,2

s14,3

(b) Execution E 1 where initially-correct processes p0 , p1 , and p4 propose value 1.
m10,0p0 − 1s10,0p1 − 1s11,0p2 − 0s02,0p3 − 0s03,0p4 − ?

?

m14,0
m11,0

m14,0
m02,0

m04,0

m10,1

m14,1

s10,1
s11,1

m11,1

m14,1
m02,1

s02,1

m03,0 m0

m04,1

m10,2

s11,2
s02,2

m03,1 m04,0 s04,1 s0

3,1

3,2

?

m14,2

s10,2

?

m11,2

m14,2
m02,2

m04,2

s10,3
s11,3
s02,3

m03,2 m04,2 s03,3?

(c) Execution E 01 where initially-correct processes p0 and p1 propose value 1 while initially-correct
processes p2 and p3 propose value 0. Process p4 is faulty and sends diﬀerent messages to each process.

Figure 2: Three executions leading to a contradiction of the existence of a BA protocol
in a 5-process system with one mobile malicious agent. (Legend: Arrows correspond tomessages exchanged between processes. Gray boxes contain the new local state computedby each process at the end of each round, which is then used to send message in thefollowing round. Red indicates actions taken by the faulty processes while light red refers
to actions taken by cured processes. Vertical dashed line separate successive rounds.)

8

values since they may have been corrupted by the malicious agent. Vertical dashed lines
separate successive rounds.
For each execution, we choose the process occupied by the single malicious agent. As
required, there is at least one process which is permanently non-faulty in each execution.
Executions E 0 and E 1 . In execution E 0 , the malicious agent alternates between processes p0 and p1 . In execution E 1 , it alternates between processes p2 and p3 . Processes
p2 , p3 , and p4 are initially correct and propose 0 in E 0 , while processes p0 , p1 , and p4 are
initially correct and propose 1 in E 1 .
For non-faulty processes, the messages sent during these executions are computed by
the algorithm based on the local states of processes. For correct processes (i.e., excluding
cured ones), let us denote by s0i,r (resp. s1i,r ) the local state of process pi at the beginningof the round r in execution E 0 (resp. E 1 ). Based on this local state, let m0i,r (resp., m1i,r )denote the message computed and sent by a correct process pi at round r in execution
E 0 (resp., E 1 ).
We now define the behavior of the malicious agent. For the faulty process pi (either
p0 or p1 ) at round r of execution E 0 , we choose that pi sends the message m1i,r (i.e., themessage it would have sent at the same round in E 1 ) and we choose that pi updates its
local state to s1i,r+1 at the end of the round (i.e., the same state it would have computedin E 1 ). Similarly we choose that the faulty process pi (either p2 or p3 ) at round r of
execution E 1 sends the message m0i,r and updates its state to s0i,r+1 .
Execution E 01 . In execution E 01 , the malicious agent always occupies process p4 . The
four other processes are initially (and forever) correct. As in E 0 , processes p2 and p3
propose 0. As in E 1 , processes p0 and p1 propose 1. In this execution, the faulty process
p4 does not send the same message to all processes. At any round, p4 sends the message
m14,r to p0 and p1 , but sends m04,r to p3 and p4 .
Indistinguishability. In the sequel, we prove the following claim: E 0 and E 01 areindistinguishable for p2 and p3 , and similarly E 1 and E 01 for p0 and p1 . This can beproven by induction on the round number, using the following predicate P(r) for r ≥ 0:
p0 starts round r in E 1 and E 01 with the same local state
p1 starts round r in E 1 and E 01 with the same local stateP(r) =
p2 starts round r in E 0 and E 01 with the same local state
p3 starts round r in E 0 and E 01 with the same local state
The proof is only for p0 . The proofs for p1 , p2 , and p3 are identical.
Case r = 0. p0 proposes the same value in E 1 and E 01 and therefore starts round 0
with the same initial local state, namely s00,0 .
Case r ≥ 0. Let us suppose that predicate P(r) is true.
• p0 is correct in E 1 and E 01 and, by induction hypothesis, starts round r with thesame local state. Therefore p0 necessarily sends the same message, namely m10,r , toall processes in round r of both E 1 and E 01 .
9

Similarly, p1 sends the same message m11,r to all processes in round r of both E 1and E 01 .
• p2 is correct in E 0 and E 01 and, by induction hypothesis, starts round r with thesame local state. Therefore p2 necessarily sends the same message, namely m02,r , toall processes in round r of both E 0 and E 01 . Considering execution E 1 , there are
two cases to consider; (1) p2 is faulty during round r and then, by construction, themalicious agent forces p2 to send the message m02,r ; (2) p2 is cured during roundr, which means that it was faulty in the previous round and the malicious agent
forced p2 to start round r in the local state s02,r which implies that p2 still sends themessage m02,r . In all cases, p2 sends the same message in round r of both E 1 andE 01 .
Similarly, p3 sends the same message m03,r to all processes in round r of both E 1and E 01 .
• p4 is faulty in E 01 . By construction, in each round, it sends to p0 the same message
as in E 1 . It means that p4 sends the same message, namely m04,r , to p0 in round rof both E 1 and E 01 .
Process p0 receives the same messages from all processes in round r of E 1 and E 01 . Since
p0 is correct in both executions, it computes the same new local state and starts roundr + 1, which prove P(r + 1).
Thus by induction, the predicate P(r) is true for all rounds and therefore the claim
holds. Since p0 and p1 eventually decide 1 in E 1 , they also decide 1 in E 01 . Similarly,
since p2 and p3 eventually decide 0 in E 0 , they also decide 0 in E 01 . Contradiction. □When n ≤ 5t, the proof of Theorem 1 can be generalized by replacing any process
appearing in the proof by a group of processes of size at most t.
Corollary 1 There is no deterministic algorithm that solves the Mobile Byzantine Agreement problem in a synchronous n-process system in the presence of t mobile byzantine
agent if n ≤ 5t (even with a permanently correct process).

4

Algorithm for Mobile Byzantine Agreement

Given a system with t malicious mobile agents, we introduce an algorithm that solves Mobile Byzantine Agreement under the following two conditions: (1) there are at least 5t + 1
processes in total, and (2) at least one process remains uncorrupted for 3n consecutive
rounds (see Lemma 1).

10

Algorithm 1: BA algorithm (code for pi with proposed value wi )1
2

Function MBA(wi ):vi ← wi ;

24
25
26

for s = 0 to n − 1 do
begin round // proposing round r = 3svi ← propose(vi );deci ← ⊥;end round

3
4
5
6
7

27
28
29
30

Function propose(v):P V [1..n] ← [⊥, . . . , ⊥];send v to all processes;
foreach j ∈ Π do
if vj received from j then P V [j] ← vj ;if ∃w ̸= ⊥, #w (P V ) ≥ n − 2t then return w;
return ⊥;begin round // collecting round r = 3s + 1 31 Function collect(v):SVi ← collect(vi );32
SV [1..n] ← [⊥, . . . , ⊥];deci ← ⊥;33
send v to all processes;
34
foreach j ∈ Π do
end round35
if vj received from j then SV [j] ← vj ;begin round // deciding round r = 3s + 2 36
return SV ;vi ← decide(s, SVi );deci ← ⊥;37 Function decide(s, SV ):end round38
EV [1..n][1..n] ← [[⊥, . . . , ⊥], . . . , [⊥, . . . , ⊥]];
end for39
send SV to all processes;
40
foreach j ∈ Π dodeci ← vi ;41
if SVj received from j then EV [j] ← SVj ;

8
9
10
11
12
13
14
15
16
17

for r = 3n to ∞ do
begin round // maintaining round
send deci to all processes;
deci ← the value received at least n − 2ttimes;
end roundend for

18
19
20
21
22
23

42
43
44
45
46
47
48
49

4.1

RV [1..n] ← [⊥, . . . , ⊥];foreach j ∈ Π doif ∃w ̸= ⊥, #w (EV [·][j]) > 2t then RV [j] ← w;
if ∃w ̸= ⊥, #w (RV ) > 3t then return w;elsec ← s mod n;
if ∃w ̸= ⊥, #w (EV [c][·]) > 2t then return w;
return 0;

Description of the algorithm

The algorithm builds upon earlier ones [1, 10, 20] but contains some important improvements; (i) a clear separation between the deciding and the maintaining parts, (ii) a
simplification of the code of the algorithm, and (iii) additional code in order to satisfy
our stricter BA-Agreement property. The algorithm (lines 1 − 23) consists of two mainparts:
1. Deciding part: processes execute 3n rounds to agree on a value.
2. Maintaining part: processes execute the same round forever to keep the decided
value.
Maintaining part (lines 18 − 23) This part is simple and repeats forever from round
3n. The goal is to allow cured processes to recover the decided value from correct ones,
since that value may have been corrupted by the malicious agent. All processes exchange
their current decided values dec and update their variable dec to the value that has been
received at least n − 2t times. During each of these rounds, there must be at least n − 2tcorrect processes according to the model. If all of them send the same value (which isguaranteed by the algorithm), all non-faulty processes receive n − 2t messages containing
this same value and thus decide accordingly.
Deciding part (lines 3−16) This part is complex and consists of n phases of 3 rounds
each. The goal is to guarantee that, at the end of round 3n − 1, all non-faulty processes
11have the same value v and therefore decide it (line 17). During the first 3n rounds, v
may take diﬀerent non-bottom values, which is why processes cannot decide in earlier
rounds.4
This part uses the rotating coordinator paradigm. Recall that, in each round, there
are at least n − t non-faulty processes, and at least n − 2t correct ones. Each of the nphases are divided into 3 rounds:• Proposing round; all non-faulty processes (at least n − t) end the round with at
most one non-bottom value v. Consequently, it guarantees that the (at least n − 2t)correct processes of the next round start with at most one non-bottom value v.
• Collecting round; processes exchange the values computed in the previous roundand store them in array SV (the set of received values).
• Deciding round; processes try to agree on the same value v using the rotating
coordinator paradigm. If the coordinator of the current round is correct during theentire phase, non-faulty processes are guaranteed to terminate the phase with thesame value. Such a coordinating round exists since, by assumption, there is one
process which is correct for at least 3n rounds.
In the deciding round, processes exchange the array SV computed during the previous round. Based on the arrays they received, each process computes a new5 array
RV (the vector of reconstructed values). For each non-faulty process, both SV
and RV contain “almost” the same values (SV = RV if all processes are correct),but, as it appears in the proof, these two arrays are necessary to guarantee thecorrectness of our algorithm.
After the phase corresponding to a correct coordinator, all non-faulty processes havethe same value v. This property will continue during all subsequent phases even if thecorresponding coordinators are faulty (in fact lines 46 − 49 will not be executed anymore
as shown in the proof).
Additional code (lines 6, 10, 14) Usually, the variable dec is initialized to ⊥ atthe beginning of an algorithm. However, this value may be corrupted for any processthat becomes faulty during the execution. To satisfy the BA-Agreement property, it istherefore necessary for each non-faulty process to re-initialize its variable dec to ⊥ at theend of each of the first 3n round.

4.2

Proof of the algorithm

Due to page limitations, the proof of the algorithm appears in Appendix A. We only
state here the final theorem.
Theorem 2 Algorithm 1 solves Mobile Byzantine Agreement in a synchronous n-processsystem in the presence of t mobile Byzantine agents provided that n ≥ 5t + 1 and that atleast one process remains uncorrupted.
4This is diﬀerent from previous papers as already mentioned in Section 2.
Technically, as in [20], it is possible to use the same variable for both SV and RV . We choose to use
two diﬀerent names for the clarity of the proof.
5

12

5

Conclusion and Discussion

We proposed a new model for Mobile Byzantine Agreement, that balances the power ofcorrect and malicious agents. In our model, a process cannot detect its own infection
and cannot instantly recover its state after the malicious agent moves away. Hence, ourmodel gives less power to correct processes than Garay’s model [10]. Recall that, in thismodel, a cured process can magically detect the leave of the malicious agent. In contrast,
in our model, a cured process (a process that has been infected by a malicious agent)
will not behave maliciously after the agent left it. That is, a cured process may send
corrupted messages (computed based on a corrupted state) but it will send the same
corrupted message to all neighbors. In this respect, our model gives less power to the
Byzantine agents than Sasaki’s model [20] where a Byzantine agent can prepare messages
and control the sending of these messages even after it left that process. In our model, we
prove that there is no protocol for Mobile Byzantine Agreement in synchronous networks
with n ≤ 5t. We propose then a tight algorithm which can tolerate t mobile Byzantine
agents with at least 5t + 1 processes.
In the following, we list several open questions and non trivial research directions inthis area. The next step in our research is the study on the feasibility of Mobile Byzantine
Agreement on arbitrary topologies. Another interesting direction would be to decrease,
via randomization, the time complexity of the algorithm.
Notice that, even though our model has a self-stabilization flavor, our work is diﬀerent
in several aspects from the self-stabilizing Byzantine agreement of [5]. Note that in thecase of self-stabilizing Byzantine agreement the studied model assumes that the Byzantine
set is fixed. That is, it does not change during the execution. Also it is assumed,
as in all self-stabilizing algorithms, that the system eventually becomes coherent (i.e.
the communication network and a suﬃcient fraction of nodes is not faulty for suﬃcient
long time period for the pre-conditions for convergence of the protocol to hold). Morespecifically, in self-stabilization it is assumed that during the convergence period thesystem does not suﬀer additional perturbations. In our case the system is permanently
stressed due to the mobility of the Byzantine nodes. Note also that the problem solved
in [5] is diﬀerent since it allows the output of inconsistent decision values during transientperiods.
In our model, a malicious agent can move anywhere in the network, and likely mostwork on the subject, we considered a fully connected topology. Sasaki et al. [20] haveconsidered the case of diﬀerent topologies. An interesting line of work is to generalize toarbitrary topologies, and also to consider when the mobility of the malicious agents isconstrained by a, possibly diﬀerent, topology.
Finally, to the best of our knowledge, so far no investigation of Mobile Byzantine
Agreement has been done in anonymous settings or networks where node identities are
not unique. In these contexts, algorithms based on a coordinator are not applicable.

Acknowledgments
This research was supported in part by JSPS KAKENHI Grant Number 26330020 and 26870228.

13

References[1] N. Banu, S. Souissi, T. Izumi, and K. Wada. An improved byzantine agreement algorithm for synchronous systems with mobile faults. International Journal of Computer
Applications, 43(22):1–7, April 2012.
[2] G. Bracha. An o(log n) expected rounds randomized byzantine generals protocol.
Journal of the ACM, 34(4):910–920, October 1987.
[3] H. Buhrman, J. A. Garay, and J.-H. Hoepman. Optimal resiliency against mobile
faults. In Proceedings of the 25th International Symposium on Fault-Tolerant Computing (FTCS’95), pages 83–88, 1995.
[4] M. Correia, G. S. Veronese, and L. C. Lung. Asynchronous byzantine consensus with
2f + 1 processes. In Proceedings of the 25th ACM Symposium on Applied Computing(SAC’10), pages 475–480, 2010.
[5] Ariel Daliot and Danny Dolev. Self-stabilizing Byzantine agreement. In Proc. 25th
ACM Symp. on Principles of Distributed Computing (PODC’06), pages 143–152,
2006.
[6] D. Dolev. The byzantine generals strike again. Journal of Algorithms, 3(1):14–30,
March 1982.
[7] D. Dolev, M. J. Fischer, T. R. Fowler, N. A. Lynch, and H. R. Strong. An eﬃcientalgorithm for byzantine agreement without authentication. Information and Control,
52(3):257–274, March 1982.
[8] P. Feldman and S. Micali. An optimal probabilistic protocol for synchronous byzantine agreement. SIAM Journal on Computing, 26(4):873–933, August 1997.
[9] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
[10] J. A. Garay. Reaching (and maintaining) agreement in the presence of mobile faults.
In Proceedings of the 8th International Workshop on Distributed Algorithms, volume857, pages 253–264. Springer Berlin Heidelberg, 1994.
[11] L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM
Transactions on Programming Languages and Systems, 4(3):382–401, July 1982.
[12] J.-P. Martin and L. Alvisi. Fast byzantine consensus. IEEE Transactions on Dependable and Secure Computing, 3(3):202–215, July 2006.
[13] M. Okun and A. Barak. Eﬃcient algorithms for anonymous byzantine agreement.
Theory of Computing Systems, 42(2):222–238, January 2008.
[14] R. Ostrovsky and M. Yung. How to withstand mobile virus attacks (extended abstract). In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (PODC’91), pages 51–59, 1991.
14

[15] M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults.
Journal of the ACM, 27(2):228–234, April 1980.
[16] M. Raynal. Fault-tolerant Agreement in Synchronous Message-passing Systems. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers,
2010.
[17] R. Reischuk. A new solution for the byzantine generals problem. Information andControl, 64(1-3):23–42, January-March 1985.
[18] N. Santoro and P. Widmayer. Time is not a healer. In Proceedings of the 6th Annual
Symposium on Theoretical Aspects of Computer Science (STACS’89), pages 304–313,
1989.
[19] N. Santoro and P. Widmayer. Majority and unanimity in synchronous networks
with ubiquitous dynamic faults. In Proceedings of the 12th International Conferenceon Structural Information and Communication Complexity (SIROCCO’05), pages
262–276, 2005.
[20] T. Sasaki, Y. Yamauchi, S. Kijima, and M. Yamashita. Mobile byzantine agreement on arbitrary network. In Proceedings of the 17th International Conference on
Principles of Distributed Systems (OPODIS’13), pages 236–250, December 2013.
[21] U. Schmid, B. Weiss, and I. Keidar. Impossibility results and lower bounds for consensus under link failures. SIAM Journal on Computing, 38(5):1912–1951, January
2009.

A

Proof of the algorithm

In the formal definitions and proofs, varir denotes the value of variable var in process
pi at the end of round r. We also use the notation #w (W) to refer to the number ofoccurrences of w in tuple W. dH (·, ·) denotes the Hamming distance which corresponds
to the number of diﬀerent elements between two tuples and X can be any arbitrary set.
In all following lemmas, we suppose that t ≥ 0 and n ≥ 5t + 1. As stated previously, we
also suppose that there exists some process which remains correct for at least 3n rounds.
Moreover, for each round, the proposed algorithm makes each process to send the samemessage to all processes. Consequently, in each round, only faulty processes may send
diﬀerent message to diﬀerent processes.
We prove first a simple preliminary lemma that will be used in the main proof of thealgorithm.
Lemma 3 Let t ≥ 0, n ≥ 5t + 1, and two n-tuples that diﬀer on at most t values. If twovalues appear n − 2t times respectively in each tuple, then they are the same. Formally:(∀t ≥ 0∀n ≥ 5t + 1∀T, T ′ ∈ X n∀x, x′ ∈ X)(dH (T, T ) ≤ t) ∧ (#x (T ) ≥ n − 2t) ∧ (# (T ) ≥ n − 2t) ⇒ (x = x′ )
′

x′

15

′

Proof: The proof is by contradiction. Let us assume that for some t ≥ 0 and somen ≥ 5t + 1 there exist two n-tuples T and T ′ such that(dH (T, T ′ ) ≤ t) ∧ (#x (T ) ≥ n − 2t) ∧ (#x′ (T ′ ) ≥ n − 2t) ∧ (x ̸= x′ )Since #x (T ) ≥ n − 2t and x ̸= x′ , it implies that #x′ (T ) ≤ 2t. Then from dH (T, T ′ ) ≤ t,
we deduce that #x′ (T ′ ) ≤ #x′ (T ) + t ≤ 2t + t = 3t. Finally n ≥ 5t + 1 implies that#x′ (T ′ ) ≤ n − 2t − 1, which is a contradiction.
□
Lemma 4 There exists a phase that all non-faulty processes terminate with the same(non-bottom) value v. Formally:∃s ≤ n − 1,∃w ̸= ⊥,∀i ∈ C3s+2

vi3s+2 = w

Proof: By assumption, there is a process which remains non-faulty for at least 3n rounds.
Let pc be this process and consider the cth phase where pc is the coordinator (line 47).
We consider sequentially the three rounds of this phase. (To simplify the explanations;when it is not specified, faulty/non-faulty/correct processes are defined with respect tothe current round.)• Round 3c. Each non-faulty process updates its variable v at line 5 from the value
returned by the function propose. Since there are at most t faulty processes, thetuples P V (computed at line 28) of non-faulty processes diﬀer on at most t values.
Function propose returns a non-bottom value (line 29) only if this value appears
at least n − 2t times in the tuple P V . From Lemma 3, it implies that the n − t
non-faulty processes can have only one non-bottom value v at the end of the round.
Formally:()∀i, j ∈ C3c(vi3c ̸= ⊥) ∧ (vj3c ̸= ⊥) ⇒ (vi3c = vj3c )(1)
If any non-faulty process has a non-bottom value vi3c , let w denote this specificvalue.
• Round 3c + 1. All correct processes in this round were non-faulty in the previous
round: Co3c+1 ⊆ C3c . Observation (1) implies that all correct processes send either abottom value or the value w (if it exists) at line 33. Only cured and faulty processes
may send other values. Therefore, all non-faulty processes receive at most 2t values
which are diﬀerent from w and ⊥.
It also means that the arrays SV computed at line 35 by non-faulty processes
contain at most 2t elements diﬀerent from w and ⊥ and these elements are all
located at the same indexes. Formally:∀j, j ′ ∈ C3c+1∀k ∈ Co3c+1

SVj3c+1 [k] = SVj3c+1[k] ∈ {w, ⊥}′(2)• Round 3c + 2. All correct processes in this round were non-faulty in the previous
round: Co3c+2 ⊆ C3c+1 . Observation (2) implies that all correct processes send anarray SV (line 39) satisfying the previous conditions and therefore all non-faulty
processes update their matrix EV such that:∀i ∈ C3c+2∀j, j ′ ∈ Co3c+2∀k ∈ Co3c+1
16

EVi3c+2 [j][k] = EVi3c+2 [j ′ ][k] ∈ {w, ⊥}Since |Π \ Co3c+2 | ≤ 2t, for all such indexes k, the test of line 44 can be true only
for the value w:∀i ∈ C3c+2∀k ∈ Co3c+1

RVi3c+2 [k] ∈ {w, ⊥}Since |Π \ Co3c+1 | ≤ 2t, it implies that the test of line 45 can be true only for thevalue w. (Note that the test of line 45 uses the threshold 3t instead of 2t for anotherreason, as explained later in the proof.)
Non-faulty processes update their variable v from the value returned by the function
decide. This value may be returned at lines 45, 48, or 49. There are two cases toconsider:1. No (non-faulty) process receives the value from line 45. All non-faulty processes update their variable v according to the test of line 48. Since, by hypothesis, the current coordinator pc is correct, it sends the same array SVc3c+1
to all processes and thus all non-faulty processes have the same line EV [c][·],
which means that all non-faulty processes terminate the phase with the samenon-bottom value v (returned at line 48 or 49).
2. At least one non-faulty process updates its variable v from a value returned atline 45. Let pm be such a process. As stated above, pm necessarily updates vm
to the value w and any other non-faulty process that returns from decide atline 45 also updates its variable v to w. It remains to prove that the remaining
non-faulty processes (if any) that update their variable v from a value returned
at line 48 or 49 also update to the same value w. Since pm returns from decide
at line 45, it means that RVm contains more than 3t times the value w. Let
us called J the set of indexes j corresponding to the value w:
J = {j, RVm3c+2 [j] = w}
For all indexes of J, pm has executed line 44 which means that the column
EVm [·][j] contains more than 2t times the value w. Since there are at most
2t non-correct (faulty and cured) processes; it means that at least one correct
process sends an array SV containing the value w at the j th position for allindexes j of J. Formally:∀j ∈ J∃i ∈ Co3c+2 ,SVi3c+2 [j] = w(3)

Let us consider the subset J ′ of J that contain all processes of J that are
non-faulty in the round 3c + 1. Since there are at most t faulty processes perround, |J ′ | ≥ |J| − t ≥ 2t. According to Observation (3), for each element of
J ′ , there is at least one correct process whose corresponding entry in its array
SV contains the value w. This value comes from the execution of line 35 ofround 3c + 1. Since, by definition, all processes of J ′ are non-faulty during theround 3c + 1, it implies that all processes of J ′ sends the value w at line 33 ofround 3c + 1. Formally:∀j ′ ∈ J ′ vj3c+1=w′
17

Therefore, all non-faulty processes of round 3c + 1 have received these values
w from processes of J ′ . It includes the process pc which is, by assumption,
always correct. It means that pc sends at line 39 of round 3c + 2 an array SVc
that contains at least |J ′ | ≥ 2t values w. Consequently, during round 3c + 2,
all non-faulty processes that has not returned from decide at line 45 returns
at line 45 (since the test of line 45 is true). All non-faulty processes update
their variable v to w, which concludes the proof of the lemma.
□
Lemma 5 If all correct processes start a phase with the same variable v, then all nonfaulty processes terminate the phase with this same value. Formally:()()∀s ≤ n − 1, ∀w ̸= ⊥,∀i ∈ Co3s vi3s−1 = w ⇒ ∀i ∈ C3s+2 vi3s+2 = w
Proof: We consider sequentially the three rounds of phase s:• Round 3s. All correct processes start the round with the same value v = w. They
all send this value at line 26. Since there are at least n − 2t correct processes,
all non-faulty processes receive the value w at least n − 2t times and therefore all
non-faulty processes update their variable v to w. Formally:∀i ∈ C3s

vi3s = w(4)• Round 3s + 1. All correct processes in this round were non-faulty in the previous
round: Co3s+1 ⊆ C3s . Observation (4) implies that all correct processes send thevalue w at line 33. Therefore all non-faulty processes obtain an array SV whichcontains at least n − 2t times the value w at the indexes corresponding to correct
processes. Formally:∀j ∈ C3s+1∀k ∈ Co3s+1

SVj3s+1 [k] = w(5)• Round 3s + 2. All correct processes in this round were non-faulty in the previous
round: Co3s+2 ⊆ C3s+1 . Observation (5) implies that all correct processes send anarray SV at line 39 that contains at least n − 2t times the value w. Therefore all
non-faulty processes obtain a variable EV that contains “many” w. Formally:∀i ∈ C3s+2∀j ∈ Co3s+2∀k ∈ Co3s+1

EVi [j][k] = w

Since |Co3s+2 | > 2t, all non-faulty processes will execute line 44 for all indexes
corresponding to correct processes of the previous round:∀i ∈ C3s+2∀k ∈ Co3s+1

RVi3s+2 [k] = w

Consequently, for all non-faulty processes, the array RV contains at least |Co3s+1 |times the value w. Since |Co3s+1 | ≥ n − 2t > 3t, all non-faulty processes evaluate
positively the test of line 45 and return w, which means that all non-faulty processes
terminate the round 3s + 2 with their variable v to value w. It concludes the proof.
18

□
Theorem 2 Algorithm 1 solves the Mobile Byzantine Agreement problem in a synchronous
n-process system in the presence of t mobile byzantine agents provided that n ≥ 5t + 1
and that there is at least one process which remains uncorrupted.
Proof: Lemmas 4 and 5 guarantee that all non-faulty processes of round 3n − 1 terminate
the round with the same non-bottom value w in variable v. At line 17, all these non-faulty
processes decide the value w. Starting from round 3n, a simple induction shows that all
non-faulty processes will always decide this same value w since there are at most 2t noncorrect processes during each round. It proves the BA-Termination and BA-Agreement
properties.
To prove the BA-Validity, it is suﬃcient to apply Lemma 5 directly from the firstround. If all initially-correct processes propose the same value, this value will be propagated until round 3n − 1 where it will be decided. This concludes the proof.
□19