Silvia Bonomi
email: bonomi@dis.uniroma1.it

Antonella Del Pozzo
email: delpozzo@dis.uniroma1.it

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

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

Optimal Mobile Byzantine Fault Tolerant Distributed Storage

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free message-passing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. 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. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures.

Introduction

Byzantine fault tolerance is at the core of Distributed Computing and a fundamental building block in any reasonably sized distributed system. Byzantine failures encompass all possible cases that can occur in practice (even unforeseen ones) as the impacted process may simply exhibit arbitrary behavior. Specifically targeted attacks to compromise processes and/or virus infections can indeed cause malicious code execution.

In classical Byzantine fault-tolerance, attacks and infections are typically abstracted as an upper bound f on the number of Byzantine processes that a given set of n processes should be able to tolerate. Such bounds permit to characterize the solvable cases for benchmarking problems in Distributed Computing (e.g. Agreement and Register Emulation). However, this abstraction fails the reality test of long-lived distributed services. With new exploits being publicized daily and hackers offering services at amazingly low prices, every process is bound to be compromised in a long lasting execution. On the light side, dedicated cure and software rejuvenation techniques increase the possibility that a compromised node does not remain compromised forever, and may be aware about its previously compromised status [START_REF] Sousa | Highly available intrusion-tolerant services with proactive-reactive recovery[END_REF].

To integrate both aspects, Mobile Byzantine Failures (MBF) models have been introduced. Then, faults are represented by Byzantine agents that are managed by a powerful omniscient adversary that "moves" them from a process to another. Mobile Byzantine failures that have been investigated so far consider round-based computations, and can be classified according to Byzantine mobility constraints: (i) Byzantines with constrained mobility [START_REF] Buhrman | Optimal resiliency against mobile faults[END_REF] may only move from one process to another when protocol messages are sent (similarly to how viruses would propagate), while (ii) Byzantines with unconstrained mobility [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] 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] may move independently of protocol messages.

Buhrman et al. [START_REF] Buhrman | Optimal resiliency against mobile faults[END_REF] studied the problem of Agreement when Byzantines have constrained mobility. In the case of unconstrained mobility, several variants were investigated, still for the Agreement problem [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] 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. 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] or Bonnet et al. [START_REF] 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 processes 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] 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 processes 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 process is able to detect its own infection after the Byzantine agent left it. More precisely, during the first round following the leave of the Byzantine agent, a process enters a state, called cured, during which it can take preventive actions to avoid sending messages that are based on a corrupted state. Garay [START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF] proposed, in this model, an algorithm that solves Mobile Byzantine Agreement provided that n > 6f . This bound was later dropped to n > 4f by Banu et al. [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF]. Sasaki et al. [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] investigated the same problem in a model where processes do not have the ability to detect when Byzantine agents move, and show that the bound raises to n > 6f . Finally, Bonnet et al. [START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF] considers an intermediate setting where cured processes 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); this subtle difference on the power of Byzantine agents has an important impact on the bounds for solving agreement: the bound becomes n > 5f and is proven tight.

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. Recently, Bonomi et al. [START_REF] Bonomi | Tight self-stabilizing mobile byzantine-tolerant atomic register[END_REF] proposed optimal selfstabilizing 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] 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].

Our Contribution. The main motivation for our work comes from realizing that the hypothesis that Byzantine agent moves are tightly synchronized with protocol rounds is not a realistic assumption, when Byzantine agents are driven by an adversary that can make use of out of band resources for coordinating them. Indeed, infection and cure are independent from the protocol that is executed on the servers, and typically result from external actions.

Our first contribution (Section 3) is to propose and formalize a general mobile Byzantine model, where Byzantine agent movements are decoupled from the protocol computation steps (in particular, movements of the Byzantine agents are no more related to messages that are exchanged through the protocol). We explore the fundamental implications of the relaxed hypothesis about Byzantine agent movements, and nevertheless retain the dimension related to process awareness about its failure state.

The second contribution of the paper is a protocol to emulate a regular register in our general mobile Byzantine model. We first explore (Section 4) the instances of the model where this problem is solvable (e.g. we provide impossibility results for the asynchronous setting), and in the solvable cases, we present and prove protocols (Section 5 and Section 6) whose resilience is optimal with respect to the number of Byzantine agents.

System Models

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 such protocol is totally transparent to clients (i.e., clients do not know the protocol executed by servers). The passage of time is measured by a fictional global clock (e.g., that spans the set of natural integers). Processes in the system do not have access at the fictional global time. At each time t, each process (either client or server) is characterized by its internal state i.e., by the set of all its local variables and the corresponding values. We assume that an arbitrary number of clients may crash while up to f servers are affected, at any time t, by Mobile Byzantine Failures. The Mobile Byzantine Failure adversarial model considered in this paper (and described in details below) is stronger than any other adversary previously considered in the literature [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Buhrman | Optimal resiliency against mobile faults[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].

No agreement abstraction is assumed to be available at each process (i.e. processes are not able to use consensus or total order primitives to agree upon the current values). Moreover, we assume that each process has the same role in the distributed computation (i.e., there is no special process acting as a coordinator). Communication model. Processes communicate trough message passing. In particular, we assume that: (i) each client c i ∈ C can communicate with every server trough a broadcast() primitive, (ii) each server can communicate with every other server trough a broadcast() primitive, and (iii) each server can communicate with a particular client trough 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. We will consider two types of systems: (i) asynchronous (see Section 4.2) and (ii) round-free synchronous (see Sections 5 and 6).

The system is asynchronous in the sense that there not exists any upper bound on communication and computation latencies. As a consequence, messages are delivered but it is not possible do compute any upper bounds on their delivery time. The system is round-free synchronous if: (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 automata 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 Ĥ = (H, →) is a partial order on H satisfying the relation →.

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 Ĥ.

Adversary Model

The Mobile Byzantine Failure (MBF) models considered so far in literature [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Buhrman | Optimal resiliency against mobile faults[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] assume that faults, represented by Byzantine agents, are controlled by a powerful external adversary that "moves" them from a server to another. Note that the term "mobile" does not necessary mean that a Byzantine agent physically moves from one process to another but it rather captures the phenomenon of a progressive infection, that alters the code executed by a process and its internal state.

Mobile Byzantine Models for round-based computations

In all the above cited works the system evolves in synchronous rounds. Every round is divided in three phases: (i) send where processes send all the messages for the current round, (ii) receive where processes receive all the messages sent at the beginning of the current round and (iii) computation where processes process received messages and prepare those that will be sent in the next round. Concerning the assumptions on agent movements and servers awareness on their cured state the Mobile Byzantine Models defined in [START_REF] 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] Buhrman | Optimal resiliency against mobile faults[END_REF][START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] are summarized as follows:

• Garay's model [START_REF] Garay | Reaching (and maintaining) agreement in the presence of mobile faults[END_REF]. In this model, agents can move arbitrarily from a server to another at the beginning of each round (i.e. before the send phase starts). When a server is in the cured state it is aware of its condition and thus can remain silent for a round to prevent the dissemination of wrong information.

• Bonnet et al.'s model [START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF] and Sasaki et al.'s model [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF]. As in the previous model, agents can move arbitrarily from a server to another at the beginning of each round (i.e. before the send phase starts). Differently from the Garay's model, in both models it is assumed that servers do not know if they are correct or cured when the Byzantine agent moved. The main difference between these two models is that in the [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] model a cured process still acts as a Byzantine one extra round.

• Buhrman's model [START_REF] Buhrman | Optimal resiliency against mobile faults[END_REF]. Differently from the previous models, agents move together with the message (i.e., with the send or broadcast operation). However, when a server is in the cured state it is aware of that.

Most of the previously cited models [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Buhrman | Optimal resiliency against mobile faults[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] consider that the Byzantine agents mobility is related to the round-based synchronous system communication. That is, processes execute synchronous rounds composed of three phases: send, receive, compute. Only between two consecutive rounds, Byzantine agents are allowed to move from one node to another. In the sequel we formalize and generalize the MBF model. Our generalization is twofold: (i) we decouple the Byzantine agents movement from the structure of the computation making it round-free and hence suitable for any distributed application and (ii) we model the infection diffusion in relation with the detection/recovery capabilities of servers.

Informally, in the MBF model, when a Byzantine agent is hosted by a process, the adversary takes the entire control of the process making it Byzantine faulty (i.e., it can corrupt the process's local variables, forces the process to send arbitrary messages etc...). Then, the Byzantine agent moves away and it leaves the process with a possible corrupted state (i.e., in cured state). Such movement abstracts, for example, a virus that has been detected and putted in quarantine or a software update/patching of the machine.

As in the case of round-based MBF models [START_REF] Banu | An improved byzantine agreement algorithm for synchronous systems with mobile faults[END_REF][START_REF] Bonnet | Tight bound on mobile byzantine agreement[END_REF][START_REF] Buhrman | Optimal resiliency against mobile faults[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], we assume that any process previously infected by a mobile Byzantine agent has access to a tamper-proof memory storing the correct protocol code. However, a healed (cured) server may still have a corrupted internal state and cannot be considered correct. As a consequence, the notions of correct and faulty process need to be redefined when dealing with Mobile Byzantine Failures. Definition 3 (Correct process at time t) Let Ĥ = (H, →) be an execution history and let P be the protocol generating Ĥ. A process is said to be correct at time t if (i) it is correctly executing its protocol P and (ii) its state is a valid state at time t. We will denote as Co(t) the set of correct processes at time t while, given a time interval [t, t ], we will denote as Co([t, t ]) the set of all the processes that are correct during the whole interval

[t, t ] (i.e., Co([t, t ]) = τ ∈ [t,t ] Co(τ )).
Definition 4 (Faulty process at time t) Let Ĥ = (H, →) be an execution history and let P be the protocol generating Ĥ. A process is said to be faulty at time t if it is controlled by a mobile Byzantine agent and it is not executing correctly its protocol P (i.e., it is behaving arbitrarily). We will denote as B(t) the set of faulty processes at time t while, given a time interval [t, t ], we will denote as B([t, t ]) the set of all the processes that are faulty during the whole interval [t, t ] (i.e., B([t, t ]) = τ ∈ [t,t ] B(τ )). Definition 5 (Cured process at time t) Let Ĥ = (H, →) be an execution history and let P be the protocol generating Ĥ. A process is said to be cured at time t if (i) it is correctly executing its protocol P and (ii) its state is not a valid state at time t. We will denote as Cu(t) the set of cured processes at time t while, given a time interval [t, t ], we will denote as Cu([t, t ]) the set of all the processes that are cured during the whole interval [t, t ] (i.e., Cu([t, t ]) = τ ∈ [t,t ] Cu(τ )).

Mobile Byzantine Models for round-free computations

We will discuss further how the MBF model for round-free computations introduced informally in the previous section is able to abstract different attack scenarios mentioned in Section 1. In addition, we will classify its six possible instances (see Figure 1) according to the adversary power (from the weakest adversary model (∆S, CAM ) to the strongest one (IT U, CU M )) showing the relationships between them.

Our model takes into account two different attack dimensions: (i) how the external adversary can coordinate the movement of the Byzantine agents and (ii) the process awareness about their current failure state. The first point abstracts the capability of the external adversary to propagate the infection with respect to the detection and recovery capability of processes while the second point distinguishes between detection and proactive recovery capabilities. Thus, any instance of our MBF model is characterized by a pair (X, Y ), where X represents the coordination aspect (i.e., one among ∆S, IT B and IT U ) and Y represents the process awareness (i.e., CAM vs. CU M ).

The coordination dimension allows to characterize the infection spreading from a time point of view. In particular:

• (∆S, * ) allows to consider coordinated attacks where the external adversary needs to control a subset of machines. In this case, compromising new machines will take almost the same time as the time needed to detect the attack or the time necessary to rejuvenate. This may represent scenarios with low diversity where compromising time depends only on the complexity of the exploit and not on the target server. More formally, the external adversary moves all the f mobile Byzantine Agents at the same time t and movements happen periodically (i.e., movements happen at time t 0 + ∆, t 0 + 2∆, . . . , t 0 + i∆, with i ∈ N).

• (IT B, * ) slightly relaxes the assumption about the time of the infection propagation. In particular, in this case the Byzantine agents may affect different servers for different periods of time. This abstracts in some way the possible different complexities of various attack steps (each mobile agent can do a set of exploits and each exploit may take different time to succeed and then to be detected). As a consequence, we are able to capture possible differences in the detection and the rejuvenation times that are now different from server to server. More formally, each of the f Mobile Byzantine Agent ma i is forced to remain on a process 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.

• (IT U, * ) further relaxes the coordination assumption and allows to consider extremely fast infection and detection/rejuvenation processes. More formally, each Mobile Byzantine agent ma i is free to move at any time (i.e., it may occupy a process for one time unit, corrupt its state and then leave). This case can be seen as a particular case of IT B where ∆ i = 1 for each mobile agent ma i .

Let us note that, obviously, (∆S, * ) is the more restrictive coordination case with respect to the adversary power while (IT U, * ) represents the maximum freedom (from the coordination point of view) for the external adversary.

Example of (∆S, * ) coordination, (IT B, * ) coordination and (IT U, * ) coordination are shown respectively in Figure 2, Figure 3 and Figure 4 (where ma i denotes the mobile Byzantine agents). The awareness dimension allows to distinguish between servers under continuous monitoring from the non-monitored ones. Monitored systems are, in fact, characterized by detection and reaction capabilities that enable them to detect their failure state and to act accordingly. On the contrary, non-monitored servers have no self-diagnosis capabilities but they can try to prevent infections by adopting pessimistic strategies that include proactive rejuvenation. In particular:

s 5 s 4 s 3 s 2 s 1 s 0 ma 1 ma 2 t 0 t 0 + ∆ . . . t 0 + i∆
• ( * , CAM ) is able to capture scenarios where servers are aware of a past infection as they abstract environments characterized by the presence of monitors (e.g., antivirus, Intrusion Detection System etc...) that are able to detect the infection and notify the server when the threat is no more affecting the server. • ( * , CU M ) represents situations where the server is not aware of a possible past infection. This scenario is typical of distributed systems subject to periodic maintenance and proactive rejuvenation. In this systems, there is a schedule that reboots all the servers and reloads correct versions of the code to prevent infections to be propagated in the whole network. However, this happens independently from the presence of a real infection and implies that there could be periods of time where the server execute the correct protocol however its internal state is not aligned with non compromised servers.

s 5 s 4 s 3 s 2 s 1 s 0 ma 1 ma 2 ∆ 2 ∆ 1 |B(t0 + ∆1, t0 + 2∆1)| = f
It is easy to prove that CAM is a stronger awareness condition with respect to CU M and thus represents a restriction over the adversary power.

Combining together a type of movement and one of the two awareness conditions, we obtain six different instances of our MBF model for round-free computations, see Figure 1. The instance (∆S, CAM ) is the strongest one as it is the more restrictive for the external adversary and it provides cured processes with the highest awareness while the instance (IT U, CU M ) represents the weakest model as it considers the most powerful adversary and provides no awareness to cured processes.

As in the round-based models, we assume that the adversary can control at most f Byzantine agents at any time (i.e., Byzantine agents are not replicating themselves while moving).

In our work, only servers can be affected by the mobile Byzantine agents1 . It follows that, at any time t |B(t)| ≤ f . However, during the system life, all servers may be affected by a Byzantine agent (i.e., none of the server is guaranteed to be correct forever). In order to abstract the knowledge a server has on its state (i.e. cured or correct), we assume the existence of a cured state oracle. When invoked via report cured state() function, the oracle returns, in the CAM model, true to cured servers and false to others. Contrarily, the cured state oracle returns always false in the CUM model.

s 5 s 4 s 3 s 2 s 1 s 0 ma 1 ma 2 |B(t)| = f t Figure 4: Example of a (IT U, * ) run with f = 2.
The implementation of the oracle is out of scope of this paper and the reader may refer to [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] for further details.

Registers in MBF model

Register Specification

A register is a shared variable accessed by a set of processes (i.e., 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). The register state is maintained by the set of servers S. 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 (i.e., 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 (i.e., the client issuing the operation does not crash between the invocation time and the reply time). Then, an operation op is failed if it is invoked by a process that crashes before the reply event occurs.

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 )), we say that 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 [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF] specified as follows:

-Termination: if a correct client invokes an operation, it eventually returns from that operation (i.e., every operation issued by a correct client eventually terminates).

-Validity: A read() operation returns the last value written before its invocation (i.e. the value written by the latest completed write() preceding it), or a value written by a concurrent write() operation.

Our impossibility results (reported in the next section) are proven for the case of safe register (weaker than the regular register in the Lamport's hierarchy [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF]). A read operation on a safe register concurrent with a write operation may return any value in the register domain.

We will consider in the sequel only execution histories related to the register computation. In particular, the set of relevant computation events H will be defined by the set of all the operations issued on the register and the happened-before relation will be substituted by the precedence relation ≺ between operations. Thus, we will consider a register execution history specified as ĤR = (H, ≺).

From the specification above, we can define the notion of valid value at time t as follow:

Definition 6 (Valid Value at time t) Let ĤR = (H, ≺) be a register execution history of a regular register R. A valid value at time t is any value returned by a fictional read() operation on the register R executed instantaneously at time t.

A protocol P reg is a collection of distributed algorithms implementing basic register operations (i.e., P reg ⊆ {A R , A W } where A R is the algorithm implementing the read() operation and A W is the algorithm implementing the write() operation). We will say that P reg is correct with respect to its specification if it implements a register satisfying the specification.

Impossibility results

In this section we prove that, contrary to the static Byzantine tolerant implementations of registers, in the case of MBF tolerant implementations a new operation, namely maintenance(), must be implemented to prevent servers from losing the current register value. Then, we will show that in an asynchronous system and in the presence of single Mobile Byzantine Agent, there is no protocol P reg implementing a safe register and consequently a regular register.

Theorem 1 Let n be the number of servers emulating a safe register and let f be the number of Mobile Byzantine Agents affecting servers. Let A R and A W be respectively the algorithms implementing the read() and the write() operation assuming no communication between servers. If f > 0 then there exists no protocol P reg = {A R , A W } implementing a safe register in any of the MBF models for round-free computations.

Proof Let us suppose by contradiction that P reg = {A R , A W } is a correct protocol implementing a safe register. If P reg is correct, it means that both A R and A W implementing respectively the read() and the write() operation terminates i.e., they stop to execute steps when the operation is completed. Let t be the time at which the last operation op terminated and let us assume that no other operation is invoked until time t > t. Let us note that during the time interval [t, t ] no algorithm is running as all the operations issued in the past are completed. As a consequence, no correct server and no cured server will change its state. However, considering that t does not depend on P reg (i.e., it is not controlled by the register protocol but it is defined by clients) and considering the mobility of the Mobile Byzantine agents, we may easily have a run where every correct server is faulty and its state can be corrupted at some time in [t, t ].

Considering that P reg = {A R , A W } and that A R and A W are not running in [t, t ] we can have that every server stores a non valid state at time t and the register value is lost. As a consequence, A R has no way to read a valid value and the validity property is violated. It follows that P reg is not correct and we have a contradiction.

T heorem 1

From Theorem 1 it follows that, in presence of Mobile Byzantine Agents, a new operation must be defined to allow cured servers to restore a valid state and avoid the loss of the register value.

Definition 7 (maintenance() and A M ) 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). A maintenance algorithm A M is an algorithm that implements the maintenance() operation.

As a consequence, any correct protocol P reg must include one more algorithm implementing the maintenance() operation2 so that the corollary follows:

Corollary 1 Let n be the number of servers emulating a register and let f be the number of Mobile Byzantine Agents in the system. That is, if f > 0 then any correct protocol P reg implementing a register in the round-free Mobile Byzantine Failure model must include an algorithm A M (i.e.,

P reg = {A R , A W , A M }).
Corollary 2 Let P reg = {A R , A W , A M } be a protocol implementing a safe register in the (∆S, CAM ) Mobile Byzantine Failure Model. Let f > 0 be the number of Byzantine Agents controlled by the external adversary. Any algorithm A M must involve at least one communication step.

Proof The claim simply follows by considering that cured servers have a compromised state thus, they need to receive information from correct servers in order to be able to update their state to a valid one.

2 Lemma 2 Proof Let us recall that read() and write() operations are issued by clients and that the set of clients C and the set of servers S maintaining the register are disjoint. As a consequence, when a client c i wants to write a new value v in the register, it has necessarily to propagate it in the server set. The same happens when a client c j wants to read: it has to ask servers the most up-to-date value. It follows that a send (request) communication step is necessary.

Impossibilities in Asynchronous System

Let us now show that the send communication step is not sufficient to provide a correct implementation of A W and A R .

In oder to be correct, A W must ensure the termination property. As a consequence, c i must be able to decide when it can trigger the write return event. In particular, this can be done when at least one correct server3 updated its internal state.

Let us recall that (i) processes communicate only by exchanging messages, (ii) clients (and in particular the writer) do not know the failure state of servers and (iii) the system is asynchronous.

As a consequence, the only way c i has to know that at least one server s j updated its state is to wait for an acknowledgement from s j . As a consequence, a second communication step, i.e., a reply step, is necessary for a correct implementation of A W .

The same reasoning applies for the termination of the read() operation and the claim follows.

2 Lemma 1

Lemma 2 Let n be the number of servers emulating a safe register and let f be the number of Byzantine agents in the (∆S, CAM ) Mobile Byzantine Failure model. Let t be a time instant at which f servers are faulty and f other servers are cured. Let op be a maintenance() operation issued at time t. There does not exist a maintenance algorithm A M able to terminate in asynchronous settings leaving cured servers with a valid state.

Proof Consider an arbitrary cured server s in the set of cured servers that triggers a maintenance operation op. Assume that op is implemented by an algorithm A M in asynchronous settings. Two cases may happen: (i) there is no write() operation concurrent with op or (ii) there is at least one concurrent write() operation.

• Case 1: write(v)||op. Considering that no write() is concurrent with op, the only way s has to come back to be correct is to get the valid value from correct servers. As a consequence, every A M must include a communication step where correct servers send their stored value to the cured server s (see Lemma 2). Let us recall that the system is asynchronous; thus it is not possible to bound, a priori, the time needed by such messages to reach s. In addition, s is aware just about its failure state but it is not aware about other failure states (in other words, s cannot know, for any time t, the sets Co(t) and B(t)).

As a consequence, the termination condition of A M will depend on messages delivered by s and coming from other servers. Let us recall that cured servers have a non-valid state and, in order to terminate, A M must be able to decide a valid value to update the state of the cured server.

Thus, the termination condition of A M must be able to select a valid value by considering all the information received by s.

Let us now show that due to the Byzantine agents movement and the asynchrony of the communication, we can always have an indistinguishability situation between valid values and non valid values.

The indistinguishability comes from the following observations:

1. in every time interval [t 0 + j∆, t 0 + (j + 1)∆] (with j ∈ N) the number of correct servers sending valid values is n -(j + 1)f . In fact, at any movement, the adversary may decide to move the Byzantine agents on a totally disjoint set of servers (corrupting each time f new servers) until everyone is corrupted. Where t 0 is the initial time where f servers and all the other servers where correct.

2. messages may take an arbitrary time to reach their destination and, in the worse case, all the messages sent in a long time period may be delivered at the same time and not following the FIFO order.

3. when a server is affected by the Byzantine agents, it can send an arbitrary number of messages with an arbitrary content. In particular, given the sequence of messages sent by a server before its compromising, such sequence can be permuted and sent again creating a symmetry condition.

As a consequence, each time that s evaluates a set of messages, it can always have a symmetric set and it will be forced to wait forever. Hence, the maintenance operation never terminates which contradicts the assumption. The same scenario may happen for every cured server starting a maintenance() operation and there is a time t such that Co(t ) = ∅ and none of the maintenance() operation will terminate.

• Case 2: ∃ write(v)||op. Due to the asynchrony of the system, every write() operation may be completed by interacting with servers always in the time period in which they are faulty. As a consequence, the resulting computation is equivalent to the one in which the write() never happened, we fall down in the previous case and the claim follows.

2 Lemma 2
Theorem 2 Let n be the number of servers emulating the register and let f be the number of Byzantine agents in the (∆S, CAM ) Mobile Byzantine Failure model. If f > 0, then there exists no protocol P reg = {A R , A W , A M } implementing a safe register in a asynchronous system.

Proof Let us consider the time t 0 at which the distributed computation starts. At time t 0 , we have that f servers are affected by the mobile Byzantine agents (i.e., |B(t 0 )| = f ) while all the others are correct (i.e., |Co(t 0 ) = n -f ). At time t 0 + ∆, the adversary moves mobile agents and, in the worse case, such agents affect a set of f servers completely disjoint from the previous one. Thus, in the computation we have f servers controlled by the Byzantine agents (|B(t 0 + ∆)| = f ) , f different servers entering in the cured state (|Cu(t 0 + ∆)| = f )) and n -2f correct processes (|Co(t 0 + ∆)| = n -2f ). Let us recall that, by assumption, cured servers know about their state (see CAM model) and thus they can start executing the maintenance operation running the maintenance algorithm A M . Each of the cured servers at time t 0 + ∆, s, will start a maintenance() operation. Following Lemma 2 there is no A M maintenance algorithm able to terminate leaving s with a valid state under asynchronous communication model. As a consequence, the value of the register is lost and no client is able to return a valid value of the register.

2 T heorem 2

Note that the above result extends to any register specification and to any MBF instance defined in Section 2 since (∆S, CAM ) is the weakest adversary and safe is the weakest specification.

Lower bounds

Before to begin with lower bounds let us prove the following auxiliary Lemma.

Lemma 3 Let t be the time at which server s i enters the cured set. There exists no maintenance algorithm A M that guarantees s i to become correct before t + δ.

Proof The proof simply follow from the proof of Lemma 2, which commands that at least one communication step completes. Being in a synchronous system, such a step requires at most δ time to complete.

2 Lemma 3

In Sections 4.5 and 4.6, we consider the following two possibilities for ∆: (i) δ ≤ ∆ < 2δ, and (ii) 2δ ≤ ∆ < 3δ, both for the (∆S, CAM ) and the (∆S, CU M ) models. In the following, we consider lower bounds with respect to the number of correct servers to implement a safe register. Lower bounds for safe registers trivially extend to any stronger register, as those give the weakest set of guarantees in Lamport's hierarchy [START_REF] Lamport | On interprocess communication. part i: Basic formalism[END_REF]. For each of the cases we consider, we assume that a read() operation with no concurrent write() operation occurs. Now, each read() operation consists of two phases: in the first one, a client requests the current value to all servers, and in the second one, the client collects replies from servers. The necessity for these two steps can be proved following a similar reasoning as in Lemma 1. In each scenario, we assume that each message sent to or by faulty servers is instantaneously delivered, while each message sent to or by correct servers requires δ time. Without loss of generality, let us assume that all faulty servers send the same value and send it only once, for each period where they are faulty. 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 faulty servers, with the same assumptions on message delivery time. We suppose there exists (thanks to Lemma 3) a maintenance() protocol that guarantees cured servers to become correct within δ time. In the sequel, m s j denotes the message m sent by s j .

4.5 δ ≤ ∆ < 2δ, (∆S, CAM ) and (∆S, CU M ) models.

Theorem 3 If δ ≤ ∆ < 2δ, γ ≤ δ and n ≤ 5f , then there exists no protocol P reg that implements a safe register in the (∆S, CAM ) model.

Proof Let us suppose for the purpose of contradiction that such a protocol P reg exists. Suppose now that P reg implements a read() operation whose duration is exactly 2δ. When a client c i invokes a read() operation op, c i successfully reads the register value (i.e., the valid value at t B (op)), by the safe register validity property in the scenario with no concurrent write() operation. In such a scenario (see Figure 5, where we depicted in red and in green the time in which a server is affected and in a cured state respectively), let us consider a first execution E 1 in which the register valid value is 1 and c i invokes op. We also consider one mobile Byzantine agent. Now, if each faulty server replies with 0, then c i collects: {1 s 0 , 0 s 1 , 0 s 2 , 1 s 3 , 0 s 3 , 1 s 4 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 1. Let us now consider a second execution E 0 in which the register stores 0, and c i invokes op. If each faulty server replies with 1, then c i collects: {0 s 0 , 1 s 1 , 1 s 2 , 0 s 3 , 1 s 3 , 0 s 4 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 0. In both executions E 1 and E 0 , c i collects the same set of replies, yet gives two different values, hence a contradiction.

We now extend the indistinguishability argument to longer durations for P reg completion. Assume P reg implements a read() operation has duration 3δ. In such a case (see Figure 6), the previous executions E 1 and E 0 evolve in E 1 (in which c i collects:

{1 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 1 s 3 , 0 s 3 , 1 s 4 , 0 s 4 }) and E 0 (in which c i collects: {0 s 0 , 1 s 1 , 0 s 1 , 1 s 2 , 0 s 3 , 1 s 3 , 0 s 4 , 1 s 4 })
, respectively. Again, since there are not concurrent write() operations, due to the safe register validity property, c i return two different values in the two executions, although the replies c i gets are the same in both cases. The case of duration 4δ is similar. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects:

{1 s 0 , 0 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 1 s 2 , 1 s 3 , 0 s 3 , 1 s 4 , 0 s 4 }) and E 0 (in which c i collects: {0 s 0 1 s 0 , 1 s 1 , 0 s 1 , 1 s 2 0 s 2 , 0 s 3 , 1 s 3 , 0 s 4 , 1 s 4 })
, respectively (see Figure 7). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies. At this point each server replied with two different values. A simple induction argument implies that waiting more does not bring any new way to break symmetry. Proof Let us suppose for the purpose of contradiction that such a protocol P reg exists. Suppose now that P reg implements a read() operation whose duration is exactly 2δ. When a client c i invokes a read() operation op, c i successfully reads the register value (i.e., the valid value at t B (op)), by the safe register validity property in the scenario with no concurrent write() operation. In such a scenario (see Figure 8, where we depicted in red and in yellow the time in which a server is affected and in a cured state respectively), let us consider a first execution E 1 in which the register valid value is 1 and c i invokes op. We also consider one mobile Byzantine agent. Now, if each faulty server replies with 0, then c i collects: {0 s 0 , 1 s 0 , 0 s 1 , 0 s 2 , 0 s 3 , 1 s 4 , 0 s 4 , 1 s 5 , 1 s 6 , 1 s 7 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 1. Let us now consider a second execution E 0 in which the register stores 0, and c i invokes op. If each faulty server replies with 1, then c i collects: {1 s 0 , 0 s 0 , 1 s 1 , 1 s 2 , 1 s 3 , 0 s 4 , 1 s 4 , 0 s 5 , 0 s 6 , 0 s 7 }.

Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 0. In both executions E 1 and E 0 , c i collects the same set of replies, yet gives two different values, hence a contradiction. We now extend the indistinguishably argument to longer durations for P reg completion. Assume P reg implements a read() operation has duration 3δ. In such a case (see Figure 4.5), the previous executions E 1 and E 0 evolve in E 1 (in which c i collects: {0 s 0 , 1 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 0 s 3 , 1 s 4 , 0 s 4 , 1 s 5 , 0 s 5 , 1 s 6 , 1 s 7 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 1 s 1 , 0 s 1 , 1 s 2 , 1 s 3 , 0 s 4 , 1 s 4 , 0 s 5 , 1 s 5 , 0 s 6 , 0 s 7 }), respectively. Again, since there are not concurrent write() operations, due to the safe register validity property, c i returns two different values in the two executions, although the replies c i gets are the same in both cases.

The case of duration 4δ is similar. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects: {0 s 0 , 1 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 1 s 2 , 0 s 3 , 1 s 4 , 0 s 4 , 1 s 5 , 0 s 5 , 1 s 6 , 0 s 6 , 1 s 7 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 1 s 1 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 0 s 4 , 1 s 4 , 0 s 5 , 1 s 5 , 0 s 6 , 1 s 6 , 0 s 7 }), respectively (see Figure 4.5). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies.

Finally, the case of duration 5δ is similar. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects: 4.6 2δ ≤ ∆ < 3δ, (∆S, CAM ) and (∆S, CU M ) models.

{0 s 0 , 1 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 1 s 2 , 0 s 3 , 1 s 3 , 1 s 4 , 0 s 4 , 1 s 5 , 0 s 5 , 1 s 6 , 0 s 6 , 1 s 7 , 0 s 7 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 1 s 1 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 0 s 3 , 0 s 4 , 1 s 4 , 0 s 5 , 1 s 5 , 0 s 6 , 1 s 6 , 0 s 7 , 1 s 7 }),
Theorem 5 If 2δ ≤ ∆ < 3δ, γ ≤ δ and n ≤ 4f , then there exists no protocol P reg that implements a safe register abstraction in the (∆S, CAM ) model.

Proof Let us suppose for the purpose of contradiction that such a protocol P reg exists. Suppose now that P reg implements a read() operation whose duration is exactly 2δ. When a client c i invokes a read() operation op, c i successfully reads the register value (i.e., the valid value at t B (op)), by the safe register validity property in the scenario with no concurrent write() operation. In such a scenario (see Figure 12, where we depicted in red and in green the time in which a server is affected and in a cured state respectively), let us consider a first execution E 1 in which the register valid value is 1 and c i invokes op. We also consider one mobile Byzantine agent. Now, if each faulty server replies with 0, then c i collects: {0 s 0 , 1 s 1 , 1 s 2 , 0 s 3 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 1. Let us now consider a second execution E 0 in which the register stores 0, and c i invokes op. If each faulty server replies with 1, then c i collects: {1 s 0 , 0 s 1 , 0 s 2 , 1 s 3 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 0. In both executions E 1 and E 0 , c i collects the same set of replies, yet gives two different values, hence a contradiction. We now extend the indistinguishability argument to longer durations for P reg completion. Assume P reg implements a read() operation has duration 3δ. In such a case (see Figure 13), the previous executions E 1 and E 0 evolve in E 1 (in which c i collects: {0 s 0 , 1 s 1 , 1 s 1 , 1 s 2 , 0 s 2 , 0 s 3 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 0 s 1 , 0 s 2 , 1 s 2 , 1 s 3 }), respectively. Again, since there are not concurrent write() operations, due to the safe register validity property, c i return two different values in the two executions, although the replies c i gets are the same in both cases. A duration of 4δ allows the same two executions E 1 and E 0 as in the 3δ case (see Figure 14), leading to an identical outcome. The case of duration 5δ is similar. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects: {0 s 0 , 1 s 1 , 1 s 1 , 0 s 1 , 1 s 2 , 0 s 2 , 0 s 3 , 1 s 3 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 0 s 1 , 1 s 1 , 0 s 2 , 1 s 2 , 1 s 3 , 0 s 3 }), respectively (see Figure 15). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies. At this point each server replied with two different values. A simple induction argument implies that waiting more does not bring any new way to break symmetry. Theorem 6 If 2δ ≤ ∆ < 3δ, γ ≤ 2δ and n ≤ 5f , then there exists no protocol P reg that implements a safe register abstractions in the (∆S, CU M ) model.

2 T heorem 3 s 0 s 1 s 2 s 3 read()
Proof Let us suppose for the purpose of contradiction that such a protocol P reg exists. Suppose now that P reg implements a read() operation whose duration is exactly 2δ. When a client c i invokes a read() operation op, c i successfully reads the register value (i.e., the valid value at t B (op)), by the safe register validity property in the scenario with no concurrent write() operation. In such a scenario (see Figure 16, where we depicted in red and in green the time in which a server is affected and in a cured state respectively), let us consider a first execution E 1 in which the register valid value is 1 and c i invokes op. We also consider one mobile Byzantine agent. Now, if each faulty server replies with 0, then c i collects: {0 s 0 , 0 s 1 , 1 s 2 , 1 s 3 , 0 s 4 , 1 s 4 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 1. Let us now consider a second execution E 0 in which the register stores 0, and c i invokes op. If each faulty server replies with 1, then c i collects: {1 s 0 , 1 s 1 , 0 s 2 , 0 s 3 , 1 s 4 , 0 s 4 }. Since P reg implements a safe register and there are not concurrent write() operations, then c i reads the valid value at t B (op), that is, 0. In both executions E 1 and E 0 , c i collects the same set of replies, yet gives two different values, hence a contradiction. We now extend the indistinguishably argument to longer durations for P reg completion. Assume P reg implements a read() operation has duration 3δ. In such a case (see Figure 4.6), we consider n ≤ 6f , so that we build the following executions, E 1 (in which c i collects: {0 s 0 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 1 s 4 , 0 s 5 , 1 s 5 }) and E 0 (in which c i collects: {1 s 0 , 1 s 1 , 0 s 2 , 1 s 2 , 0 s 3 , 0 s 4 , 1 s 5 , 0 s 5 }), respectively. Again, since there are not concurrent write() operations, due to the safe register validity property, c i returns two different values in the two executions, although the replies c i gets are the same in both cases.

When we analyze the case of duration 4δ we consider directly n ≤ 5. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects: Figure 4.6). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies.

{0 s 0 , 1 s 0 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 0 s 4 , 1 s 4 }) and E 0 (in which c i collects: {1 s 0 , 0 s 0 , 1 s 1 , 0 s 2 , 0 s 3 , 1 s 3 , 1 s 4 , 0 s 4 }), respectively (see
When we consider the case of duration 5δ we consider n ≤ 6. The previous executions E 1 and E 0 evolve in E 1 (in which c i collects: {0 s 0 , 1 s 0 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 0 s 3 , 1 s 4 , 0 s 5 , 1 s 5 }) and E 0 (in which c i collects: {0 s 0 , 1 s 0 , 0 s 1 , 1 s 2 , 0 s 2 , 1 s 3 , 0 s 3 , 1 s 4 , 0 s 5 , 1 s 5 }), respectively (see Fig. 4.6). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies. It follows that if does not exist P reg solving the regular register for n ≤ 6f then it is straightforward that such protocol does not exist for n ≤ 5f .

We can proceed in the same way for read() operation whose duration is 6δ (Fig. 4.6) and 7δ ((Fig. 4

.6)).

At this point each server replied with two different values. A simple induction argument implies that waiting more does not bring any new way to break symmetry.

k∆ ≥ 2δ, k ∈ {1, 2} k∆ ≥ 2δ, k ∈ {1, 2} k∆ ≥ 2δ, k ∈ {1, 2} n CAM ≥ (k + 3)f + 1 n CAM ≥ (k + 3)f + 1 n CAM ≥ (k + 3)f + 1 #reply CAM ≥ (k + 1)f + 1 #reply CAM ≥ (k + 1)f + 1 #reply CAM ≥ (k + 1)f + 1 k = 1 4f + 1 2f + 1 k = 2 5f + 1 3f + 1 s 0 s 1 s 2 s 3 s 4 req rep

Optimal Regular Register Implementation in the (∆S, CAM ) model

In this section, we present an optimal protocol P reg that implements a SWMR Regular Register in a round-free synchronous system for (∆S, CAM ) instance of the proposed MBF model. Our solution is based on the following three key points: (1) we implement a maintenance() operation that is executed periodically at each T i = t 0 + i∆ time. In this way, the effect of a Byzantine agent on a server disappears in a bounded period of time;

(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 computed by taking into account the time to terminate the maintenance() operation, δ and ∆; (3) we define a forwarding mechanism to avoid that read() and write() messages are "lost" by some server s i due to a concurrent movement of the Byzantine agent during such operations. Note that even though communication channels are reliable, we may have the following situation: a message is sent by a client at time t and the Byzantine agents move at some t < t + δ. As a consequence, some faulty servers may receive the message in the interval [t, t ] and then agents move leaving cured servers without any trace of the message. Interestingly, we found that the number of replicas needed to tolerate f Byzantine agents does not depend only on f but also on the ∆ and δ relationship (see Table 1).

P reg Detailed Description

The protocol P reg for the (∆S, CAM ) model is described in Figures 222324, 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. 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.

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 tree 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 three values, it discards from V i the value associated to the lowest sn.

• 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 trough 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().

• f w vals i : set variable storing a triple j, v, sn meaning that server s j forwarded a write message with value v and sequence number sn.

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

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 2f + 1 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. Otherwise if there are two tuples, the third tuple returned is ⊥, 0 .

• 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 1). If there are more pairs satisfying such condition, it returns the one with the highest sequence number.

The maintenance() operation. Such operation is executed by servers periodically at any time

T i = t 0 + i∆.
If a server s i is not in a cured state then it broadcasts an echo message carrying the set V i and the set pending read i (it contains identifiers of clients that are currently running a read()

operation maintenance() executed every T i = t 0 + ∆ i : (01) cured i ← report cured state(); (02) if (cured i ) then (03) V i ← ∅; echo vals i ← ∅; echo read i ← ∅; (04) wait(δ); (05) insert(V i , select three pairs max sn(echo vals i )); (06) cured i ← false; (07)
for each (j ∈ (pending read i ∪ echo read i )) do (08) send reply (i, V i ) to c j ; (09) endFor [START_REF] Martin | Small byzantine quorum systems[END_REF] else [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] broadcast echo(i, V i , pending read i ); [START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF] if( ⊥, 0 ∈ V i )then [START_REF] Sasaki | Mobile byzantine agreement on arbitrary network[END_REF] f w vals i ← ∅; echo vals i ← ∅; ---------------------------------when echo (j, V j , pr) is received:

(14) endif (15) endif -
(16) echo vals i ← echo vals i ∪ V j ; (17) echo read i ← echo read i ∪ pr;
Figure 22: A M algorithm implementing the maintenance() operation (code for server s i ) in the (∆S, CAM ) model. operation). Moreover if in V i there are no ⊥, 0 values then it empties the f w vals i and echo vals i sets, meaning that it is not trying to retrieve a value lost because s i was affected by a Byzantine agent while such value has been written.

Otherwise, if a server s i is in a cured state it first cleans its local variables and then, after δ time units, tries to update 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 three or at least two tuples v, sn . If there are only two tuple v, sn , it means that there exists a concurrent write() operation that is updating the register value concurrently with the maintenance() operation. Thus, s i considers ⊥, 0 as the pair associated to the value that is concurrently written. Finally, it assigns false to cured i , meaning that it is now correct and starts replying to clients that are currently reading.

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 forwards the message, trough a write fw(i, v, csn ), to others servers. This prevents the message loss in case servers deliver such message while they are affected by mobile Byzantine agents. In addition, it also sends a reply() message to all clients that are currently reading (clients in pending read i ) to allow them to terminate their read() operation.

When s i delivers a write fw(j, v, csn ) message, it stores such message in f w vals i set. Such set is constantly monitored together with echo vals i set to find a couple v, sn occurring at least #reply CAM times. This continuous check enables servers in a cured state to store the new value and reply to a reading client as soon as possible even in case they delivered such value when affected by mobile Byzantine agents. (a) Client code (code for client ci).

when write(v, csn) is received:

(01) insert(V i , v, csn ); (02) for each j ∈ (pending read i ∪ echo read i ) do (03)
send reply (i, { v, csn }); (04) endFor (05) broadcast write fw(i, v, csn ); -------------------------------------when write fw(j, v, csn ) is received: ------------------------------------when ∃ j, v, sn ∈ (f w vals i ∪ echo vals i ) occurring at least #reply CAM times: (07) insert(V i , v, sn ); (08) ∀j : f w vals i ← f w vals i \ { j, v, ts }; (09) ∀j : echo vals i ← echo vals i \ { j, v, ts }; [START_REF] Martin | Small byzantine quorum systems[END_REF] for each (j ∈ (pending read i ∪ echo read i )) do [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] send reply (i, { v, sn }) to c j ; (12) endFor (b) Server code (code for server si). 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. 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 , which contains three tuples value, ts or two tuples value, ts and one ⊥, 0 .

(06) f w vals i ← f w vals i ∪ { j, v, csn };
The last case occurs if s i was affected by a Byzantine agent when the last write() operation occurred so that s i is still retrieving such value. As soon as s i retrieve such value through the f w vals i and echo vals i sets, such value is sent back to c j .

In any case, 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 fw(j) message is delivered, c j identifier is added to pending read i set, as when the read request is just received from the client.

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

Definition 13 (write() completion time t wE ) Let write() be an operation op W writing v on the register and let S the set of servers in B(t B (op W )) that missed the write(v) message. Then t wE is the time at which every server s k ∈ S retrieve such value v, so that, by this time v is stored by #reply CAM + f correct servers.

Lemma 8 Let op be a write(v) operation invoked by a client c k at time t B (op) = t, then (i) any s j / ∈ B(t, t + δ) has v ∈ V j at time t + δ and (ii) the write completion time t wE ≤ t + 2δ.

Proof The first part of the proof simply follows considering that: due to the communication channel synchrony, the write messages from c k are delivered by servers within the time interval [t, t + δ]; any correct server s j during the whole time interval [t, t + δ] executes the correct algorithm code. Thus, when s j delivers the write message it executes line 01 in Figure 23(b) storing v in V .

Concerning the second part, let us call S ⊆ B(t) the set of servers whose missed the write() message sent by c k because affected by a Byzantine agent at the beginning of op. Let T i the time at which servers in S became cured, so that t < T i < t + δ. Any server s i ∈ S does execute line 07 in Figure 23(b) (i.e., it stores v in V ) when there are at least #reply CAM = (k + 1)f + 1 occurrences of v in the set f w vals i ∪ echo vals i . Considering that during the write() operation at most 2f servers may be affected by Byzantine agents (cf. Lemma 6 for a δ time interval), then there are min Co(t, t + δ) = n -2f = 3(k + 1)f + 1 -2f = (k + 1)f + 1 non faulty servers. In other words, there are at least (k +1)f +1 non faulty servers executing line 05. Servers in Co(t, t+δ) may deliver the write() message from c k before of after T i . Consequently they can send the WRITE FW() message before of after T i . In the first case the WRITE FW() message can be missed as well (i.e. delivered by servers in S before T i , when still Byzantine). When those servers deliver the write() message, v is inserted in the V set (Figure 23 line 01) such that at the next maintenance() operation, at T i , v is in the echo() message (Figure 22 line 08). This means that servers in S deliver the written value v at most at T i + δ. In the second case, when the write() message from c k is delivered by servers in Co(t, t + δ) after T i , the WRITE FW() message is sent by servers in the time interval [T i , t E (op)] (Figure 23 line 05). Since a message is delivered by δ time, then by t E (op) + δ = t + 2δ any servers in S, that missed the write() message, has enough occurrences of v in the f w vals i ∪ echo vals i set so that line 07 is executed and v is stored in V . Thus at the write completion time there are #reply CAM + f servers storing v. To conclude, let us consider that, each server in V can store up to three values. So that even if there are subsequent write() operations, such that the completion time of the first overlap the second write(), the new value does not overwrite the previous one before the write() is effective.

2 Lemma 8 Lemma 9 If (i) k∆ ≥ 2δ (with k ∈ {1, 2}), (ii) n CAM ≥ (k + 3)f + 1, (iii) there are no write() operations during [T i , T i + δ]. Then ∀s ∈ Cu(T i ), s ∈ Co(T i , T i + δ).
Proof Let us assume that at T i there are 2f + 1 correct servers storing

V = { v 0 , 0 , v 1 , 1 , v 2 , 2 }
and running the code in Figure 22. In particular each server s j / ∈ Cu(T 1 ) broadcasts a echo() message with attached the content of V (line 11) while each server s i ∈ Cu(T 1 ) waits δ time units (line 04) to gather all the echo() messages. Let us note that, by hypothesis there are no write() operations during [T i , T i + δ]. This means the 2f + 1 broadcast the same set of values V . So that cured servers set their state to correct and V = { v 0 , 0 , v 1 , 1 , v 2 , 2 }. This is always true if we consider that at the beginning, at T 0 , there are f servers affected by mobile Byzantine agent and n -f > 2f + 1 correct servers. So that what we proved always holds. At the end of the maintenance() there are the same number of correct servers (there have no been cured servers yet) so that at T 1 there are n -2f ≥ 2f + 1 correct servers running the maintenance() and at the end of it there are n -f correct servers, whose became n -2f ≥ 2f + 1 at T 2 and so on.

2 Lemma 9

Lemma 10 If (i) k∆ ≥ 2δ (with k ∈ {1, 2}), (ii) n CAM ≥ (k + 3)f + 1. Then ∀s ∈ Cu(T i ), s ∈ Co(T i , T i + δ) and every server in Co(T i , T i + δ) is storing at least one common value, in particular such value is the last written value before T i .

Proof Let us assume that at T i there are 2f + 1 correct servers storing

V = { v 0 , 0 , v 1 , 1 , v 2 , 2 }
and running the code in Figure 22. In particular each server s j / ∈ Cu(T 1 ) broadcasts a echo() message with attached the content of V (line 11) while each server s i ∈ Cu(T 1 ) waits δ time units (line 04) to gather all the echo() messages. If there is a write()

operation op W 1 writing v 3 , 3 , such that T i ∈ [t B (op W 1 ),t E (op W 1 )], then the 2f + 1 servers in Co(T i ) may broadcast different sets of values V , { v 0 , 0 , v 1 , 1 , v 2 , 2 } or { v 1 , 1 , v 2 , 2 , v 3 , 3 }.
At the end of the maintenance(), servers in Cu(T i ) select values occurring at least 2f + 1 times, thus they set at least V = { v 1 , 1 , v 2 , 2 , ⊥, ⊥ }. At T i + δ it may also happen that another write() operation, op W 2 writing v 4 , 4 subsequent to op W 1 , occurs, such that

T i + δ ∈ [ t B (op W 2 ),t B (op W 2 ) ].
In that case it may happen that all servers that were in Co(t) and are now in Co(t + δ) delivers the write( v 4 , 4 ) message and no yet the servers that were in Cu(T i ). So that the first group of servers is storing v 2 , 2 , v 3 , 3 , { v 4 , 4 } and the second group is storing { v 2 , 2 , v 3 , 3 , ⊥, ⊥ }. All of those servers are storing v 2 , 2 in common, which is the last written value respecting to T i , concluding the proof.

2 Lemma 10

From Lemmas 9 and 10 the next Corollary follows.

Corollary 4

The maintenance() operation guarantees that ∀T i , i ∈ N, ∀s ∈ Cu(T i ), then s ∈ Co(T i , T i + δ).

Lemma 11 Let op W be a write() operation and let v be the written value.

k = 2δ ∆ , δ ≤ ∆ < 3δ n CU M ≥ (3k + 2)f + 1 #reply CU M ≥ (2k + 1)f + 1 #echo CU M ≥ (k + 1)f + 1 k = 2 8f + 1 5f + 1 3f + 1 k = 1 5f + 1 3f + 1 2f + 1
bound on the communication latencies in the synchronous system. If (i) k∆ ≥ 2δ (with k ∈ 1, 2) and (ii) n ≥ (k + 3)f + 1, then P reg implements a SWMR Regular Register in the (∆S, CAM ) round-free Mobile Byzantine Failure model.

Proof The proof simply follows from Theorem 7 and Theorem 8. 2 T heorem 9

6 Optimal Regular Register Implementation in the (∆S, CU M ) model

In this section, we present an optimal protocol P reg that implements a SWMR Regular Register in a round-free synchronous system for (∆S, CU M ) instance of the proposed MBF model. Our solution is based on the following three key points: (1) we implement a maintenance() operation that is executed periodically at each T i = t 0 + i∆ time. In this way, the effect of a Byzantine agent on a server disappears in a bounded period of time; (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 computed by taking into account the time to terminate the maintenance() operation, δ and ∆; (3) we define a forwarding mechanism to avoid that read() and write() messages are "lost" by some server s i due to a concurrent movement of the Byzantine agent during such operations. Note that even though communication channels are reliable, we may have the following situation: a message is sent by a client at time t and the Byzantine agents move at some t < t + δ. As a consequence, some faulty servers may receive the message in the interval [t, t ] and then agents move leaving cured servers without any trace of the message. Moreover, contrarily to the (∆S, CAM ) case, the values that populate auxiliary variables (i.e., not the register stored value) have a fixed life time. This is necessary since servers are never aware to be in a cured state and thus Byzantine processes may force them to take wrong decisions.

Interestingly, we found that the number of replicas needed to tolerate f Byzantine agents does not depend only on f but also on the ∆ and δ relationship (see Table 3).

P reg Detailed Description

The protocol P reg for the (∆S, CU M ) model is described in Figures 252627.

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. 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.

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 function insert(V saf e i , v k , sn k ) 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 at the end of the maintenance() operation when the timer expires or has a value non compliant with the protocol.

• echo vals i and echo read i : two sets used to collect information propagated through echo messages at the beginning of the maintenance() operation. The first one stores tuple v, sn j propagated by servers just after the mobile Byzantine agents moved. Set echo read i stores identifiers of concurrently reading clients in order to notify cured servers and expedite termination of read().

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

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, 3 tuples v, sn , such that there exist at least #echo CU M occurrences in echo vals i of such tuple. If more than 3 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 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 periodically at any time T i = t 0 + i∆. Each server first checks if there are expired values in W i then all the content of V saf e i is stored in V i and all V saf e i and echo vals i sets are reset. Each server broadcast an echo message with the content of V i , W i (purged of the timer information) and the set pending read i . When there is a value in echo vas i set that occurs at least #echo CU M times, it updates V saf e i set by invoking select three pairs max sn(echo vals i ) function. To conclude, after δ time since the beginning of the operation, the W i set is pruned from expired values and V i is reset. Informally speaking, at this point V i is no more used, since V saf e i during the maintenance() operation is filled with values, then the content in V i is not more necessary.

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.

Proof By hypotheses at T i there are #echo CU M correct servers s j storing the same v and running the code in Figure 25. In particular each server broadcasts a echo() message with attached the content of V j which contains v (line 11 From the reasoning used in this Lemma, the following Corollary follow.

Corollary 5 Let s i be a non faulty process and v a value in W i . Such value is in W i during at most k sequential maintenance() operations.

Finally, considering that servers reply during a read() operation with values in W i , V i and V saf e i . V saf e i is safe by definition, V i is reset after the first maintenance() operation then it follows that servers can be in a cured state for 2δ time, the time that never written values can be present in W i .

Corollary 6 Protocol P implements a maintenance() operation that implies γ ≤ 2δ.

Lemma 18 Let T c be the time at which s c becomes cured. Each cured server s c can reply back with incorrect message to a read() message during a period of 2δ time. such operation and let t wC be its completion time. Then v is in the register (there are #reply CU M correct servers storing it) up to time at least t B W k+3 .

Proof The proof simply follows considering that:

• for Lemma 20 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 ordered set V saf e , whose dimension is 3;

• write() operation occur sequentially.

It follows that after 3 write() operations, op W k+1 , op W k+2 , op W k+3 , v is no more stored in the regular register.

2 Lemma 21

Before to prove the validity property, let us consider how many Byzantine and cured servers can be present during a read() operation that last 3δ, cf. Figure 28. If k = 2 there can be up to 4f (cf. Lemma 13) Byzantine servers and 2f cured servers. If k = 1 there can be up to 3f Byzantine servers (cf. Lemma 13) and f cured servers. In Figure 28 we depicted the extreme case in which there is a read() operation just after the last write() operation. T wC lines represent the time at which for sure correct servers replies with the last written value. Notice that when δ = ∆ s 4 has just the time to correctly reply to the client before being affected. In both cases there are #reply CU M correct servers that replies with the last written value and the number of those replies is greater than number of replies coming from cured and Byzantine servers.

Theorem 11 (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 )+δ]. The operation lasts 3δ, thus reply messages sent by correct servers within t B (op R )+2δ are delivered by the reading client. During [t, t + 2δ] time interval there are at least #reply CU M correct servers that have the time to deliver the read request and reply (cf. Figure 28). 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 20 after the write completion time t wC there are at least #reply CU M correct servers storing v (i.e., v ∈ conCut(V i , V saf e i , W i ). Since t B (op R ) + 2δ ≥ t C w, then there are #reply CU M correct servers replying with v. 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 )+2δ]. In such time there can be at most three sequential write() operations op W 1 , op W 2 , op W 3 . Let op W 0 be the last write operation before op R . In the extreme case in which those operations happen one after the other we have the following situation. t E (op W 0 < t B (op R )) and the write completion time of op W 0 , t wC 0 < t B (op W 0 ) + 3δ < t B (op R ) + 2δ < t B (op W 3 ). Basically, the value written by op W 0 is overwritten in V i by the value written op W 3 , but not before t B (op R ) + 2δ, thus all correct servers have the time to reply with the last written value. Notice that the concurrently written values may be returned if the write() and reply() messages are fast enough to be delivered before the end of the read() operation. To conclude, for Lemma 18 Byzantine and cured servers can no force correct servers to store and thus to reply with a never written value. Only cured and Theorem 13 Protocol P Rreg is tight with respect to the number of replicas.

Proof The proof simply follows considering that Theorems 10-11 proved that P Rreg works with bounds provided in Table 3. Those match the previously known lower bounds proved in Theorem 4 and Theorem 6 for the (∆S, CU M ) model.

T heorem 13 7 Conclusion

This paper addressed the problem of emulating multi-reader regular registers under the MBF adversarial model for round-free computations. We first formalized MBF adversarial model in order to capture dynamic failures in generic (round-free) distributed computations and then we studied solvability issues raised by this powerful adversary. In particular, we proved that in the presence of mobile Byzantine agents a new operation, namely maintenance() must be defined. Then, we proved that in asynchronous distributed systems it is not possible to emulate a safe or regular register even in the presence of one Byzantine agent governed by the weakest (∆S, CAM ) adversary. We then considered the case of round-free synchronous systems and we proved that an emulation of an optimal regular register is possible against (∆S, CAM ) adversary provided that, n CAM ≥ 4f + 1 if 2δ ≤ ∆ < 3δ and n CAM ≥ 5f + 1 if δ ≤ ∆ < 2δ. While an emulation of an optimal regular register is possible against (∆S, CU M ) adversary provided that, n CU M ≥ 5f + 1 if 2δ ≤ ∆ < 3δ and n CU M ≥ 8f + 1 if δ ≤ ∆ < 2δ. We currently are investigating the solvability of other distributed building blocks under the proposed models.

Figure 1 :

 1 Figure 1: MBF model instances for round-free computations and their relations.

Figure 2 :

 2 Figure 2: Example of a (∆S, * ) run with f = 2.

Figure 3 :

 3 Figure 3: Example of a (IT B, * ) run with f = 2.

Lemma 1

 1 Let P reg = {A R , A W , A M } be a protocol implementing a safe register in the (∆S, CAM ) MBF model. Let f > 0 be the number of Byzantine Agents controlled by the external adversary. Any algorithm A W and A R must involve at least one sendreply (resp. requestreply) communication pattern (i.e., two communication steps).

Figure 5 :Figure 6 :Figure 7 :Theorem 4

 5674 Figure 5: A 2δ read() operation is performed in a CAM model for δ ≤ ∆ < 2δ.

Figure 10 :

 10 Figure 10: A 4δ read() operation is performed in the CUM model for δ ≤ ∆ < 2δ and γ ≤ 2δ.

Figure 11 :

 11 Figure 11: A 4δ read() operation is performed in the CUM model for δ ≤ ∆ < 2δ and γ ≤ 2δ.

Figure 12 :

 12 Figure 12: A 2δ read() operation is performed in a CAM model in which 2δ ≤ ∆ < 3δ.

Figure 13 :

 13 Figure 13: A 3δ read() operation is performed in a CAM model in which 2δ ≤ ∆ < 3δ.

Figure 14 :Figure 15 :

 1415 Figure 14: A 4δ read() operation is performed in a CAM model in which 2δ ≤ ∆ < 3δ.

Figure 16 :Figure 17 :Figure 18 :Figure 19 :

 16171819 Figure 16: A 2δ read() operation performed in the CUM model for 2δ ≤ ∆ < 3δ and γ ≤ 2δ.

Figure 20 :Figure 21 :

 2021 Figure 20: A 6δ read() operation is performed in the CUM model for 2δ ≤ ∆ < 3δ and γ ≤ 2δ.

  operation write(v): (01) csn ← csn + 1; (02) broadcast write(v, csn); (03) wait (δ); (04) return write confirmation;

Figure 23 :

 23 Figure 23: A W algorithm implementing the write(v) operation in the (∆S, CAM ) model.

  respectively (seeFigure 4.5). Again, with no concurrent write() operations, c i returns two different values although receiving the same set of replies. At this point each server replied with two different values. A simple induction argument implies that waiting more does not bring any new way to break symmetry.

		req rep
	read()
	s 0	s 0
	s 1	s 1
	s 2	s 2
	s 3	s 3
	s 4	s 4
	s 5	s 5
	s 6	s 6
	s 7	s 7
	Figure 8: A 2δ read() operation is performed	Figure 9: A 3δ read() operation is performed
	in the CUM model for δ ≤ ∆ < 2δ and γ ≤	in the CUM model for δ ≤ ∆ < 2δ and γ ≤
	2δ.	2δ.
	req rep
	s 0
	s 1	2 T heorem 4
	s 2
	s 3
	s 4
	s 5
	s 6
	s 7

Table 1 :

 1 Parameters for P Rreg Protocol.

  Let t E w be its completion time and let T i the time of the first Byzantine agent movement after t E w. Then if there are no other write() operations after op W , the value written by op W is stored by #reply CAM servers forever.Proof Let us consider the case k = 2. Let us first consider how many Byzantine servers there may be in the time interval [t B (op W ), T i ]. The time from t B (op W ) and t E w is at most 2δ (cf. Lemma 8) and the time from t E w to T i is at most δ since we are considering k = 2. Thus the time interval [t B (op W ), T i ] is at most 3δ. In such period, being the agent movement aligned to T i and being k = 2, there may be at most 3f Byzantine servers. Moreover, n ≥ 5f + 1, then at T i there are at least f + 1 servers never affected in the considered time interval and thus, for Lemma 8, such servers are storing v by time t B (op W ) + δ. For the same Lemma, by time t E w, the f servers that were in B(t B (op W )) are storing v. Thus, at time T i there are at least 2f + 1 correct servers storing v, so for Lemma 9 at the end of the maintenance(), servers that were cured at T i are now storing the same values as servers in Co(T i ). Thus at T i there are n -f ≥ 4f + 1 correct servers storing v. At T i+1 the new maintenance() operation run with n -2f servers storing v, which at the end of the maintenance() operation is n -f again and so on. Thus if there are no more write() operation v is stored forever. Case k = 1 is similar concluding the proof.2 Lemma 11

Table 3 :

 3 Parameters for P Rreg Protocol in the (∆S, CU M ).

  ). Messages sent by #echo CU M correct servers are delivered by s c and stored in echo vals c . The system is synchronous, thus by time T i + δ function select pairs(echo vals c ) returns v. 2 Lemma 16 Lemma 17 Let s i be a correct server running the maintenance() operation at time T i , then if v is returned by the function select pairs(echo vals i ) there exist a write() operation that wrote such value. Proof Let us suppose that select pairs(echo vals i ) returns v and there no exist a write()(v ). This means that s i collects in echo vals i at least #echo CU M occurrences of v coming from cured and Byzantine servers. Let us consider cured servers s c at time T c . At the beginning of the maintenance() operation s c broadcasts values contained in V i and W i (Figure 25 line 11). V i is reset at each operation with the content of V saf e i which is reset at each operation (line 06). It follows that s c broadcasts non valid values contained in V i only during the maintenance() operation run a T c . Contrarily, values in W i , depending on k, are broadcast only at T c or also at T c+1 . Let us consider two cases: k = 1 and k = 2. case k = 1: In this case since ∆ ≥ 2δ and the maximum value of the timer associated to a value is 2δ, then each cured server s c broadcasts a non valid value contained in W Byzantine servers, f cured servers and f servers that were cured during the previous operation. Those servers are not enough to send #echo CU M = 3f + 1 occurrences of v , for Lemma 16 this is the necessary condition to return v invoking select pairs(echo vals i ), leading to a contradiction and concluding the proof. 2 Lemma 17

i only during the first maintenance() operation. Thus, during each maintenance() operation there are f Byzantine servers and f cured servers, those are not enough to send #echo CU M = 2f + 1 occurrences of v . For Lemma 16 this is the necessary condition to return v invoking select pairs(echo vals i ), leading to a contradiction. case k = 2: δ ≤ ∆ < 2δ and the maximum value of the timer associated to a value is 2δ, then each cured server s c broadcasts a non valid value contained in W i during the two subsequent maintenance() operations. Summing up, during each maintenance() operation at time T i there are f

  Figure 28: In the first scenario ∆ ≥ 2δ and in second one is ∆ ≥ δ. Blue arrows are the correct replies sent back by correct servers.Byzantine servers can reply with non valid values. As we stated, if k = 1 there are up to 4f non correct servers. If k = 2 there are 6f non correct servers. In both cases the threshold #reply CU M is higher than the occurrences of non valid values that a reader can deliver. Mobile agents can 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 chosen.2 T heorem 11Theorem 12 Let n be the number of servers emulating the register and let f be the number of Byzantine agents in the (∆S, CU M ) round-free Mobile Byzantine Failure model. Let δ be the upper bound on the communication latencies in the synchronous system. If (i) k∆ ≥ 2δ (with k ∈ 1, 2) and (ii) n ≥ 2(k + 1)f + 1, then P reg implements a SWMR Regular Register in the (∆S, CU M ) round-free Mobile Byzantine Failure model.Proof The proof simply follows from Theorem 10 and Theorem 11.2 T heorem 12

			write() T wC
			t	t + 3δ
			s 0
			s 1
	t write() T wC	t + 3δ	s 2
	s 0		s 3
	s 1		s 4
	s 2		s 5
	s 3		s 6	. . .
	s 4		s 7
	s 5		s 8

It is trivial to prove that in our model when clients are Byzantine it is impossible to implement deterministically even a safe register. The Byzantine client will always introduce a corrupted value. A server cannot distinguish between a correct client and a Byzantine one.

Let us note that such an operation can also be embedded in the other algorithm. However, for the sake of clarity, we will consider here only protocols where valid state recovery is managed by a specific operation.

The exact number of processes is given by the implementation of AW algorithm. In any case, such number does not affect the proof and it must be at least one.

We are interested in correct servers that surely can reply, so that a read() message sent by a client is for sure delivered by servers by t + δ and a reply sent by t + T -δ is for sure delivered by client.

 ------------------------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 (a) Client code (code for client ci).

when read (j) is received: (01) pending read i ← pending read i ∪ {j}; (02) if (¬cured i ) (03) then send reply (i, V i ); (04) endif (05) broadcast read fw(j); ------------------------when read fw (j) is received: (06) pending read i ← pending read i ∪ {j}; ------------------------when read ack (j) is received: (07) pending read i ← pending read i \ {j}; (08) echo read i ← echo read i \ {j};

(b) Server code (code for server si).

Figure 24: A R algorithm implementing the read() operation in the (∆S, CAM ) model.

Correctness proofs

To prove the correctness of P reg , we first demonstrate that the termination property is satisfied i.e, that read() and write() operations terminates. Due to the algorithm implementation, such property is independent from the specific instance of the MBF model considered.

Lemma 4 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 23(a)).

2 Lemma 4

Lemma 5 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 03-06, Figure 24(a)).

2 Lemma 5

Theorem 7 (Termination) If a correct client c i invokes an operation, c i returns from that operation in finite time.

Proof The proof simply follows from Lemma 4 and Lemma 5. Proof For simplicity let us consider a single agent ma 1 , then we extend the reasoning to all the f agents. In the [t, t + T ] time interval, with T ≥ δ, ma 1 can affect a different server each ∆ time. It follows that the number of times it may "jump" from a server to another is T ∆ . Thus the affected servers are at most T ∆ plus the server on which ma 1 is at t. Finally, extending the reasoning to f agents, M ax B(t, t + T ) = ( T ∆ + 1)f , concluding the proof.

Table 2: Table summing up the value that we get substituting δ and ∆ in the formulas.

Proof

Let us consider the two cases separately, k = 2 so that δ ≤ ∆ < 2δ and k = 1 so that 2δ ≤ ∆

The number of correct servers at time t + δ is given by the number of serves that are nonfaulty in the whole interval (n CAM -M ax B(t, t + 2δ)) plus the number of server that were not correct at time t but that had "enough" time to terminate the maintenance operation before time t + δ (i.e., M ax B(t, t + 2δ) -M ax B(t + δ, t + 2δ)).

Thus Considering the worst case scenario where each message sent to and by non correct servers is instantaneously delivered, while each message sent to and by correct servers needs δ time, from Lemma 7 the next corollary follows Corollary 3 Let op be a read() operation issued at time t and terminating at time t + 2δ. The number of replies carrying valid values at some time τ ∈ [t, t+2δ] is always greater than the number of replies carrying non valid values.

. . 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 .

Proof The proof simply follows considering that:

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

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

• write() operations occur sequentially.

From that is it clear 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. Basically we can say that thanks to the maintenance() operation and the forwarding mechanism, when a read() operation op R begins at time t B (op R ), at time t B (op R ) + δ there are #reply CAM correct servers that reply with a value v ∈ V V S(t B (op R )).

Theorem 9 Let n be the number of servers emulating the register and let f be the number of Byzantine agents in the (∆S, CAM ) round-free Mobile Byzantine Failure model. Let δ be the upper ------------------------------------operation maintenance() executed every ----------------------------------when select three pairs max sn(echo vals i ) = ⊥ (14) insert(V saf e i , select three pairs max sn(echo vals i )); [START_REF] Sousa | Highly available intrusion-tolerant services with proactive-reactive recovery[END_REF] for each (j ∈ (pending read i ∪ echo read i )) do (16) send reply (i, V saf e ) to c j ; (17) endFor ------------------------------------ When a server s i delivers a write, it stores v in W i . Then server sends a reply carrying such value to each reading client and broadcast such value as an echo() message to other servers. The read() operation. When a client wants to read, it broadcasts a read() request to all servers and waits 3δ time to collect replies. When it is unblocked from the wait statement, it selects a value v occurring #reply CU M number of times from the 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. 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. Thus, considering the function conCut(), a cured server may send a non valid value during 2δ time. 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 fw(j) message is delivered, c j identifier is added to pending read i set, as when the read request is just received from the client.

When a read ack(j) message is delivered, c j identifier is removed from both pending read i and echo read i sets as it does not need anymore to receive updates for the current read() operation. ------------------------when reply (j, V set) is received:

reply i ← reply i ∪ { j, v, sn }; (09) endFor ========= Server code ========== when read (j) is received: (10) pending read i ← pending read i ∪ {j}; [START_REF] Ostrovsky | How to withstand mobile virus attacks (extended abstract)[END_REF] send reply (i, conCut(V i , V saf e i , W i )); [START_REF] Reischuk | A new solution for the byzantine generals problem[END_REF] broadcast read fw(j); ------------------------when read fw (j) is received: (13) pending read i ← pending read i ∪ {j}; ------------------------when read ack (j) is received: (14) pending read i ← pending read i \ {j}; (15) echo read i ← echo read i \ {j};

Correctness proofs

Definition 14 (Faulty servers in the interval I) Let us define as B[t, t + T ] the set of servers that are affected by a Byzantine agent for at least one time unit in the time interval

Proof For simplicity let us consider a single agent ma 1 , then we extend the reasoning to all the f agents. In the [t, t + T ] time interval, with T ≥ δ, ma 1 can affect a different server each ∆ time. It follows that the number of times it may "jump" from a server to another is T ∆ . Thus the affected servers are at most T ∆ plus the server on which ma 1 is at t. Finally, extending the reasoning to f agents, M ax B(t, t + T ) = ( T ∆ + 1)f , concluding the proof.

Concerning the protocol correctness, the termination property is guaranteed by the way the code is designed, after a fixed period of time all operations terminate. The 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 CU M correct servers at the beginning of the maintenance() operation, there are n -f servers that store v after δ time since the beginning 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 + 3δ after which #reply CU M correct servers store v;

3. at the next maintenance() operation after t there are #reply CU M -f = #echo CU M correct servers that store v, for step (1) this value is maintained in the register;

4. the validity property follows considering that the read() operation is long enough to include the t of the last written value in such a way that servers have enough time to reply. Moreover we show that V i is big enough to do not be full filled with new values before t .

Lemma 14 If a 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 servers behavior (see lines 03-04, Figure 26). 2 Lemma 14

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

Proof The claim simply follows by considering that a read() returns a value to the client after 3δ time, independently of the behavior of the servers (see lines 03-06, Figure 27). 2 Lemma 15

Theorem 10 (ss-Termination) Any operation invoked on the register eventually terminates.

Proof The proof simply follows from Lemma 14 and Lemma 15.

T heorem 10

Lemma 16 (Step 1.) Let v be a value stored at #echo CU M correct servers s j ∈ Co(T i ), v ∈ V j ∀s j ∈ Co(T i ). Then ∀s c ∈ Cu(T i ) at T i + δ (i.e., at the end of the maintenance()) v is returned by the function select pairs(echo vals i ).

Proof The proof directly follows considering that the content of a reply() message comes from the V c , V saf ec and W i sets. The first one is filled with the content of V saf ec at the beginning of each manteneance() operation and after δ time is reset (cf. Figure 25 For simplicity, from now on, given a write() operation op W we call t B (op W ) + 3δ = t wC the completion time of op W , the time at which there are at least #reply CU M servers s i storing the value written by op W in V saf e i .

Lemma 20 (Step 3.) Let op W be a write() operation and let v be the written value. If there are no other write() operations, the value written by op W is stored by all correct servers forever (i.e., v is returned invoking the conCut() function).

Proof From Lemma 19 at time t wC there are at least n -2f ≥ #reply CU M correct servers s j that have v in V saf e i . At the next Byzantine agents movement there are n -2f -f ≥ #echo CU M correct server storing v in V saf e i , which is moved to V i and broadcast during the maintenance() operation. For Lemma 16, after δ time, all non Byzantine servers are storing v in V saf e i . At the next Byzantine agents movement there are f less correct servers that store v in V saf e i , but those servers are still more than #echo CU M . It follows that cyclically before each agent movements there are f servers more that store v thanks to the maintenance() and f servers that lose v because faulty, but this set of non faulty servers is enough to successfully run the maintenance() operation (cf. Lemma 16)). By hypotheses there are no more write() operation, then v is never overwritten and all correct servers store v forever.

2 Lemma 20

Lemma 21 (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