Silvia Bonomi
email: bonomi@dis.uniroma1.it

Antonella Del Pozzo ⋆ †

Maria Potop-Butucaru
email: maria.potop-butucaru@lip6.fr

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

Optimal Storage under Unsynchrononized Mobile Byzantine Faults

In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled).

We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.

Introduction

Byzantine fault tolerance is a fundamental building block in distributed system, as Byzantine failures include all possible faults, attacks, virus infections and arbitrary behaviors that can occur in practice (even unforeseen ones). The classical setting considers Byzantine participants remain so during the entire execution, yet software rejuvenation techniques increase the possibility that a corrupted node does not remain corrupted during the whole system execution and may be aware of its previously compromised status [START_REF] Sousa | Highly available intrusion-tolerant services with proactive-reactive recovery[END_REF].

Mobile Byzantine Failures (MBF) models have been recently introduced to integrate those concerns. Then, faults are represented by Byzantine agents that are managed by an omniscient adversary that "moves" them from a host process to another, an agent being able to corrupt its host in an unforeseen manner. MBF investigated so far consider mostly round-based computations, and can be classified according to Byzantine mobility constraints: (i) constrained mobility [START_REF] Buhrman | Optimal resiliency against mobile faults[END_REF] agents may only move from one host to another when protocol messages are sent (similarly to how viruses would propagate), while (ii) unconstrained mobility [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF][START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF][START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF][START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] agents may move independently of protocol messages. In the case of unconstrained mobility, several variants were investigated [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF][START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF][START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF][START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF]: Reischuk [START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF] considers that malicious agents are stationary for a given period of time, Ostrovsky and Yung [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] introduce the notion of mobile viruses and define the adversary as an entity that can inject and distribute faults; finally, Garay [START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF], and more recently Banu et al. [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF], and Sasaki et al. [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] and Bonnet et al. [START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF] consider that processes execute synchronous rounds composed of three phases: send, receive, and compute. Between two consecutive such synchronous rounds, Byzantine agents can move from one node to another. Hence the set of faulty hosts at any given time has a bounded size, yet its membership may evolve from one round to the next. The main difference between the aforementioned four works [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF][START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] lies in the knowledge that hosts have about their previous infection by a Byzantine agent. In Garay's model [START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF], a host is able to detect its own infection after the Byzantine agent left it. Sasaki et al. [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] investigate a model where hosts cannot detect when Byzantine agents leave. Finally, Bonnet et al. [START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF] considers an intermediate setting where cured hosts remain in control on the messages they send (in particular, they send the same message to all destinations, and they do not send obviously fake information, e.g. fake id). Those subtle differences on the power of Byzantine agents turns out to have an important impact on the bounds for solving distributed problems.

A first step toward decoupling algorithm rounds from mobile Byzantine moves is due to Bonomi et al. [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF]. In their model, mobile Byzantine movements are either: (i) synchronized, but the period of movement is independent to that of algorithm rounds, (ii) independent time bounded, meaning that Byzantine agents are only requested to remain some minimum amount of time at any occupied node, or (iii) independent time unbounded, which can be seen as a special case of (ii) when the minimum amount of time is one time unit. In particular, the Bonomi et al. [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] model implies that Byzantine moves are no more related to messages that are exchanged through the protocol.

Register Emulation. Traditional solutions to build a Byzantine tolerant storage service (a.k.a. register emulation) can be divided into two categories: replicated state machines [START_REF] Schneider | Implementing fault-tolerant services using the state machine approach: A tutorial[END_REF], and Byzantine quorum systems [START_REF] Rida | Synchronous byzantine quorum systems[END_REF][START_REF] Malkhi | Byzantine quorum systems[END_REF][START_REF] Martin | Small byzantine quorum systems[END_REF][START_REF] Martin | Minimal byzantine storage[END_REF]. Both approaches are based on the idea that the current state of the storage is replicated among processes, and the main difference lies in the number of replicas that are simultaneously involved in the state maintenance protocol. Several works investigated the emulation of self-stabilizing or pseudostabilizing Byzantine tolerant SWMR or MWMR registers [START_REF] Noga Alon | Practically stabilizing SWMR atomic memory in message-passing systems[END_REF][START_REF] Bonomi | Byzantine tolerant storage[END_REF][START_REF] Bonomi | Stabilizing server-based storage in byzantine asynchronous message-passing systems[END_REF]. All these works do not consider the complex case of mobile Byzantine faults. Recently, Bonomi et al. [START_REF] Bonomi | Tight self-stabilizing mobile byzantine-tolerant atomic register[END_REF] proposed optimal self-stabilizing atomic register implementations for round-based synchronous systems under the four Mobile Byzantine models described in [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Franc ¸ois Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF][START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF]. The round-free model [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] where Byzantine moves are decoupled from protocol rounds also enables optimal solutions (with respect to the number of Byzantine agents) for the implementation of regular registers. However, this last solution requires Byzantine agents to move in synchronous steps, whose duration for the entire execution is fixed, so the movements of Byzantine agents is essentially synchronous. As it is impossible to solve the register emulation problem when processes are asynchronous and Byzantine agents are synchronous [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF], the only case remaining open is that of synchronous processes and unsynchronized Byzantine agents.

Our Contribution. We relax the main assumption made for obtaining positive results in the round-free model: Byzantine moves are no more synchronized. The main contribution of this paper is to thoroughly study the impact of unsynchronized mobile Byzantine agents on the register emulation problem. We present Table 1: Summary of lower bounds in different system models. δ is the upper bound on the message delay, and ∆ is the period for synchronized agent moves (in the synchronous agents setting) or the lower bound for an agent to remain on a server (in the unsynchronized agents setting).

Round-based model [START_REF] Bonomi | Tight self-stabilizing mobile byzantine-tolerant atomic register[END_REF] Burhman Garay Bonnet Sasaki 2f + 1 3f + 1 4f + 1 4f + 1

Round-free model Agents moves

Synchronized Unsynchronized [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] [this paper] Cured state awareness Aware Unaware Aware Unaware δ ≤ ∆ < 2δ 5f + 1 8f + 1 6f + 1 12f + 1 2δ ≤ ∆ < 3δ 4f + 1 5f + 1 4f + 1 7f + 1 lower and matching upper bounds for implementing a regular register in the unsynchronized mobile Byzantine model. We first explore and characterize the key parameters of the model that enable problem solvability. As expected, the lower bounds results require completely new proof techniques that are of independent interest while studying other classical problems in the context of unsynchronized mobile Byzantine agents.

When the problem is solvable, it turns out that minor changes to existing quorum-based protocols joint with smart choices of quorums thresholds command optimal resilience (with respect to the number of Byzantine agents). Table 1 summarizes all the lower bounds for the various models, the newly obtained results are presented in boldface.

System Model

We consider a distributed system composed of an arbitrary large set of client processes C, and a set of n server processes S = {s 1 , s 2 . . . s n }. Each process in the distributed system (i.e., both servers and clients) is identified by a unique identifier. Servers run a distributed protocol emulating a shared memory abstraction, and clients are unaware of the protocol run by the servers.The passage of time is measured by a fictional global clock (e.g., that spans the set of natural integers), whose processes are unaware of.At each time instant t, each process (either client or server) is characterized by its internal state, i.e., by the set of its local variables and their assigned values. We assume that an arbitrary number of clients may crash, and that up to f servers host, at any time t, a Byzantine agent. Furthermore, servers processes execute the same algorithm, and cannot rely on high level primitives such as consensus or total order broadcast. Communication model. Processes communicate through message passing. In particular, we assume that: (i) each client c i ∈ C can communicate with every server through a broadcast() primitive, (ii) each server can communicate with every other server through a broadcast() primitive, and (iii) each server can communicate with a particular client through a send() unicast primitive. We assume that communications are authenticated (i.e., given a message m, the identity of its sender cannot be forged) and reliable (i.e., spurious messages are not created and sent messages are neither lost nor duplicated). Timing Assumptions. The system is round-free synchronous in the sense that: (i) the processing time of local computations (except for wait statements) are negligible with respect to communication delays, and are assumed to be equal to 0, and (ii) messages take time to travel to their destination processes. In particular, concerning point-to-point communications, we assume that if a process sends a message m at time t then it is delivered by time t + δ p (with δ p > 0). Similarly, let t be the time at which a process p invokes the broadcast(m) primitive, then there is a constant δ b (with δ b ≥ δ p ) such that all servers have delivered m at time t + δ b . For the sake of presentation, in the following we consider a unique message delivery delay δ (equal to δ b ≥ δ p ), and assume δ is known to every process.

Computation model. Each process of the distributed system executes a distributed protocol P that is composed by a set of distributed algorithms. Each algorithm in P is represented by a finite state automaton and it is composed of a sequence of computation and communication steps. A computation step is represented by the computation executed locally to each process while a communication step is represented by the sending and the delivering events of a message. Computation steps and communication steps are generally called events.

Definition 1 (Execution History) Let P be a distributed protocol. Let H be the set of all the events generated by P at any process p i in the distributed system and let → be the happened-before relation. An execution history (or simply history) Ĥ = (H, →) is a partial order on H satisfying the relation →. MBF model. We now recall the generalized Mobile Byzantine Failure model [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF]. Informally, in the MBF model, when a Byzantine agent is hosted by a process, the agent takes entire control of its host making it Byzantine faulty (i.e., it can corrupt the host's local variables, forces it to send arbitrary messages, etc.). Then, the Byzantine agent leaves its host with a possible corrupted state (that host is called cured) before reaching another host.We assume that any process previously hosting a Byzantine agent has access to a tamper-proof memory storing the correct protocol code. However, a cured server may still have a corrupted internal state, and thus cannot be considered correct. The moves of a Byzantine agent are controlled by an omniscient adversary.

]) = τ ∈ [t,t ′ ] Cu(τ )).
With respect to the movements of agents, we consider the independent time-bounded (ITB) model: each mobile Byzantine agent ma i is forced to remain on a host for at least a period ∆ i . Given two mobile Byzantine Agents ma i and ma j , their movement periods ∆ i and ∆ j may be different. Note that previous results considering decoupled Byzantine moves [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] were established in the weaker ∆-synchronized model, where the external adversary moves all controlled mobile Byzantine agents at the same time t, and their movements happen periodically with period ∆. None of those properties remain valid in our model.

Concerning the knowledge that each process has about its failure state, we distinguish the following two cases: Cured Aware Model (CAM): at any time t, every process is aware about its failure state; Cured Unaware Model (CUM): at any time t, every process is not aware about its failure state.

We assume that the adversary can control at most f Byzantine agents at any time (i.e., Byzantine agents do not replicate while moving). In our work, only servers can be affected by the mobile Byzantine agents 1 . It follows that, at any time t |B(t)| ≤ f . However, during the system lifetime, all servers may be hosting a Byzantine agent at some point (i.e., none of the servers is guaranteed to remain correct forever). Register Specification.

A register is a shared variable accessed by a set of processes, called clients, through two operations, namely read and write. Informally, the write operation updates the value stored in the shared variable, while the read obtains the value contained in the variable (i.e., the last written value). Every operation issued on a register is, generally, not instantaneous and it can be characterized by two events occurring at its boundaries: an invocation event and a reply event. These events occur at two time instants (called the invocation time and the reply time) according to the fictional global time.

An operation op is complete if both the invocation event and the reply event occurred, otherwise, it failed.Given two operations op and op ′ , their invocation times (t B (op) and t B (op ′ )) and reply times (t E (op) and t E (op ′ )), op precedes op ′ (op ≺ op ′ ) if and only if t E (op) < t B (op ′ ). If op does not precede op ′ and op ′ does not precede op, then op and op ′ are concurrent (noted op||op ′ ). Given a write(v) operation, the value v is said to be written when the operation is complete.

In this paper, we consider a single-writer/multi-reader (SWMR) regular register, as defined by Lamport [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF], which is specified as follows:

-Termination: if a correct client invokes an operation op, op completes. -Validity: A read returns the last written value before its invocation (i.e. the value written by the latest completed write preceding it), or a value written by a write concurrent with it.

Lower bounds

In this section we prove lower bounds with respect to the minimum fraction of correct servers to implement safe registers in presence of mobile Byzantine failures 2 . In particular we first prove lower bounds for the (∆S, CAM ) and (∆S, CU M ) models and then we extend those results to (IT B, CAM ) and (IT B, CU M ) models. The first observation that raises is that in presence of mobile agents in the round-free models there are several parameters to take into account with respect to the round-based model. Let us start considering that the set of Byzantine servers changes its composition dynamically time to time. This yields to the following question: does it impact on the read() duration? Or, in other words, such operation has to last as less as possible or until it eventually terminates? In this chapter we consider the read() operation duration as a parameter itself, allowing us to easily verify when the variation of such parameter has any impact on lower bounds. Here below the list of parameters we take into account.

• servers knowledge about their failures state (CAM, CU M );

• the relationship between δ and ∆ (that states how many Byzantine servers there may be during an operation);

• T r , the read() operations duration;

1 It is trivial to prove that in our model, if clients are Byzantine, it is impossible to implement deterministically even a safe register. A Byzantine client may always introduce a corrupted value, and a server cannot distinguish between a correct client and a Byzantine one. 2 Results on safe register can be directly extended to the other register specifications.

• γ, the upper bound on the time during which a server can be in a cured state (the design of an optimal maintenance() operation is out of the scope of this thesis, thus we use such upper bound as another parameter).

Those parameters allow us to describe different failure models and help us to provide a general framework that produces lower bounds for each specific instance of the MBF models. In the sequel it will be clear that γ varies depending on the coordinated/uncoordinated mobile agents movements (∆S, IT B, IT U ). In other words, in this parameter is hidden the movements model taken into account, so we do not need to explicitly parametrize it. Before to start let us precise that we do not consider the following algorithm families: (i) full information algorithm families (processes exchange information at each time instant); (ii) algorithms characterized by a read operation that does not require a request-reply pattern; (iii) algorithms with non quiescent operation (the message exchange triggered by an operation eventually terminates); and finally (iv) algorithms where clients interact with each other. All results presented in the sequel consider a families of algorithms such that previous characteristics do not hold. The lower bounds proof leverages on the classical construction of two indistinguishable executions. The tricky part is to characterize the set of messages delivered by a client from correct and incorrect servers depending of the read() operation duration. Let T r , T r ≥ 2δ be such duration, each read() operation requires at least a request-reply pattern). We first characterize the correct and incorrect sets of messages, delivered during T r time, with respect to ∆ and γ.

For clarity, in the sequel we note correct message/request/reply a message that carries a valid value when it is sent (i.e., sent by a correct process). Otherwise, the message is incorrect. It has been proven [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] that a protocol P reg implementing a regular register in a mobile Byzantine setting must include in addition to the mandatory read and write operations an additional operation, maintenance, defined below.

Definition 6 (Maintenance operation maintenance) A maintenance operation is an operation that, when executed by a process p i , terminates at some time t leaving p i with a valid state at time t (i.e., it guarantees that p i is correct at time t).

Such operation has a direct impact on the number of correct processes in any time instant. For that reason it is important to characterize its duration, in particular its upper bound in terms of time. The following definition defines γ, the upper bound of the time during which a server can be in a cured state.

Definition 7 (Curing time, γ) We define γ as the maximum time a server can be in a cured state. More formally, let T c the time at which server s c is left by a mobile agent, let op M the first maintenance operation that correctly terminates, then t E (op M ) -T c ≤ γ.

In order to build our indistinguishable execution, we define below a scenario of agents movement. Then, with respect this scenario, we construct two indistinguishable executions. Definition 8 (Scenario S * ) Let S * be the following scenario: for each time T i , i ≥ 0 the affected servers are s (i mod n)f +1 , . . . , s (i mod n)f +f .

In Figure 1 is depicted S * . In particular, the red part is the time where f agents are affecting f servers and the gray part is the time servers are running the maintenance operation.

Let us characterize the P reg protocol in the most general possible way. By definition a register abstraction involves read() and write() operations issued by clients. A read operation involves at least a requestreply communication pattern (i.e., two communication steps). Thus, given the system synchrony, a read() operation op R lasts at least T r ≥ 2δ time. Moreover we consider that a correct server sends a reply message in two occasions: (i) after the delivery of a request message, and (ii) right after it changes its state, at the end of the maintenance operation if an op R is occurring. The latter case exploits the maintenance operation allowing servers to reply with a valid value in case they were Byzantine at the beginning of the read operation. Moreover we assume that in ( * , CAM ) model servers in a cured state do not participate to the read operation. Notice that those servers are aware of their current cured state and are aware of their impossibility to send correct replies. Even though those may seems not very general assumptions, let us just consider that we are allowing servers to correctly contribute to the computation as soon as they can and stay silent when they can not and under those assumptions we prove lower bounds. Thus if we remove those assumptions the lower bounds do not decreases. Scenario and protocol has been characterized. Now we aim to characterize the set of servers, regarding their failure states, that can appear during the execution of the protocol, in particular during the read() operation. Those sets allow us to characterize correct and incorrect messages that a client delivers during a read() operation. This value quantifies in the worst case scenario how many servers can be Byzantine, for at least one time unit, during a read() operation. Figure 2 depicts a scenario where T r = 3δ and during the time interval [t ′ , t ′ +T r ] there is a maximum number of Byzantine servers while in [t ′′ , t ′′ +T r ] this number is not maximal.

Definition 13 (M axSil(t, t + T r )) Let S be a scenario and [t, t + T r ] a time interval. The cardinality of Sil S (t, t + T r ) is maximum with respect to S if for any t ′ , t ′ ≥ 0 we have that |Sil(t, t + T r )| ≥ |Sil(t ′ , t ′ + T r )| and B(t, t + T r ) = M ax B(t, t + T r ). Then we call the value of such cardinality as M axSil S (t, t + T r ). If we consider only one scenario per time then we can omit the subscript related to the scenario and write directly minSil(t, t + T r ).

This value quantifies the maximum number of servers that begin in a cured state a read() operation and are still cured after T rδ time. So that any correct reply sent after such period has no guarantees to be delivered by the client and such servers are assumed to be silent.

Definition 14 (M axCu(t)) Let S be a scenario and t be a time instant. The cardinality of Cu S (t) is maximum with respect to S if for any t ′ , t ′ ≥ 0, we have that |Cu

S (t ′ )| ≤ |Cu S (t)| and B(t, t + T r ) = M ax B(t, t + T r ).

We call the value of such cardinality as M axCu S (t). If we consider only one scenario per time then we can omit the subscript related to it and write directly M axCu(t).

This value quantifies, in the worst case scenario, how many cured servers there may be at the beginning of a read() operation. Figure 3 depicts a scenario where at time t ′ there are the maximum number of cured server while at t ′′ this value is not maximum. Notice that in such figure, in case of a shorter time interval [t ′ , t ′ + 2δ] s 0 would be silent. s 0

s 0 s 1 s 2 s 3 t ′ t ′ + 3δ t ′′ t ′′ + 3δ
s 1 s 2 s 3 t ′ t ′ + 3δ t ′′ t ′′ + 3δ Figure 4: Let [t, t + T r ] be a time interval such that in the depicted scenario | Co(t, t + T r )| = min Co(t, t + T r ). Then in both time intervals [t ′ , t ′ + T r ] and [t ′′ , t ′′ + T r ] we have that | Co(t ′ , t ′ + T r )| = | Co(t ′′ , t ′′ + T r )| = min Co(t, t + T r ).
T r ) = M ax B(t, t + T r ).
In particular let us denote as:

• min BC(t, t + T r ) the minimum number of servers that during a time interval [t, t + T r ] belong to B(t, t + T r ) or Cu(t) (only in (∆S, CU M ) model) and to Co(t + δ, t + T r -δ).
• min CB(t, t + T r ) the minimum number of servers that during a time interval [t, t + T r ] belong to Co(t + δ, t + T rδ) and to B(t, t + T r ).

As we stated before, Byzantine servers set changes during the read() operation op R , so there can be servers that are in a Byzantine state at t B (op R ) and in a correct state before t

E (op R ) -δ (cf. s 0 during s 0 s 1 s 2 s 3 t ′ t ′ + 3δ t ′′ t ′′ + 3δ Figure 5: Let [t, t + T r ] a time interval such that in the depicted scenario CBC(t, t + T r ) = min CBC(t, t + T r ). Then CBC(t ′ , t ′ + T r ) > min CBC(t, t + T r ) and CBC(t ′′ , t ′′ + T r ) = min CBC(t, t + T r ).
[t ′ , t ′ + 3δ] time interval in Figure 5). Those servers contribute with an incorrect message at the beginning and with a correct message after. The same may happen with servers that are correct from t B (op R ) to at least t B (op R ) + δ (so that for sure deliver the read request message and send the reply back) and are affected by a mobile agent after t B (op R ) + δ (cf. s 0 during [t ′′ , t ′′ + 3δ] time interval in Figure 5).

Lemma 1 M ax B(t, t + T r ) = (⌈ Tr ∆ ⌉ + 1)f .
Proof For simplicity let us consider a single agent ma k , then we extend the same reasoning to all the f agents. In [t, t + T r ] time interval, with T r ≥ 2δ, ma k can affect a different server each ∆ time. It follows that the number of times it may change server is Tr ∆ . Thus the affected servers are ⌈ Tr ∆ ⌉ plus the server that was affected at t. Finally, extending the reasoning to f agents, M ax B(t, t + T r ) = (⌈ Tr ∆ ⌉ + 1)f , which concludes the proof.

2

As we see in the sequel, the value of M ax B(t, t + T r ) is enough to compute the lower bound. Now we can define the worst case scenario for a read() operation with respect to S * . Let op be a read operation issued by c i . We want to define, among the messages that can be deliver by c i during op, the minimum amount of messages sent by server when they are in a correct state and the maximum amount of messages sent by servers when they are not in a correct state. In each scenario, we assume that each message sent to or by Byzantine servers is instantaneously delivered, while each message sent to or by correct servers requires δ time. Without loss of generality, let us assume that all Byzantine servers send the same value and send it only once, for each period where they are Byzantine. Moreover, we make the assumption that each cured server (in the CAM model) does not reply as long as it is cured. Yet, in the CUM model, it behaves similarly to Byzantine servers, with the same assumptions on message delivery time.

Definition 17 (M axReplies N Co(t, t + T r ) k ) Let M axReplies N Co(t, t + T r ) k be the multi-set main- tained by client c k containing m ij elements, where m ij is the i -th message delivered by c k and sent at time t ′ , t ′ ∈ [t, t + T r ] by s j such that s j / ∈ Co(t ′ ).
Considering the definitions of both M ax B(t, t + T r ) and M axCu(t) the next Corollary follows: Note that correct replies come from servers that (i) have never been affected during the time interval [t, t + T r ], or (ii) where in a cured state at t but do not belong to the Sil(t, t + T r ) set, or (iii) servers that reply both correctly and incorrectly. The next Corollary follows.

Corollary 2 In the worst case scenario, during a read operation lasting T r ≥ 2δ issued by client c i , c i delivers n-(M ax B(t, t+T r )+M axSil(t, t+T r ))+min CBC(t, t+T r ) correct replies in the (∆S, CAM ) model and n -[M ax B(t, t + T r ) + M axCu(t)] + min CBC(t, t + T r ) correct replies in the (∆S, CU M ) model.

In the following, given a time interval, we characterize correct and incorrect servers involved in such interval. Concerning correct servers, let us first analyze when a client collects x ≤ n different replies and then we extend such result to x > n. Then we do the same for incorrect replies.

Lemma 2 Let op be a read operation issued by client c i in a scenario S * , whose duration is T r ≥ 2δ. Let x, x ≥ 2, be the number of messages delivered by c i during op. If x ≤ n then minReplies Co(t, t + T r ) k contains replies from x different servers.

Proof Let us suppose that minReplies Co(t, t + T r ) k contains replies from x -1 different servers (trivially it can not be greater than x). Without lost of generality, let us suppose that c i collects replies from s 1 , . . . , s x-1 . It follows that there is a server s i , i ∈ [1, x -1] that replied twice and a server s x that did not replied. Let us also suppose w.l.g. that there is one Byzantine mobile agent ma k (i.e., f = 1). If during the time interval [t, t + T r ] s x never replied, then s x has been affected at least during

[t + δ, t + T r -δ -γ + 1].
This implies that T r ≤ ∆ + 2δ + γ. Since s i replies twice then two scenarios are possible during op: (i) s i was first affected by ma k and then became correct (so it replied once), then affected again and then correct again (so it replied twice); (ii) s i was correct (so it replied once), then it was affected by ma k and then correct again (so it replied twice). Let us consider case (ii) (case (i) follows trivially). Since s i had the time to reply (δ), to be affected and then became correct (∆ + γ) and reply again (δ) this means that T r > ∆ + 2δ + γ. A similar result we get in case (i) where the considered execution requires a longer time. This is in contradiction with T r ≤ ∆ + 2δ + γ thus c i gets replies for x different servers.

2

If a client delivers n > x messages then we can apply the same reasoning of the previous Lemma to the first chunk of n messages, then to the second chunk of n messages and so on. Roughly speaking, if n = 5 and a client delivers 11 messages from correct processes, then there are 3 occurrences of the message coming from the first server and 2 occurrences of the messages coming from the remaining servers. Thus the next Corollary directly follows.

Corollary 3 Let op be a read operation issued by client c i in a scenario S * , op duration is T r ≥ 2δ. Let x, x ≥ 2, be the number of messages delivered by c i during op, then minReplies Co(t, t

+ T r ) k contains x mod n messages m ij whose occurrences is ⌊ x n ⌋ + 1 and (n -x (mod n)) messages whose occurrences is ⌊ x n ⌋.
The case of M axReplies N Co(t, t + T r ) k directly follows from scenario S * , since by hypotheses mobile Byzantine agents move circularly from servers to servers, never passing on the same server before having affected all the others. Thus, the following corollary holds. At this point we can compute how many correct and incorrect replies a client c k can deliver in the worst case scenario during a time interval [t, t + T r ]. Trivially, c k in order to distinguish correct and incorrect replies needs to get minReplies Co(t, t + T r ) k > M axReplies N Co(t, t + T r ) k . It follows that the number of correct servers has to be enough to guarantee this condition. Table 2 follows directly from this observation. In a model with b Byzantine (non mobile) a client c i requires to get at least 2b + 1 replies to break the symmetry and thus n ≥ 2b + 1. In presence of mobile Byzantine we have to sum also servers that do not reply (silent) and do not count twice servers that reply with both incorrect and correct values. Proof Let us suppose that n < n CAM LB (n < n CU M LB ) and that protocol P reg does exist. If a client c i invokes a read operation op, lasting T r ≥ 2δ time, if no write operations occur, then c i returns a valid value at time t B (op). Let us consider an execution E 0 where c i invokes a read operation op and let 0 be the valid value at t B (op). Let us assume that all Byzantine severs involved in such operation reply once with 1. From Corollaries 1 and 2, c i collects M axReplies N Co(t, t + T r ) i occurrences of 1 and minReplies Co(t, t + T r ) i occurrences of 0. Since P reg exists and no write operations occur, then c i returns 0. Let us now consider a another execution E 1 where c i invokes a read operation op and let 1 be the valid value at t B (op). Let us assume that all Byzantine severs involved in such operation replies once with 0. From Corollaries 1 and 2 and Corollary 3 and Corollary 4, c i collects M axReplies N Co(t, t + T r ) i occurrences of 0 and minReplies Co(t, t+T r ) i occurrences of 1. Since P reg exists and no write operations occur, then c i returns 1.

Theorem 1 If n < n CAM LB (n < n CU M LB ) as defined in
From Lemma 1 and using values in Table 2 we obtain following equations for both models:

• (∆S, CAM ):

-M axReplies N Co(t, t + T r ) i = M ax B(t, t + T r ) = (⌈ Tr ∆ ⌉ + 1)f -minReplies Co(t, t+T r ) i = n-[M ax B(t, t+T r )+M axSil(t, t+T r )]+min CBC(t, t+T r ) = [2(M ax B(t, t + T r )) + M axSil(t, t + T r ) -min CBC(t, t + T r )] -[(M ax B(t, t + T r ) + M axSil(t, t + T r )) +min CBC(t, t + T r )] = M ax B(t, t + T r ) = (⌈ T r ∆ ⌉ + 1)f • (∆S, CU M ): -M axReplies N Co(t, t + T r ) i = M ax B(t, t + T r ) + M axCu(t) = (⌈ Tr ∆ ⌉ + 1)f + M axCu(t) -minReplies Co(t, t + T r ) i = n -[M ax B(t, t + T r ) + M axCu(t)] + min CBC(t, t + T r ) = [2M ax B(t, t + T r ) + 2M axCu(t)) -min CBC(t, t + T r )]+ -[M ax B(t, t + T r ) + M axCu(t)] + min CBC(t, t + T r ) = M ax B(t, t + T r ) + M axCu(t) = (⌈ T r ∆ ⌉ + 1)f + M axCu(t)
It follows that in E 0 and E 1 c i delivers the same occurrences of 0 and 1, both executions are indistinguishable leading to a contradiction. 2

M axReplies N Co(t, t + T r ) i and minReplies Co(t, t + T r ) i are equal independently from the value assumed by T r , the read() operation duration. From the equation just used in the previous lemma the next Corollary follows.

Corollary 5 For each T r ≥ 2δ if n > n CAM LB (n > n CU M LB ) then M axReplies N Co(t, t + T r ) i < minReplies Co(t, t + T r ) i .
At this point we compute minCu(t), M axSil(t, t + T r ) and min CBC(t, t + T r ) to finally state exact lower bounds depending on the system parameters, in particular depending on ∆, γ and the servers awareness, i.e., (∆S, CAM ) and (∆S, CU M ).

Let us adopt the following notation. Given the time interval [t, t + T r ] let {s 1 , s 2 , . . . , s b } ∈ B(t, t + T r ) be the servers affected sequentially during T r by the mobile agent ma k . Let {s -1 , s -2 , . . . , s -c } ∈ Cu(t) be the servers in a cured state at time t such that s -1 is the last server that entered in such state and s c the first server that became cured. Let t B B(s i ) and t E B(s i ) be respectively the time instant in which s i become Byzantine and the time in which the Byzantine agent left. t B Cu(s i ) and t E Cu(s i ) are respectively the time instant in which s i become cured and the time instant in which it became correct. Considering that ma k moves each ∆ time then we have that t B B(s i-1 )t B B(s i ) = ∆ and t B Cu(s -j )t B Cu(s -j+1 ) = ∆. The same holds for the t E of such states. Moreover t B B(s 1 ) = t B Cu(s -1 ). Now we are ready to build the read scenario with respect to S * . In particular we build a scenario for the (∆S, CAM ) model and one for the (∆S, CU M ) model. Intuitively, the presence of cured servers do not have the same impact in the two models, thus in the (∆S, CU M ) model we maximize such number. Let [t, t + 2δ] be the considered time interval and let ǫ be a positive number arbitrarily smaller, then we consider in the (∆S, CAM ) scenarios t = t E B(s 1 )ǫ (cf. Figure 6) and in the (∆S, CU M ) scenarios t B B(s b ) = t + 2δǫ (cf. Figure 7).

In the sequel we use the notion of Ramp Function:

R(x) = x if x ≥ 0 0 if x < 0 Lemma 3 Let us consider a time interval [t, t + T r ],
T r ≥ 2δ and an arbitrarily small number ǫ > 0, then in fthe

(∆S, CAM ) model M axCu(t) = R(⌈ γ-∆+ǫ ∆ ⌉). s -2=-c s 1 s 2 s -1 s 3=b . . . t t + 2δ
Figure 6: Representation of S * when we consider a (∆S, CAM ) model, in particular t E B(s 1 ) = t + ǫ, for ǫ > 0 and arbitrarily small. Proof As we defined, s -1 is the most recent server that entered in a cured state, with respect to the considered time interval. Intuitively each s -j is in Cu(t) if t E Cu(s -j ) > t. Considering that t E Cu(s -j )t E Cu(s -j-1 ) = ∆ then the number of servers in a cured state at t is M axCu(t) = ⌈ t E Cu(s 1 )-t ∆ ⌉. 3 As we stated, for ( * , CAM ) models we consider scenarios in which t, the beginning of the considered time interval, is just before t E B(s 1 ). Thus given an arbitrarily small number ǫ > 0, let t = t E B(s 1 )ǫ. By construction we know that t B B(s 1 ) = t E B(s 1 ) -∆ = t B Cu(s -1 ). Substituting t B Cu(s -1 ) = t + ǫ -∆, since we consider γ the upper bound for the curing time, then t E Cu(s -1

s -2=-c s 1 s 2 s -1 s 3=b . . . t t + 2δ
) = t + ǫ -∆ + γ . So finally, M axCu(t) = ⌈ t E Cu(s 1 )-t ∆ ⌉ = ⌈ γ-∆+ǫ
∆ ⌉ and since there can no be a negative result then M axCu(t) = R(⌈ γ-∆+ǫ ∆ ⌉). This concludes the proof. 2

Lemma 4 Let us consider a time interval [t, t + T r ], T r ≥ 2δ and an arbitrarily small number ǫ > 0, then

in the (∆S, CU M ) model M axCu(t) = R(⌈ Tr-ǫ-⌈ Tr ∆ ⌉∆+γ ∆ ⌉).
Proof As we defined, s -1 is the most recent server that entered in a cured state, with respect to the considered interval. Intuitively,

s -j is in Cu(t) if t E Cu(s -j ) > t. Considering that t E Cu(s -j )-t E Cu(s -j-1 ) = ∆ then the number of servers in a cured state at t is M axCu(t) = ⌈ t E Cu(s 1 )-t ∆ ⌉.
As we state, for ( * , CU M ) models we consider scenarios in which the end of the considered time interval, is just after t B B(s b ). Thus given an arbitrarily small number ǫ > 0, let t B B(s b ) = t + T rǫ. By construction we know that t B B(s 1 ) = t E B(s 1 )-∆ = t B Cu(s -1 ) and t B B(s 1 ) = t B B(s b )-⌈ Tr ∆ ⌉∆ (cf. Lemma 1). Substituting and considering that t E Cu(s -1 ) = t B Cu(s -1 ) + γ) we get the following:

t E Cu(s -1 ) = t + T r -ǫ -⌈ Tr ∆ ⌉ + γ. Finally M axCu(t) = ⌈ t E Cu(s 1 )-t ∆ ⌉ = ⌈ Tr-ǫ-⌈ Tr ∆ ⌉+γ ∆
⌉ and since there can not be a negative result then

M axCu(t) = R(⌈ Tr -ǫ-⌈ Tr ∆ ⌉∆+γ ∆ ⌉)
. This concludes the proof. 2

Lemma 5 Let us consider a time interval [t, t + T r ], T r ≥ 2δ and an arbitrarily small number ǫ > 0, then in the (∆S, CAM ) model M axSil(t, t

+ T r ) = R(⌈ γ-∆+ǫ-Tr+δ ∆ ⌉).
Proof As we defined, s -1 is the most recent server that entered in a cured state, with respect to the considered interval. Intuitively,

s -j is in Sil(t, t + 2δ) if t E Cu(s -j ) > T r -δ. Considering that t E Cu(s -j ) - t E Cu(s -j-1 ) = ∆ then the number of servers in a silent state at t is M axSil(t, t+2δ) = ⌈ t E Cu(s 1 )-Tr+δ ∆ ⌉.
As we stated for (∆S, CAM ) models we consider scenarios in which t, the beginning of the considered time interval, is just before t E B(s 1 ). Thus given an arbitrarily small number ǫ > 0, let t = t E B(s 1 )ǫ. By construction we know that t B B(s 1 ) = t E B(s 1 ) -∆ = t B Cu(s -1 ). Substituting t B Cu(s -1 ) = t + ǫ -∆, since we consider γ the upper bound for curing time, then

t E Cu(s -1 ) = t + ǫ -∆ + γ . So finally, M axSil(t, t + T r ) = ⌈ t E Cu(s 1 )-Tr+δ ∆ ⌉ = ⌈ γ-∆+ǫ-Tr+δ ∆ ⌉, then since there can not be a negative result M axSil(t, t + 2δ) = R(⌈ γ-∆+ǫ-Tr+δ ∆ ⌉). 2
Lemma 6 Let us consider a time interval [t, t + T r ], T r ≥ 2δ and an arbitrarily small number ǫ > 0, then

in the (∆S, CU M ) model M axSil(t, t + T r ) = ⌈ Tr-ǫ-⌈ Tr ∆ ⌉∆+γ-δ ∆ ⌉.
Proof As we defined, s -1 is the most recent server that entered in a cured state, with respect to the considered interval. Intuitively,

s -j is in Sil(t, t + T r ) if t E Cu(s -j ) > T r -δ.
Considering that t E Cu(s -j )t E Cu(s -j-1 ) = ∆ then the number of servers in a silent state at t is M axSil(t, t+T r ) = ⌈ t E Cu(s 1 )-Tr+δ ∆ ⌉. As we stated for (∆S, CU M ) models we consider scenarios in which t + T r , the end of the considered time interval, is just after t B B(s b ). Thus given an arbitrarily small number ǫ > 0, let t B B(s b ) = t + T rǫ. By construction we know that t B B(s 1 ) = t E B(s 1 ) -∆ = t B Cu(s -1 ) and t B B(s 1 ) = t B B(s b ) -⌈ Tr ∆ ⌉∆ (cf. Lemma 1). Substituting and considering that t E Cu(s -1 = t B Cu(s -1 ) + γ) we get the following:

t E Cu(s -1 = t+T r -ǫ-⌈ Tr ∆ ⌉+γ. Finally M axSil(t, t+T r ) = ⌈ t E Cu(s 1 )-Tr+δ ∆ ⌉ = ⌈ Tr-ǫ-⌈ Tr ∆ ⌉+γ-Tr+δ ∆ ⌉,
then since there can not be a negative result, M axSil(t, t

+ T r ) = ⌈ Tr-ǫ-⌈ Tr ∆ ⌉∆+γ-Tr+δ ∆ ⌉. 2 Lemma 7 Let us consider a time interval [t, t + T r ], T r ≥ 2δ then in the (∆S, CAM ) model. min CBC = R(⌈ Tr ∆ ⌉ -⌈ δ ∆ ⌉) + R(⌈ Tr-γ-Tr+δ ∆ ⌉).
Proof By definition min CBC(t, t + T r ) = min CB(t, t + T r ) + min BC(t, t + T r ).

min CB(t, t + T r ) is the minimum number of servers that correctly reply and then, before t + T r are affected and incorrectly reply. Let us observe that a correct server correctly reply if belongs to Co(t, t + δ), it follows that servers in B(t, t + δ) do not correctly reply. Thus, min CB(t, t + T r ) = M ax B(t, t + T r ) -M ax B(t, t + δ). It may happen that M ax B(t, t + T r ) < M ax B(t, t + T rδ), but obviously there can no be negative servers, so we consider only non negative values, min CB(t, t

+ T r ) = R(M ax B(t, t + T r ) - M ax B(t, t + δ)).
min BC(t, t + 2δ) is the minimum number of servers that incorrectly reply and then become correct in time that the correct reply is delivered. A server is able to correctly reply if it is correct before t + T rδ (the reply message needs at most δ time to be delivered). Thus we are interested in servers that are affected by a mobile agent up to t + T rγδ. For (∆, CAM ) models we consider scenarios in which t, the beginning of the considered time interval, is just before t E B(s 1 ). Thus given an arbitrarily small number ǫ > 0, let t = t E B(s 1 )ǫ. In the time interval [t, t + T rγδ] the number of the mobile agent "jumps" is given by ⌈ Tr-γ-δ ∆ ⌉ Trivially, we can not have a negative number, so it becomes R(⌈

Tr -γ-δ ∆ ⌉). Summing up min CBC = R(⌈ Tr ∆ ⌉ -⌈ δ ∆ ⌉) + R(⌈ Tr -γ-δ ∆ ⌉), which concludes the proof. 2
Lemma 8 Let us consider a time interval [t, t + T r ], T r ≥ 2δ, let ǫ > 0 be an arbitrarily small number.

If

maxCu(t) > 0 or γ > ∆ then in the (∆S, CU M ) model min CB = ⌈ Tr-ǫ-δ ∆ ⌉ otherwise min CB = R(M ax B(t, t + T r ) -M ax B(t, t + T r -δ)).
Proof min CB(t, t + T r ) is the minimum number of servers that correctly reply and then, before t + T r are affected by a mobile agent and incorrectly reply. We are interested in the maximum number of Byzantine servers in B(t, t + T rδ), so that the remaining ones belong to B(t + T rδ, t + T r ), which means that servers in B(t + T rδ, t + T r ) are in Co(t, t + δ) (considering the scenario S * ). Thus, considering that in the (∆, CU M ) model we consider t B B(s b ) = t + T rǫ (ǫ > 0 and arbitrarily small) then we consider the maximum number of "jumps" there could be in the time interval

[t + δ, t + T r -ǫ]. Thus min CB(t, t + T r ) = ⌈ t+Tr-ǫ-t-δ ∆ ⌉ = ⌈ Tr-ǫ-δ ∆ ⌉.
If M axCu(t) = 0 or γ > ∆ then it has no sense to consider the (∆S, CU M ) worst case scenario that aims to maximize cured servers. Thus in this case we consider the (∆S, CAM ) worst case scenario, min CB = R(M ax B(t, t + T r ) -M ax B(t, t + T rδ)), concluding the proof.

2 Proof By definition min CBC(t, t + T r ) = min CB(t, t + T r ) + min BC(t, t + T r ). From Lemma 8, if maxCu(t) > 0 or ∆ > γ then in the (∆S, CU M ) model min CB = ⌈ Tr-ǫ-δ ∆ ⌉ otherwise min CB = R(M ax B(t, t + T r ) -M ax B(t, t + T rδ)). min BC(t, t+T r ) is the minimum number of servers that incorrectly reply and then, before t+T r -δ become correct so that are able to correctly reply in time such that their reply is delivered. In the (∆S, CU M ) model servers may incorrectly reply because affect by a mobile agent or because in a cured state. In the first case, a server is able to correctly reply if it become correct before t + T rδ (the reply message needs at most δ time to be delivered). Thus we consider the maximum number of servers that can be affected in the period t + T rγδ, t + T r , which is ⌈ γ+δ ∆ ⌉. Thus, among the Byzantine servers (i.e., M ax B(t, t + T )) we consider servers not affected in the time interval [t + T rγ + δ, t + T r ]. In other words such servers have γ time to became correct and δ time to reply before the end of the operation. Thus M ax B(t, t + T r ) -M ax(t + T rγ + δ, t + T r ). Again we can not have a negative number, so it becomes R(⌈ Tr ∆ -γ-δ ∆ ⌉). Concerning servers that incorrectly reply when in a cured state, we are interested in servers that correctly reply after in time such that the reply is delivered by the client, i.e., they are not silent. This number is easily computable, M axCu(t) -M axSil(t, t + T r ). Thus min BC(t, t + 2δ) = (M axCu(t)-M axSil(t, t+T r )). Summing up if maxCu(t) > 0 or ∆ > γ, then min CBC = ⌈ Tr-ǫ-δ ∆ ⌉+ Table 3: Values for a general read() operation that terminates after T r time.

M ax B(t, t + T r ) M axCu(t) M axSil(t, t + T r ) (∆S, CAM ) ⌈ Tr ∆ ⌉ + 1 R(⌈ γ-∆+ǫ ∆ ⌉) R(⌈ γ-∆+ǫ-Tr+δ ∆ ⌉) (∆S, CU M ) ⌈ Tr ∆ ⌉ + 1 R(⌈ Tr -ǫ-⌈ Tr ∆ ⌉∆+γ ∆ ⌉) ⌈ γ+δ-ǫ-⌈ Tr ∆ ⌉∆ ∆ ⌉ min CBC(t, t + T r ) (∆S, CAM ) R(⌈ Tr ∆ ⌉ -⌈ δ ∆ ⌉) + R(⌈ Tr-γ-δ ∆ ⌉) (∆S, CU M ) ⌈ Tr-ǫ-δ ∆ ⌉ a +R(⌈ Tr ∆ ⌉ -⌈ γ+δ ∆ ⌉) + (M axCu(t) -M axSil(t, t + T r ))
a if maxCu(t) > 0 otherwise is the same value of min CBC(t, t + Tr) in the ( * , CAM ) model

R(⌈ Tr ∆ ⌉ -⌈ γ-δ ∆ ⌉) + (M axCu(t) -M axSil(t, t + 2δ
)), otherwise min CBC assumes the same values as in the (∆S, CAM ) model, which concludes the proof.

2

In Table 3 are reported all the results found so far for (∆S, * ) models. Such results have been proved considering f = 1. Extending such results to scenario for f > 1 is straightforward in the (∆S, * ) model. The extension to f > 1 in the (IT B, * ) and (IT U, * ) models is less direct. What is left to prove is that the results found for f = 1 can be applied to all other models in which mobile agents move independently from each other. In the following Lemma we employ * to indicate that the result holds for * assuming consistently the value CAM or CU M .

Lemma 10 Let n * LB ≤ α * (∆, δ, γ)f be the impossibility results holding in the (∆S, * ) model for f = 1. If there exists a tight protocol P reg solving the safe register for n ≥ α * (∆, δ, γ)f + 1 (f ≥ 1) then all the Safe Register impossibility results that hold in the (∆S, * ) models hold also in the (IT B, * ) and (IT U, * ) models.

Proof Let us consider the scenario S * for f = 1 and a read() operation time interval [t, t + T r ], t ≥ 0. Depending on the value of t there can be different (but finite) read scenarios, rs 1 , rs 2 , . . . , rs s . By hypothesis there exists P reg solving the safe register for n ≥ α * f (∆, δ, γ)+1 then among the read scenarios RS = {rs 1 , rs 2 , . . . , rs s } all the possible worst case scenarios {wrs 1 , . . . , wrs w } ⊆ RS hold for n = α * (∆, δ, γ)f (meaning that P reg does not exist). We can say that those worst scenarios are equivalent in terms of replicas, i.e., for each wsr k is it possible to build an impossibility run if n = α * (∆, δ, γ) but P reg works if n = α * (∆, δ, γ) + 1 (if we consider f = 1). Let us now consider (∆S, * ) for f > 1. In this case, mobile agents move all together, thus the same wrs k scenario is reproduced f times. For each wrs k scenario is it possible to build an impossibility run if n = α * (∆, δ, γ)f , i.e., α * (∆, δ, γ) -1 non Byzantine servers are not enough to cope with 1 Byzantine server, then it is straightforward that α * (∆, δ, γ)f non Byzantine servers are not enough to cope with f Byzantine servers, the same scenario is reproduced f times. In the case of unsynchronized movements (ITB and ITU) we consider ∆ = min {∆ 1 , . . . , ∆ f }. Each mobile agent generates a different read scenarios, those scenario can be up to f . As we just stated, if P reg exists, those worst case scenarios are equivalent each others in terms of replicas. Since all the worst case scenarios are equivalent in terms of replicas, thus impossibility results holding for mobile agents moving together hold also for mobile agent moving in an uncoordinated way.

2

In [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF], for n ≥ α * (∆, δ, γ)f + 1 (f ≥ 1), it has been presented a tight protocol P reg that solves the Regular Register problem whose bounds match the safe register lower bounds. Thus the next corollary follows.

2δ ≤ ∆<3δ n CAM 4f+1 #reply CAM 2f+1 δ ≤ ∆<2δ n CAM 6f+1 #reply CAM 3f+1 (CUM, ITB) 2δ ≤ ∆<3δ n CU M 7f+1 #reply CU M 4f+1 δ ≤ ∆<2δ n CU M 12f+1 #reply CU M 7f+1
Corollary 6 Let n * LB ≤ α * (∆, δ, γ)f be the impossibility results holding in the (∆S, * ) model for f = 1. All the Safe Register impossibility results hold also in the (IT B, * ) and (IT U, * ) models.

Upper Bounds

In this section, we present an overview of the optimal protocols that implement a SWMR Regular Register in a round-free synchronous system respectively for (IT B, CAM ) and (IT B, CU M ) instances of the proposed MBF model.

Following the same approach we used in [START_REF] Bonomi | Optimal mobile byzantine fault tolerant distributed storage[END_REF] for the (∆S, CAM ) model, our solution is based on the following two key points: (1) we implement a maintenance() operation, in this case executed on demand;

(2) we implement read() and write() operations following the classical quorum-based approach. The size of the quorum needed to carry on the operations, and consequently the total number of servers required by the computation, is dependent on the time to terminate the maintenance() operation, δ and ∆ (see Table 4). The difference with respect (∆S, CAM ) model is that the time at which mobile agents move is unknown. Notice that each mobile ma i agent has it own ∆ i . Since we do not have any other information we consider ∆ = min{∆ 1 , . . . , ∆ f }. The maintenance() operation for (IT B, CAM ) model. This operation is executed by servers on demand (request-reply) when the oracle notifies them that are in a cured state. Notice that in the ( * , CAM ) models servers know when a mobile agent leaves them, thus depending on such knowledge they execute different actions. In particular, if a server s i is not in a cured state then it does nothing, it just replies to ECHO REQ() messages. Otherwise, if a server s i is in a cured state it first cleans its local variables and broadcast to other servers a request. Then, after 2δ time units it removes values that may come from servers that were Byzantine before the maintenance() and updates its state by checking the number of occurrences of each value received from the other servers. Contrarily to the (∆S, CAM ) case, a cured server notifies to all servers that it was Byzantine in the previous δ time period. This is done invoking the awareAll function that broadcasts a default value ⊥ after δ time a server discovered to be in a cured state. This is done to prevent a cured server to collect "slow" replies coming from servers that were affected before the execution of the maintenance() operation. In this model, the curing time γ ≤ 2δ.

The maintenance() operation for (IT B, CU M ) model. In this case servers are not aware of their failure state, thus they have to run such operation even if they are correct or cured. In addition, in the (IT B, CU M ) model, the moment at which mobile agents move is not known, thus as for the (IT B, CAM ) case, a requestreply pattern is used to implement the maintenance() operation. Such operation is executed by servers every 2δ times. In this case, to prevent a cured server to collect "slow" replies coming from servers that were affected before the execution of the maintenance() operation, a server choses a random number to associate Table 5: Parameters for P Rreg Protocol for the (IT B, CU M ) model.

k = ⌈ 2δ ∆ ⌉ ≥ 1 n CU M ≥ (5k + 2)f + 1 #reply CU M ≥ (3k + 1)f + 1 #echo CU M ≥ (3k) + 1f k = 2 12f + 1 7f + 1 6f + 1 k = 1 7f + 1 4f + 1 4f + 1
to such particular maintenance() operation instance 4 , broadcast the ECHO REQ() message and waits 2δ before restart ing the operation. When there is a value whose occurrence overcomes the #echo CU M threshold, such value is stored at the server side. Notice that, contrarily to all the previous models, servers are not aware of their failure state and do not synchronize the maintenance() operation with each other. The first consequence is that a mobile agent may leave a cured server running such operation with garbage in server variables, making the operation unfruitful. Such server has to wait 2δ to run again the maintenance() operation with clean variables, so that next time it will be effective, which implies γ ≤ 4δ.

The write operation. To write a new value v, the writer increments its sequence number csn and propagates v and csn to all servers via a WRITE messages. Then, it waits for δ time units (the maximum message transfer delay) before returning. When a server s i delivers a WRITE, it updates its local variables and sends a REPLY message to all clients that are currently reading to allow them to complete their read operation.

The read operation. When a client wants to read, it broadcasts a READ request to all servers and then waits 2δ time (i.e., one round trip delay) to collect replies. When it is unblocked from the wait statement, it selects a value v occurring enough number of times (see #reply C * M from Table 4) from the replies set, sends an acknowledgement message to servers to inform that its operation is now terminated and returns v as result of the operation. When a server s i delivers a READ(j) message from client c j , it first puts its identifier in the pending read set to remember that c j is reading and needs to receive possible concurrent updates and it sends a reply back to c j .

P reg in the (IT B, CAM)model

The protocol P reg for the (IT B, CAM ) model is described in Figures 8910, which present the maintenance(), write(), and read() operations, respectively.

Local variables at client c i . Each client c i maintains a set reply i that is used during the read() operation to collect the three tuples j, v, sn sent back from servers. In particular v is the value, sn is the associated sequence number and j is the identifier of server s j that sent the reply back. Additionally, c i also maintains a local sequence number csn that is incremented each time it invokes a write() operation and is used to timestamp such operations monotonically.

Local variables at server s i . Each server s i maintains the following local variables (we assume these variables are initialized to zero, false or empty sets according their type):

• V i : an ordered set containing d tuples v, sn , where v is a value and sn the corresponding sequence number. Such tuples are ordered incrementally according to their sn values. The function insert(V i , v k , sn k ) places the new value in V i according to the incremental order and, if there are more than d values, it discards from V i the value associated to the lowest sn.

• pending read i : set variable used to collect identifiers of the clients that are currently reading.

• cured i : boolean flag updated by the cured state oracle. In particular, such variable is set to true when s i becomes aware of its cured state and it is reset during the algorithm when s i becomes correct.

• echo vals i and echo read i : two sets used to collect information propagated through ECHO messages.

The first one stores tuple j, v, sn propagated by servers just after the mobile Byzantine agents moved, while the second stores the set of concurrently reading clients in order to notify cured servers and expedite termination of read().

• curing i : set used to collect servers running the maintenance() operation. Notice, to keep the code simple we do not explicitly manage how to empty such set since has not impact on safety properties.

In order to simplify the code of the algorithm, let us define the following functions:

• select d pairs max sn(echo vals i ): this function takes as input the set echo vals i and returns, if they exist, three tuples v, sn , such that there exist at least #echo CAM occurrences in echo vals i of such tuple. If more than three of such tuple exist, the function returns the tuples with the highest sequence numbers.

• select value(reply i ): this function takes as input the reply i set of replies collected by client c i and returns the pair v, sn occurring at least #reply CAM times (see Table ??). If there are more pairs satisfying such condition, it returns the one with the highest sequence number.

• delete cured values(echo vals): this function takes as input echo vals i and removes from f w vals i all values coming from servers that sent an ECHO() message containing ⊥.

The maintenance() operation. Such operation is executed by servers on demand when the oracle notifies them that are in a cured state. Notice that in the ( * , CAM ) models servers knows when a mobile agent leaves them, thus depending on such knowledge they execute different actions. In particular, if a server s i is not in a cured state then it does nothing, it just replies to ECHO REQ() messages. Otherwise, if a server s i is in a cured state it first cleans its local variables and broadcast to other servers an echo request then, after 2δ time units it removes value that may come from servers that were Byzantine before the maintenance() and updates its state by checking the number of occurrences of each pair v, sn received with ECHO messages.

In particular, it updates V i invoking the select three pairs max sn(echo vals i ) function that populates V i with d tuples v, sn . At the end it assigns f alse to cured i variable, meaning that it is now correct and the echo vals i can now be emptied. Contrarily to the (∆S, CAM ) case, cured server notifies to all that it has been Byzantine in the previous δ time period. This is done invoking the awareAll function that broadcast a default value ⊥ after δ time that a server discovered to be in a cured state. The write() operation. When the writer wants to write a value v, it increments its sequence number csn and propagates v and csn to all servers. Then it waits for δ time units (the maximum message transfer delay) before returning. When a server s i delivers a WRITE, it updates its local variables and sends a REPLY() message to all clients that are currently reading (clients in pending read i ) to notify them about the concurrent write() operation and to each server executing the maintenance() operation (servers in curing i ). --------------------------------- ----------------------------------when ECHO (j, V j ) is received: ----------------------------------when ECHO REQ (j) is received: The read() operation. When a client wants to read, it broadcasts a READ() request to all servers and waits 2δ time (i.e., one round trip delay) to collect replies. When it is unblocked from the wait statement, it selects a value v invoking the select value function on reply i set, sends an acknowledgement message to servers to inform that its operation is now terminated and returns v as result of the operation.

(19) for each ( v, sn ∈ V j do (20) echo vals i ← echo vals i ∪ v, sn j ; (21) endFor
(22) curing i ← curing i ∪ j; (23) if (V i = ∅) (24) send ECHO(i, V i ); (25) endif
When a server s i delivers a READ(j) message from client c j it first puts its identifier in the set pending read i to remember that c j is reading and needs to receive possible concurrent updates, then s i checks if it is in a cured state and if not, it sends a reply back to c j . Note that, the REPLY() message carries the set V i .

When a READ ACK(j) message is delivered, c j identifier is removed from both pending read i set as it does not need anymore to receive updates for the current read() operation.

P reg in the (IT B, CUM)model

P reg Detailed Description The protocol P reg for the (IT B, CU M ) model is described in Figures 111213, which present the maintenance(), write(), and read() operations, respectively. Table 5 reports the parameters for the protocol. In particular n CU M is the bound on the number of servers, #reply CU M is minimum number of occurrences from different servers of a value to be accepted as a reply during a read() operation and #echo CU M is the minimum number of occurrences from different servers of a value to be accepted during the maintenance() operation.

reply i ← ∅; (02) broadcast READ(i); (03) wait (2δ); (04) v, sn ← select value(reply i ); (05) broadcast READ ACK(i); (06) return v; ------------------------ when REPLY (j, V j ) is received: (07) for each ( v, sn ∈ V j ) do (08) reply i ← reply i ∪ { j, v, sn }; (09) endFor ========= Server code ========== when READ (j) is received: (10) pending read i ← pending read i ∪ {j}; (11) if (V i = ∅) (12)
then send REPLY (i, V i ); (13) endif ------------------------when READ ACK (j) is received: (14) pending read i ← pending read i \ {j}; Local variables at client c i . Each client c i maintains a set reply i that is used during the read() operation to collect the three tuples j, v, sn sent back from servers. In particular v is the value, sn is the associated sequence number and j is the identifier of server s j that sent the reply back. Additionally, c i also maintains a local sequence number csn that is incremented each time it invokes a write() operation and is used to timestamp such operations monotonically.

Local variables at server s i . Each server s i maintains the following local variables (we assume these variables are initialized to zero, false or empty sets according their type):

• V i : an ordered set containing 3 tuples v, sn , where v is a value and sn the corresponding sequence number. Such tuples are ordered incrementally according to their sn values.

• V saf e j : this set has the same characteristic as V j . The insert(V saf e i , v k , sn k ) function places the new value in V saf e i according to the incremental order and if dimensions exceed 3 then it discards from V saf e i the value associated to the lowest sn.

• W i : is the set where servers store values coming directly from the writer, associating to it a timer, v, sn, timer . Values from this set are deleted when the timer expires or has a value non compliant with the protocol.

• pending read i : set variable used to collect identifiers of the clients that are currently reading.

• echo vals i and echo read i : two sets used to collect information propagated through ECHO messages.

The first one stores tuple j, v, sn propagated by servers just after the mobile Byzantine agents moved, while the second stores the set of concurrently reading clients in order to notify cured servers and expedite termination of read().

• curing i : set used to collect servers running the maintenance() operation. Notice, to keep the code simple we do not explicitly manage how to empty such set since has not impact on safety properties.

In order to simplify the code of the algorithm, let us define the following functions:

• select three pairs max sn(echo vals i ): this function takes as input the set echo vals i and returns, if they exist, three tuples v, sn , such that there exist at least #echo CU M occurrences in echo vals i of such tuple. If more than three of such tuples exist, the function returns the tuples with the highest sequence numbers.

• select value(reply i ): this function takes as input the reply i set of replies collected by client c i and returns the pair v, sn occurring occurring at least #reply CU M times. If there are more pairs with the same occurrence, it returns the one with the highest sequence number.

• conCut(V i , V saf e i , W i ): this function takes as input three 3 dimension ordered sets and returns another 3 dimension ordered set. The returned set is composed by the concatenation of V saf e i • V i • W i , without duplicates, truncated after the first 3 newest values (with respect to the timestamp). e.g.,

V i = { v a , 1 , v b , 2 , v c , 3 , v d , 4 } and V saf e i = { v b , 2 , v d , 4 , v f , 5 } and W i = ∅, then the returned set is { v c , 3 , v d , 4 , v f , 5 }.
The maintenance() operation. Such operation is executed by servers every 2δ times. Each time s i resets its variables, except for W i (that is continuously checked by the function timerCheck()) and the content of V saf e i , which overrides the content of V i , before to be reset. Then s i choses a random number to associate to such particular maintenance() operation instance 5 , broadcast the ECHO REQ() message and waits 2δ before to restart the operation. In the meantime ECHO() messages are delivered and stored in the echo vals i set. When there is value v whose occurrence overcomes the #echo CU M threshold, such value is stored in V saf e i and a REPLY() message with v is sent to current reader clients (if any).

operation timerCheck(W i ) executed while (TRUE) : (01) for each ( v, csn , timer -----------------------------------operation maintenance() executed while (TRUE) : (06) echo vals i ← ∅; V i ← V saf e i ; V saf e ← ∅; (07) rand ← new rand(); (08) broadcast ECHO REQ(i, rand); (09) wait(2δ); ----------------------------------when select three pairs max sn(echo vals i ) = ⊥ (10) insert(V saf e i , select three pairs max sn(echo vals i )); [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF] for each (j ∈ (pending read i ∪ echo read i )) do [START_REF] Malkhi | Byzantine quorum systems[END_REF] send REPLY (i, V saf e ) to c j ; (13) endFor -------------------------------------when ECHO (j, S, pr, r) is received: [START_REF] Martin | Small byzantine quorum systems[END_REF] if (rand = r)then: [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] echo vals i ← echo vals i ∪ v, sn j ; [START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF] echo read i ← echo read i ∪ pr; (17) endIf ----------------------------------when ECHO REQ (j, r) is received: Notice that, contrarily to all the previous models, servers are not aware about their failure state and do not synchronize the maintenance() operation with each other. The first consequence is a that a mobile agent may leave a cured server running such operation with garbage in server variables, making the operation unfruitful. Such server has to wait 2δ to run again the maintenance() operation with clean variables, so that next time it will be effective, which implies γ ≤ 4δ. The write() operation. When the writer wants to write a value v, it increments its sequence number csn and propagates v and csn to all servers. Then it waits for δ time units (the maximum message transfer delay) before returning. When a server s i delivers a WRITE message, it updates W i , associating to such value a timer 4δ. 4δ it is a consequence of the double maintenance() operation that a cured server has to run in order to be sure to be correct. Thus if a server is correct it keeps v in W i during 4δ, which is enough for our purposes. On the other side a cured servers keeps a value (not necessarily coming from a write() operation) no more than the time it is in a cured state, 4δ, which is safe. After storing v in W i , such value is inserted in REPLY() message to all clients that are currently reading (clients in pending read i ) to notify them about the concurrent write() operation and to any server executing the maintenance() operation (servers in curing i ). The read() operation. When a client wants to read, it broadcasts a READ() request to all servers and waits 2δ time (i.e., one round trip delay) to collect replies. When it is unblocked from the wait statement, it selects a value v invoking the select value function on reply i set, sends an acknowledgement message to servers to inform that its operation is now terminated and returns v as result of the operation.

j ∈ W i ) do (02) if (Expires(timer) ∧ (timer > 4δ)) (03) W i ← W i \ v, csn , timer j ; (04) endif (05) endFor -
(18) Set i ← ∅; (19) for each v, csn , epoch j ∈ W i do; (20) Set i ← Set i ∪ v, csn j ; (21) endFor (22) send ECHO(i, V i ∪ Set i , r) to s j ;
When a server s i delivers a READ(j) message from client c j it first puts its identifier in the set pending read i to remember that c j is reading and needs to receive possible concurrent updates, then s i sends a reply back to c j . Note that, in the REPLY() message is carried the result of conCut(V i , V saf e i , W i ). In this case, if the server is correct then V i contains valid values, and V saf e i contains valid values by construction, since it comes from values sent during the current maintenance(). If the server is cured, then V i and W i may contain any value. Finally, s i forwards a READ FW message to inform other servers about c j read request. This is useful in case some server missed the READ(j) message as it was affected by mobile Byzantine agent when such message has been delivered.

When a READ ACK(j) message is delivered, c j identifier is removed from both pending read i set as it does not need anymore to receive updates for the current read() operation.

Correctness

Correctness (IT B, CAM)

To prove the correctness of P reg , we first show that the termination property is satisfied i.e, that read() and write() operations terminates.

Lemma 11 If a correct client c i invokes write(v) operation at time t then this operation terminates at time t + δ.

Proof The claim follows by considering that a write confirmation event is returned to the writer client c i after δ time, independently of the behavior of the servers (see lines 03-04, Figure 9). 2

Lemma 12 If a correct client c i invokes read() operation at time t then this operation terminates at time t + 2δ.

Proof The claim follows by considering that a read() returns a value to the client after 2δ time, independently of the behavior of the servers (see lines 03-06, Figure 10). (06) return v; -----------------------when REPLY (j, V j ) is received:

(07) for each ( v, sn ∈ V j ) do (08) reply i ← reply i ∪ { j, v, sn }; (09) endFor ========= Server code ========== when READ (j) is received: [START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF] pending read i ← pending read i ∪ {j}; [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF] -----------------------when READ FW (j) is received: (13) pending read i ← pending read i ∪ {j}; ----------------------- Proof The proof follows from Lemma 11 and Lemma 12.

send REPLY (i, conCut(V i , V saf e i , W i )); (12) broadcast READ FW(j); -
2

Validity property is proved with the following steps:

• 1. maintenance() operation works (i.e., at the end of the operation n-f servers store valid values). In particular, for a given value v stored by #echo correct servers at the beginning of the maintenance() operation, there are nf servers that may store v at the end of the operation;

• 2. given a write() operation that writes v at time t and terminates at time t+δ, there is a time t ′ > t+δ after which #reply correct servers store v.

• 3. at the next maintenance() operation after t ′ there are #replyf = #echo correct servers that store v, for step (1) this value is maintained.

• 4. the validity follows considering that the read() operation is long enough to include the t ′ of the last written value before the read() and V is big enough to do not be full filled with new values before t ′ .

Before to prove the correctness of the maintenance() operation let us see how many Byzantine agent there may be during such operation. Since the cured server run it as soon as the mobile agent ma i leaves it, then ma i movement are aligned to such operation, this agent contribution is 2δ ∆ = k. All the others f -1 mobile agent are not aligned, thus their contribution is M ax B(t, t + 2δ) = k + 1. Thus there are k + (k + 1) × (f -1) Byzantine servers during the 2δ time maintenance() operation.

Lemma 13 (Step 1) Let T i = t be the time at which mobile agent ma i leave s c . Let v be the value stored at #echo CAM servers s j / ∈ B(t, t + δ) ∧ s j ∈ Co(t + δ), v ∈ V j ∀s j ∈ Co(t + δ). At time t + 2δ, at the end of the maintenance(), v is returned to s c by the function select d pairs max sn(echo vals c ).

Proof The proof follows considering that:

• the maintenance() employs a request-reply pattern and during such operation, by hypothesis, there are #echo CAM servers that are never affected during the [T i , T i + δ] time period and are correct at time T i + δ. i.e., there are #echo CAM servers that deliver the ECHO REQ() message (the can be either correct or cured) but are correct at time T i + δ such that the reply is delivered by s c by time T i + 2δ.

• during the maintenance() operation there are k + (k + 1) × (f -1) Byzantine servers, and ( k 2 )f servers that were Byzantine in [tδ, t] time period, thus they could have sent incorrect messages as well.

• each cured servers, invokes AWAREALL() function, sends a ⊥ message twice: when they are aware to be cured and δ time after. Thus by time t+2δ server running the maintenance removes from echo vals the ( k 2 )f messages sent by those servers. In the end there are k + (k + 1) × (f -1) = (k + 1)f -1 messages coming from Byzantine servers in the echo vals c set.

#echo CAM = (k+1)f > (k+1)f -
/ ∈ B(t + δ) such that v ∈ V j .
Proof The proof follows considering that during the write() operation, [t, t+δ], there can be at most ( k 2 +1)f mobile agents. Thus, during such time there are n-(

k 2 +1)f = 2(k +1)f +1-( k 2 +1)f = (k + k 2 +1
)f +1 servers s j that being either cured or correct, execute code in Figure 9, line 05, inserting v in V j . Finally, (k + k 2 + 1)f + 1 > (k + 1)f + 1 = #reply CAM concluding the proof. 2

For simplicity, for now on, given a write() operation op W we call t B (op W ) + δ = t wC the completion time of op W , the time at which there are at least #reply CAM servers storing the value written by op W .

Lemma 15 (Step 3.) Let op W be a write() operation occurring at t B (op W ) = t and let v be the written value and let t wC be its completion time. Then if there are no other write() operations after op W , the value written by op W is stored by all correct servers forever.

Proof Following the same reasoning as Lemma 14, at time t+δ, assuming that in [t, t+δ] there are ( k 2 +1)f , then there are at least (k + k 2 + 1)f + 1 servers s j that being either cured or correct, execute code in Figure 9, line 05, inserting v in V j . Now let us consider the following:

• Let B 1 = B(t, t + δ) be the set containing the ( k 2 + 1)f Byzantine servers during [t, t + δ], so that there are (2k + 1)f + 1 -k 2 = (k + k 2 + 1)f + 1 ≥ #reply CU M non faulty servers storing v;

there are ( k 2 )f Byzantine servers in B 1 that begin the maintenance() operation . At that time there are #reply CAM non faulty servers storing v, being #reply CAM > #echo CAM , for Lemma 13 at the end of the maintenance() operation, by time t + 3δ, those servers obtain v a result of select d pairs max sn(echo vals) invocation, whose is stored in V since there are no other write() operation and since v has the highest associated sequence number.

• Let B 2 = B(t + δ, t + 2δ) be the set containing Byzantine servers in the next δ period. Those servers are k 2 f (it is not k 2 f + 1, otherwise we would count the Byzantine servers at t + δ twice). Thus, at t + 2δ there are

(k + k 2 + 1)f + 1 -k 2 f = (k + 1)f + 1 = #
(k + 1)f + 1 -k 2 f + k 2 f = #reply CAM servers storing v.
Thus, after t + 3δ period there are servers becoming affected that lose v, but there are other f servers that become correct storing v, so that all correct servers store v. Since there are no more write() operation, this reasoning can be extended forever, concluding the proof. Proof The proof simply follows considering that:

• for Lemma 15 if there are no more write() operation then v, after t wC , is in the register forever.

• any new written value is store in an ordered set V (cf. Figure 9 line 05) whose dimension is 3.

• write() operations occur sequentially.

It follows that after the beginning of 3 write() operations, op W k+1 , op W k+2 , op W k+3 , v it may be no more stored in the regular register. Proof The proof follows from Theorem 4 and Theorem 1, i.e., upper bound and lower bound match. In particular Lower bounds are computed using the values in Table 3 to compute n CAM LB as defined in Table 2 for γ ≤ 2δ (cf. Lemma 13). 2

Correctness (IT B, CUM)

To prove the correctness of P reg we demonstrate that the termination property is satisfied i.e, that read() and write() operations terminates. For the validity property we follow te same four steps as defined in Section 5.1.

Lemma 18 If a correct client c i invokes write(v) operation at time t then this operation terminates at time t + δ.

Proof The claim simply follows by considering that a write confirmation event is returned to the writer client c i after δ time, independently of the behavior of the servers (see lines 03-04, Figure 12). Proof The proof follows considering that:

• the maintenance() employs a request-reply pattern and during such operation, by hypothesis, there are #echo CU M servers that are never affected during the [t, t + δ] time period and are storing v at time t + δ. i.e., there are #echo CU M servers that deliver the ECHO REQ() message (the can be either correct or cured) but are storing v in V at time t + δ such that the reply is delivered by s c by time t + 2δ.

• during the maintenance() operation can incorrectly contribute (k + 1)f Byzantine servers, and (2k)f servers that were Byzantine in [t -4δ, t] time period, thus they could be still in a cured state 6 .

• when the ECHO REQ() message is sent, s c uses a random number in order to be able to accept only ECHO() message sent after t.

#echo CU M = (3k)f +1 > 3kf thus Byzantine servers can not force the select three pairs max sn(echo vals c ) function to return a not valid value so it returns v that occurs #reply CU M times, which is true since there exist #echo CU M non faulty servers that reply to the ECHO REQ() message sending back v, concluding the proof. 2

In the sequel we consider γ ≤ 4δ. In the previous Lemma we proved that cured servers s c can get valid values in 2δ time. Contrarily to all the previous model, the maintenance() operation is triggered each 2δ. Thus a mobile agent, just before to leave could leave s c with the timer just reset and garbage in the echo set c and V c sets, which does not allow s c to correctly terminate the operation. Thus s c has to wait 2δ before to effectively starts a correct maintenance() operation. In the sequel we refer to the first maintenance as the operation that may be ineffective and we refer to the second maintenance as the operation that allows a cured server to retrieve and store valid values. It is straightforward that γ ≤ 4δ and the next Corollary just follows.

Corollary 7 Protocol P implements a maintenance() operation that implies γ ≤ 4δ.

Lemma 22 (Step 2.) Let op W be a write(v) operation invoked by a client c k at time t B (op W ) = t then at time t + δ there are at least n -2f > #reply CU M non faulty servers s i such that v ∈ W i (so that when s i invokes conCut(V i , V saf e i , W i ) v is returned).

Proof When the WRITE() message is delivered by non faulty servers s i , such message is stored in W i and a timer associated to it is set to 4δ, after that the value expires. For Lemma 1 in the [t, t + δ] time interval there are maximum 2f Byzantine servers. All the remaining n -2f non faulty servers execute the correct protocol code, Figure 12 line 05 inserting v in W i . Since write() operations are sequential, during [t, t + δ] there is only one new value inserted in W i , which is returned by the function conCut() by construction. 2

For simplicity, for now on, given a write() operation op W we call t B (op W ) + δ = t wC the completion time of op W , the time at which there are at least #reply CU M servers storing the value written by op W .

Lemma 23 (Step 3.) Let op W be a write() operation and let v be the written value and let t wC be its time completion. Then if there are no other write() operation, the value written by op W is stored by all correct servers forever (i.e., v ∈ conCut(V i , V saf e i , W i )).

Proof From Lemma 22 at time t wC there are at least n -2f > #reply CU M non faulty servers s j such that v ∈ W i . For sake of simplicity let us consider Figure 14. Let us consider that:

• for Lemma 22, all non faulty servers s i have v in W i at most at t wC ;

• when s i runs the next maintenance(), v is returned by select three pairs max sn(echo vals i ) function at the end of such operation, and since it is the value with the highest sequence number (there are no other write() operation) then v is inserted in V saf e i (cf. Figure 11 Proof The proof simply follows considering that:

• for Lemma 23 if there are no more write() operation then v, after t wC , is in the register forever.

• any new written value eventually is stored in an ordered set V saf e and then V (cf. Figure 11 line 06 or line 10) whose dimension is three.

• write() operation occur sequentially.

It follows that after three write() operations, op W k+1 , op W k+2 , op W k+3 in V V saf e and W there are three values whose sequence number is higher than the one associated to v, thus by construction conCut() does not return v anymore, v is no more stored in the regular register.

T 0

 0 T 1 T 2 T 3 T 4 T 5 T 6 T 7 . . . . . .

Figure 1 :

 1 Figure 1: Representation of S * where mobile agents affect groups of f different servers each T i period. In particular here γ > ∆.

Figure 3 :

 3 Figure 3: Let us consider the time instant t and the depicted scenario such that |Cu(t)| = M axCu(t). In particular, in this case |Cu(t ′ )| = M axCu(t) and |Cu(t ′′ )| < M axCu(t).

Figure 7 :

 7 Figure 7: Representation of S * when we consider a (∆S, CU M ) model, in particular t B B(s c ) = t + 2δǫ, for ǫ > 0 and arbitrarily small.

Lemma 9

 9 Let us consider a time interval[t, t + T r ], T r ≥ 2δ then in the (∆S, CU M ) model then if maxCu(t) > 0 min CBC = ⌈ Tr-ǫ-δ ∆ ⌉+R(⌈ Tr ∆ ⌉-⌈ γ-δ ∆ ⌉)+(M axCu(t)-M axSil(t, t+T r )), otherwise min CBC assumes the same values as in the (∆S, CAM ) case.

  function awareAll(): (01) broadcast ECHO(i, ⊥) (02) wait(δ); (03) broadcast ECHO(i, ⊥)

Figure 8 :

 8 Figure 8: A M algorithm implementing the maintenance() operation (code for server s i ) in the (IT B, CAM ) model.

Figure 9 :

 9 Figure 9: A W algorithm implementing the write(v) operation in the (IT B, CAM ) model.

Figure 10 :

 10 Figure 10: A R algorithm implementing the read() operation in the (IT B, CAM ) model.

Figure 11 :

 11 Figure 11: A M algorithm implementing the maintenance() operation (code for server s i ) in the (IT B, CU M ) model.

Figure 12 :

 12 Figure 12: A W algorithm implementing the write(v) operation in the (IT B, CU M ) model.

Figure 13 :

 13 Figure 13: A R algorithm implementing the read() operation in the (IT B, CU M ) model.

  Definition 2 (Valid State at time t) Let Ĥ = (H, →) be an execution history of a generic computation and let P be the corresponding protocol. Let p i be a process and let state p i be the state of p i at some time t. state p i is said to be valid at time t if it can be generated by executing P on Ĥ.

  Definition 9 (Failure State of servers in a time interval) Let [t, t+T t ] be a time interval and let t ′ , t ′ > 0, be a time instant. Let s i be a server and state i be s i state, state i ∈ {correct, cured, Byzantine}. Let S(t ′ ) be the set of servers s i that are in the state state i at t ′ , S(t ′ ) ∈ {Co(t ′ ), Cu(t ′ ), B(t ′ )}. S(t, t + T r ) is the set of servers that have been in the state state i for at least one time unit during [t, t + T r ]. More formally, S(t, t + T r ) = t≤t ′ ≤t+Tr S(t ′ ). + T r ] be time a interval such that in the given scenario | B(t, t + T r )| = M ax B(t, t + T r ).In particular we have that in the time interval[t ′ , t ′ + T r ], | B(t ′ , t ′ + T r )| = M ax B(t, t + T r ). While in the time interval [t ′′ , t ′′ + T r ], | B(t ′′ , t ′′ + T r )| < M ax B(t, t + T r ).reply it is not sure that client delivers such reply before the end of T r time. Now we can define the worst case scenarios for the sets we defined so far with respect to S * .Definition 12 (M ax B(t, t + T r )) Let S be a scenario and [t, t + T r ] a time interval. The cardinality of BS (t, t + T r ) is maximum with respect to S if for any t ′ , t ′ > 0, we have that | BS (t, t + T r )| ≥ | BS (t ′ , t ′ + T r )|. Then we call the value of such cardinality as Max BS (t, t + T r ). If we consider only one scenario per time then we can omit the subscript related to the scenario and write directly M ax B(t, t + T r ).

	t ′	t ′ + 3δ	t ′′	t ′′ + 3δ
	s 0
	s 1
	s 2
	s 3
	Figure 2: Let [t, t
	Definition 10 ( CBC(t, t + T r )) Let [t, t + T r ] be a time interval, CBC(t, t + T r ) denotes servers that during a time interval [t, t + T r ] belong first to B(t, t + T r ) or Cu(t) (only in (∆S, CU M ) model) and then
	to Co(t + δ, t + T r -δ) or vice versa.
	In particular let us denote:
	• BC(t, t + T r ) servers that during a time interval [t, t + T r ] belong to B(t, t + T r ) or Cu(t) (only in (∆S, CU M ) model) and to Co(t + δ, t + T r -δ).
	• CB(t, t + T r ) servers that during a time interval [t, t + T r ] belong to Co(t + δ, t + T r -δ) and to B(t, t + T r ).
	Definition 11 (Sil(t, t + T r )) Let [t, t+T r ] be a time interval. Sil(t, t+T r ) is the set of servers in Cu(t, t+
	T R -δ).
	Servers belonging to Sil(t B (op R ), t E (op R )) are servers that do no participate to op R . In oder words,
	those servers in the worst case scenario became correct after t E (opR) -δ, thus if they send back a correct

Table 2 :

 2 Lower bounds on the number of replicas in each model. Let op be a read operation issued by client c i in a scenario S * , op duration is T r ≥ 2δ. Let x, x ≥ 2, be the number of messages delivered by c i during op, then M axReplies N Co(t, t+T r ) k contains x mod n messages m ij whose occurrences is ⌊ x

n CAM LB [2M ax B(t, t + Tr) + M axSil(t, t + Tr)min CBC(t, t + Tr)]f n CU M LB [2(M ax B(t, t + Tr) + M axCu(t, t + Tr))min CBC(t, t + Tr)]f Corollary 4 n ⌋ + 1 and (nx (mod n)) messages whose occurrences is ⌊ x n ⌋.

Table 2 ,

 2 then there not exists a protocol P reg solving the safe register specification in (∆S, CAM ) model ((∆S, CU M ) model respectively).

Table 4 :

 4 Parameters for P Reg Protocol in the (IT B, CAM ) and (IT B, CU M ) models, minimum number of replicas, and minimum expected occurrence of correct values.

	(CAM, ITB)

  operation maintenance() executed while (TRUE) : (04) cured i ← report cured state(); (05) if (cured i ) then (06) cured i ← f alse; (07) curing state i ← true; (08) V i ← ∅; echo vals i ← ∅; pending read i ← ∅;curing i ← ∅;

	(09) broadcast ECHO REQ(i);
	(10) awareAll();
	(11) wait(2δ);
	(12) delete cured values(echo vals);
	(13) insert(V i , select three pairs max sn(echo vals i ));
	(14) for each (j ∈ (curing i )) do
	(15)	send ECHO (i, V i ) to s j ;
	(16) endFor
	(17) curing state i ← false;
	(18) endIf

  [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF]

	========= Client code ==========
	operation read():
	(01) reply i ← ∅;
	(02) broadcast READ(i);
	(03) wait (2δ);
	(04) v, sn ← select value(reply i );
	(05) broadcast READ ACK(i);

  when READ ACK (j) is received: (14) pending read i ← pending read i \ {j}; (15) echo read i ← echo read i \ {j};

  1 thus Byzantine servers can not force the select d pairs max sn(echo vals c ) function to return a not valid value and select d pairs max sn(echo vals c ) returns v that occurs #reply CAM times, concluding the proof. 2 Lemma 14 (Step 2.) Let op W be a write(v) operation invoked by a client c k at time t B (op W ) = t then at time t + δ there are at least #reply CAM servers s j

  reply CAM non faulty servers storing v; there are ( k 2 )f Byzantine servers in B 2 that begin the maintenance() operation during [t + δ, t + 2δ] time interval. There are #reply CAM non faulty servers storing v, being #reply CAM > #echo CAM , for Lemma 13 at the end of the maintenance() operation, by time t + 4δ, those servers, get v invoking select d pairs max sn(echo vals), whose is stored in V since there are no other write() operation and since v has the highest associated sequence number. • Let B 3 = B(t + 2δ, t + 3δ) be the set containing Byzantine servers in the next δ period. Those servers are k 2 f . At t + 3δ there are (k + 1)f + 1 -k 2 f < #reply CAM non faulty servers storing v and the there are ( k 2 )f servers in B 1 that terminated the maintenance() operation storing v. Summing up there are

2

  Lemma 16 (Step 3.) Let op W 0 , op W 1 , . . . , op W k-1 , op W k , op W

k+1 , . . . be the sequence of write() operations issued on the regular register. Let us consider a particular op W k , let v be the value written by op W k and let t E w k be its completion time. Then the register stores v (there are at least #reply CAM correct servers storing it) up to time at least t B W k+3 .

2

  Theorem 3 (Step 4.) Any read() operation returns the last value written before its invocation, or a value written by a write() operation concurrent with it.Proof Let us consider a read() operation op R . We are interested in the time interval[t B (op R ), t B (op R )+δ].Since such operation lasts 2δ, the reply messages sent by correct servers within t B (op R ) + δ are delivered by the reading client. For δ ≤ ∆ < 3δ during [t, t + δ] time interval there are n -k 2 -1 ≥ #reply CAM correct servers that have the time to deliver the read request and reply. Now we have to prove that what those correct servers reply with is a valid value. There are two cases, op R is concurrent with some write() operations or not.op R is not concurrent with any write() operation. Let op W be the last write() operation such that t E (op W ) ≤ t B (op R ) and let v be the last written value. For Lemma 15 after the write completion time t C w there are #reply CAM non faulty servers storing v. Since t B (op R ) + δ ≥ t C w, then there are #reply CAM non faulty servers replying with v (Figure10, lines[START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF][START_REF] Malkhi | Byzantine quorum systems[END_REF]. So the last written value is returned.op R is concurrent with some write() operation. Let us consider the time interval[t B (op R ), t B (op R )+δ].In such time there can be at most two write() operations. Thus for Lemma 16 the last written value before t B (op R ) is still present in #reply CAM non faulty servers. Thus at least the last written value is returned. To conclude, for Lemma 1, during the read() operation there are at most (k + 1)f Byzantine servers, being #reply CAM > (k + 1)f then Byzantine servers may not force the reader to read another or older value and even if an older values has #reply CAM occurrences the one with the highest sequence number is chosen. 2 Theorem 4 Let n be the number of servers emulating the register and let f be the number of Byzantine agents in the (IT B, CAM ) round-free Mobile Byzantine Failure model. Let δ be the upper bound on the communication latencies in the synchronous system. If n = n CAM according to Table ?? then P reg implements a SWMR Regular Register in the (IT B, CAM ) and (IT U, CAM ) round-free Mobile Byzantine Failure model.

Proof The proof simply follows from Theorem 2 and Theorem 3 and considering ∆ = 1 in the case of (IT U, CAM ) model.

2

Lemma 17 Protocol P reg for δ ≤ ∆ < 3δ is tight with respect to γ ≤ 2δ.

2

  Lemma 19 If a correct client c i invokes read() operation at time t then this operation terminates at time t + 2δ.Proof The claim simply follows by considering that a read() returns a value to the client after 2δ time, independently of the behaviour of the servers (see lines 12-15, Figure13).2Theorem 5 (Termination) If a correct client c i invokes an operation, c i returns from that operation in finite time.To easy the next Lemmas let us use state the following result. Lemma 20 Let [t, t + 2δ] be a generic interval, then there are always at least #reply CU M correct servers that reply during the [t, t + δ] time interval. Proof This follows considering the definition of minimum number of correct replies during a time interval (cf. Corollary 2). Since does exist a tight protocol P solving a regular register in the (∆S, CAM ) model, then for Lemma 10, is it possible to apply values from Table 3 to compute the minimum number of correct replies during the considered time interval, substituting values in each case the result is always at least #reply CU M . 2 Lemma 21 (Step 1.) Let T i be the time at which mobile agent ma i leave s c and let t ≤ T i + 2δ the time at which s c run the second maintenance() operation. Let v be the value stored at #echo CU M servers s

	Proof The proof simply follows from Lemma 18 and Lemma 19.	2

j / ∈ B(t, t + δ), v ∈ V j ∀s j / ∈ B(t, t + δ). At time t + 2δ

, at the end of the maintenance(), v is returned to s c by the function select three pairs max sn(echo vals c ).

  line 10), thus such value is present in the ECHO() message replies for the next 2δ time;• this is trivially true up to time t ′ = t + 4δ, for the timer associated to each v in W i . In [t, t ′ ] there are 2k + 1 Byzantine servers, thus v ∈ W j at n -(2k + 1) non faulty servers, and n -(2k + 1) = (3k + 1)f + 1 = #reply CU M ≥ #echo CU M ;• for each non faulty server the next maintenance()operation op M can happen either in [t ′ , t ′ + δ] or in [t ′ + δ, t ′ + 2δ] (cf. Figure14)s 10 and s 11 respectively:t B (op M ) ∈ [t ′ , t ′ + δ] (cf. s 10 Figure 14): s 10 starts op M 1 before t ′ + δ, let us name it server type A. This means that t B (op M -1 ) + δ < t ′δ, thus for Lemma 21, at the end of the operation v ∈ V saf e 10 and during op M 1 v ∈ V 10 ; -t B (op M ) ∈ [t ′ + δ, t ′ + 2δ] (cf. s 11 Figure 14): s 11 starts op M 1 after t ′ + 2δ let us name it server type B. This means that t B (op M -1 ) + δ > t ′ , thus at the end of the operation we can not say that v ∈ V saf e 1 0 but at least during op M -1 v ∈ V 11 . If all non faulty servers are type A, during op M 1 all non faulty servers have v ∈ V and insert v in the ECHO() message. The same happens if all non faulty servers are type B, during op M -1 , all of them inter v in the ECHO() message and the maintenance() operation terminates with such value. If the situation is mixed, then servers type B, when run op M -1 , deliver ECHO() messages from both type A and type B servers. Thus if there are enough occurrence of v they can store v ∈ V saf e b and during op M 1 v ∈ V b . During such operation both servers type A and type B have vinV . Again, if there are enough occurrences of v, the operation ends with v ∈ V saf e b . It follows that servers type A, when run op M 1 delivers ECHO() messages containing v from both type A and type B servers. During the time interval [t ′ , t ′ + 2δ] there are k correct servers that are affected by mobile agent, cf. Figure 14, s 5 and s 6 . At the same time there is server s 0 , type A, that terminate its maintenanace() with v ∈ V saf e 0 , and thus compensates s 5 , allowing s 1 , type B, to terminate the maintenanace() operation with v ∈ V saf e 1 , which compensates s 6 . This cycle, between type A and type B servers can be extended forever. By hypothesis there are no more write() operation, thus all correct servers have v ∈ V saf e or V , and v is returned when servers invoke function conCut(). 2 Lemma 24 (Step 3.) Let op W 0 , op W 1 , . . . , op W k-1 , op W k , op W k+1 , . . . be the sequence of write() operation issued on the regular register. Let us consider a generic op W k , let v be the written value by such operation and let t wC be its completion time. Then v is in the register (there are #reply CU M correct servers that return it when invoke the function conCut()) up to time at least t B W k+3 .

2

  Theorem 6 (Step 4.) Any read() operation returns the last value written before its invocation, or a value written by a write() operation concurrent with it.Proof Let us consider a read() operation op R . We are interested in the time interval[t B (op R ), t B (op R )+δ].Since such operation lasts 2δ, the reply messages sent by correct servers within t B (op R ) + δ are delivered by the reading client. During [t, t + δ], for Lemma 20 there are at least #reply CU M correct servers that reply. Now we have to prove that what those correct servers reply with is a valid value. There are two cases, op R is concurrent with some write() operations or not.op R is not concurrent with any write() operation. Let op W be the last write() operation such that t E (op W ) ≤ t B (op R ) and let v be the last written value. For Lemma 23 after the write completion time t wC there are at least #reply CU M correct servers storing v (i.e., v ∈ conCut(V j , V saf e j )). Since t B (op R )+2δ ≥ t C w, then there are #reply CU M correct servers replying with v (cf. Lemma 20), by hypothesis there are no further write() operation and v has the highest sequence number. It follows that the last written value v is returned.V saf e 9 v ∈ V saf e 10 v ∈ V saf e 11 v ∈ V saf e 12 ∈ V saf e 13 t ′ + 2δ v ∈ V saf e 0 v ∈ V saf e 1 op M -1 op M 1 op M -1 op M 1Figure14: maintenance() operation op M 1 analysis after a write() operation, t ′ = t + 4δ. White rectangles are maintenance() operation run by correct servers. In particular s 10 runs such operation during the first δ period after t ′ , while s 1 1 runs it during the second δ period.

	write(v)	t ′
	s 0
	s 1
	s 2
	s 3
	s 4
	s 5	v ∈ V saf e 5
	s 6
	s 7	. . .
	s 8
	s 9
	s 1 0
	s 1 1
	s 1 2
	s 1 3

v ∈ V saf e 6 v ∈ V saf e 7 v ∈ V saf e 8 v ∈

Consider Figure6, s2 is the most recent server that entered in the cured state. This is the server that spend more time in such state with respect to the others. It follows that other servers are in a cured state if during this time interval there is enough time for a "jump"

Is it out of the scope of this work to describe such function, we assume that Byzantine server can not predict the random number chosen next.

Is it out of the scope of this work to describe such function, we assume that Byzantine server can not predict the random number chosen next. The aim of such number is to prevent Byzantine servers to send reply to maintenance() operations before their invocation, or, in other words, it prevents correct servers to accept those replies.

We prove hereafter that γ ≤ 4δ, but to prove it we have first to prove that the maintenance() lasts 2δ time.

Servers where affected in the previous 4δ time period, thus they are still running the two maintenance() operations, that last at most 4δ.

op R is concurrent with some write() operation. Let us consider the time interval [t B (op R ), t B (op R )+ δ]. In such time there can be at most two write() operations. Thus for Lemma 24 the last written value before t B (op R ) is still present in #reply CU M correct servers and all of them reply (cf. Lemma 20) thus at least the last written value is returned. To conclude, for Lemma 1, during the read() operation there are at most (k + 1)f Byzantine servers and 2k cured servers 7 , being #reply CU M = (3k + 1)f + 1 > (3k + 1)f then Byzantine servers may not force the reader to read another or older value and even if an older values has #reply CU M occurrences the one with the highest sequence number is returned, concluding the proof. 2 Proof The proof follows from Theorem 7 and Theorem 1, i.e., upper bound and lower bound match. In particular Lower bounds are computed using the values in Table 3 to compute n CU M LB as defined in Table 2 for γ ≤ 4δ (cf. Corollary 7). 2

Concluding remarks

We proposed lower bounds and matching upper bounds for the emulation of a regular register in the round free synchronous communication model under unsynchronized moves of Byzantine agents. The computed lower bounds are significantly higher than those computed for synchronized Byzantine agents model. Investigating other classical problems in the same fault model is a challenging path for future research.