Alexandre Maurer
email: alexandre.maurer@epfl.ch

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

Xavier Defago
email: defago@jaist.ac.jp

Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults

We consider the following problem: two nodes want to reliably communicate in a dynamic multihop network where some nodes have been compromised, and may have a totally arbitrary and unpredictable behavior. These nodes are called Byzantine. We consider the two cases where cryptography is available and not available.

We prove the necessary and sufficient condition (that is, the weakest possible condition) to ensure reliable communication in this context. Our proof is constructive, as we provide Byzantine-resilient algorithms for reliable communication that are optimal with respect to our impossibility results.

In a second part, we investigate the impact of our conditions in three case studies: participants interacting in a conference, robots moving on a grid and agents in the subway. Our simulations indicate a clear benefit of using our algorithms for reliable communication in those contexts.

Introduction

As modern networks grow larger, their components become more likely to fail, sometimes in unforeseen ways. As opportunistic networks become more widespread, the lack of global control over individual participants makes those networks particularly vulnerable to attacks. Many failure and attack models have been proposed, but one of the most general is the Byzantine model proposed by Lamport et al. [START_REF] Lamport | The Byzantine generals problem[END_REF]. The model assumes that faulty nodes can behave arbitrarily. In this paper, we study the problem of reliable communication in a multihop network despite the presence of Byzantine faults. The problem proves difficult since even a single Byzantine node, if not neutralized, can lie to the entire network.

Related works

A common way to solve this problem is to use cryptography [START_REF] Castro | Practical Byzantine fault tolerance[END_REF][START_REF] Vadim Drabkin | Efficient Byzantine broadcast in wireless ad-hoc networks[END_REF]: the nodes use digital signatures to authenticate the sender across multiple hops. However, cryptography per se is not unconditionally reliable, as shown by the recent Heartbleed bug [START_REF]The Heartbleed Bug[END_REF] discovered in the widely deployed OpenSSL software. The defense in depth paradigm [START_REF] Lippmann | Validating and restoring defense in depth using attack graphs[END_REF] advocates the use of multiple layers of security controls, including non-cryptographic ones. For instance, if the cryptography-based security layer is compromised by a bug, a virus, or intentional tampering, a cryptography-free communication layer can be used to safely broadcast a patch or to update cryptographic keys. Thus, it is interesting to develop both cryptographic and non-cryptographic strategies. Following the setting of the seminal paper of Lamport et al. [START_REF] Lamport | The Byzantine generals problem[END_REF], many subsequent papers focusing of Byzantine tolerance [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations, and Advanced Topics[END_REF][START_REF] Malkhi | Diffusion without false rumors: on propagating updates in a Byzantine environment[END_REF][START_REF] Malkhi | Efficient update diffusion in Byzantine environments[END_REF][START_REF] Minsky | Tolerating malicious gossip[END_REF] study agreement and reliable communication primitives using cryptography-free protocols in networks that are both static and fully connected. A recent exception to fully connected topologies in Byzantine agreement protocols is the recent work of Tseng, Vaidya and Liang [START_REF] Tseng | Iterative approximate Byzantine consensus under a generalized fault model[END_REF][START_REF] Vaidya | Iterative approximate Byzantine consensus in arbitrary directed graphs[END_REF], which considers specific classes of static directed graphs (i.e., graphs with a particularly high clustering coefficient) and considers approximate and iterative versions of the agreement problem.

In general multihop networks, two notable classes of algorithms use some locality property to tolerate Byzantine faults: space-local and time-local algorithms. Space-local algorithms [START_REF] Masuzawa | Stabilizing link-coloration of arbitrary networks with unbounded Byzantine faults[END_REF][START_REF] Nesterenko | Tolerance to unbounded Byzantine faults[END_REF][START_REF] Sakurai | A self-stabilizing link-coloring protocol resilient to Byzantine faults in tree networks[END_REF] try to contain the fault (or its effect) as close to its source as possible. This is useful for problems where information from remote nodes is unimportant (such as vertex coloring, link coloring, or dining philosophers). Time-local algorithms [START_REF] Dubois | The impact of topology on Byzantine containment in stabilization[END_REF][START_REF] Dubois | On Byzantine containment properties of the min+1 protocol[END_REF][START_REF] Dubois | Bounding the impact of unbounded attacks in stabilization[END_REF][START_REF] Dubois | Maximum metric spanning tree made Byzantine tolerant[END_REF][START_REF] Masuzawa | Bounding the impact of unbounded attacks in stabilization[END_REF] try to limit over time the effect of Byzantine faults. Time-local algorithms presented so far can tolerate the presence of at most a single Byzantine node, and are unable to mask the effect of Byzantine actions. Thus, neither approach is suitable to reliable communication.

In dense multihop networks, a first line of work assumes that there is a bound on the fraction of Byzantine nodes among the neighbors of each node. Protocols have been proposed for nodes organized on a grid [START_REF] Bhandari | On reliable broadcast in a radio network[END_REF][START_REF] Koo | Broadcast in radio networks tolerating Byzantine adversarial behavior[END_REF] (but with much more than 4 neighbors), and later generalized to other topologies [START_REF] Pelc | Broadcasting with locally bounded Byzantine faults[END_REF], with the assumption that each node knows the global topology. Since this approach requires all nodes to have a large degree, it may not be suitable for every multihop networks. The case of sparse networks was studied under the assumption that Byzantine failures occur uniformly at random [START_REF] Maurer | Limiting Byzantine influence in multihop asynchronous networks[END_REF][START_REF] Maurer | A scalable Byzantine grid[END_REF][START_REF] Maurer | On Byzantine broadcast in loosely connected networks[END_REF], an assumption that holds, e.g., in structured overlay networks where the identifier (a.k.a. position) of a new node joining the network is assigned randomly, but not necessarily in various actual communication networks.

Most related to our work is the line of research that assume the existence of 2k + 1 node-disjoint paths from source to destination, in order to provide reliable communication in the presence of up to k Byzantine failure [START_REF] Dolev | The Byzantine generals strike again[END_REF][START_REF] Nesterenko | Discovering network topology in the presence of Byzantine faults[END_REF][START_REF] Dolev | Perfectly secure message transmission[END_REF]. The initial solution [START_REF] Dolev | The Byzantine generals strike again[END_REF] assumes that each node is aware of the global network topology, but this hypothesis was dropped in subsequent work [START_REF] Nesterenko | Discovering network topology in the presence of Byzantine faults[END_REF]18]. None of the aforementioned papers considers genuinely dynamic networks, i.e., where the topology evolves while the protocol executes.

Our contribution

In this paper, our objective is to determine the condition for reliable communication in the presence of up to k Byzantine failures in a dynamic network, where the topology can vary with time. The proof technique used in [START_REF] Dolev | The Byzantine generals strike again[END_REF][START_REF] Nesterenko | Discovering network topology in the presence of Byzantine faults[END_REF][START_REF] Dolev | Perfectly secure message transmission[END_REF] implicitly relies on Menger's theorem [START_REF] Böhme | Menger's theorem[END_REF], which can be expressed as follows: there exists x disjoint paths between two nodes p and q if and only if x nodes must removed to disconnect p and q.

However, Menger's theorem does not generalize to dynamic networks [START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF]. To illustrate this, let us consider the simple dynamic network of Figure 1. This network is in two steps (t = 1 and t = 2). There exists three dynamic paths connecting p to q: (p, a, c, q), (p, c, b, q) and (p, a, b, q). To cut these three paths, at least two nodes must be removed: either {a, b}, {b, c} or {a, c}. Yet, it is impossible to find two disjoint paths among the three dynamic paths. Therefore, Menger's theorem cannot be used to prove the condition in dynamic networks.

In this paper, we prove the necessary and sufficient condition for reliable communication in dynamic networks, in the presence of up to k Byzantine failures. We consider the two cases where cryptography is available and not available. Our characterization is based on a dynamic version of a minimal cut between p and q, denoted by DynMinCut(p, q), that takes into account both the presence of particular paths and their duration with respect to the delay that is necessary to actually transmit a message over a path. Then condition is that DynMinCut(p, q) is lower or equal to 2k (without cryptography) or k (with cryptography). The proof is constructive, as we provide algorithms to prove the sufficiency of the condition.

In a second part, we apply these conditions to three case studies: participants interacting in a conference, robots moving on a grid and agents moving in the subway. We thus show the benefit of this multihop approach for reliable communication, instead of waiting that the source meets the sink directly (if this event is to occur).

Organization of the paper

The paper is organized as follows. In Section 2, we present the model and give basic definitions. In Section 3 (resp. 4), we give the algorithm and prove the condition for the non-cryptographic (resp. cryptographic) case. We present the case studies in Section 5.

Preliminaries Network model

We consider a continuous temporal domain R + where dates are positive real numbers. We model the system as a time varying graph, as defined by Casteigts, Flocchini, Quattrociocchi and Santoro [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], where vertices represent the processes and edges represent the communication links (or channels). A time varying graph is a dynamic graph represented by a tuple G = (V, E, ρ, ζ) where:

• V is the set of nodes.

• E ⊆ V × V is the set of edges.

• ρ : E × R + → {0, 1} is the presence function: ρ(e, t) = 1 indicates that edge e is present at date t.

• ζ : E × R + → R + is

Hypotheses

We make the same hypotheses as previous work on the subject [START_REF] Bhandari | On reliable broadcast in a radio network[END_REF][START_REF] Dolev | The Byzantine generals strike again[END_REF][START_REF] Koo | Broadcast in radio networks tolerating Byzantine adversarial behavior[END_REF][START_REF] Maurer | Limiting Byzantine influence in multihop asynchronous networks[END_REF][START_REF] Maurer | On Byzantine broadcast in loosely connected networks[END_REF][START_REF] Maurer | A scalable Byzantine grid[END_REF][START_REF] Nesterenko | Discovering network topology in the presence of Byzantine faults[END_REF][START_REF] Pelc | Broadcasting with locally bounded Byzantine faults[END_REF]. First, each node has a unique identifier. Then, we assume authenticated channels (or oral model ), that is, when a node q receives a message through channel (p, q), it knows the identity of p. Now, an omniscient adversary can select up to k nodes as Byzantine. These nodes can have a totally arbitrary and unpredictable behavior defined by the adversary (including tampering or dropping messages, or simply crashing). Finally, other nodes are correct and behave as specified by the algorithm. Of course, correct nodes are unable to know a priori which nodes are Byzantine. We also assume that a correct node u is aware of its local topology at any given date t (that is, u knows the set of nodes v such that ρ((u, v), t) = 1).

Dynamicity-related definitions

Informally, a dynamic path is a sequence of nodes a message can traverse, with respect to network dynamicity and latency.

Definition 1 (Dynamic path). A sequence of distinct nodes (u 1 , . . . , u n ) is a dynamic path from u 1 to u n if and only if there exists a sequence of dates (t 1 , . . . , t n ) such that, ∀i ∈ {1, . . . , n -1} we have:

• e i = (u i , u i+1 ) ∈ E, i.e.
there exists an edge connecting u i to u i+1 .

• ∀t ∈ [t i , t i + ζ(e i , t i )],
ρ(e i , t) = 1, i.e. u i can send a message to u i+1 at date t i .

• ζ(e i , t i ) ≤ t i+1 -t i , i.e. the aforementioned message is received by date t i+1 .

We now define the dynamic minimal cut between two nodes p and q as the minimal number of nodes (besides p and q) one has to remove from the network to prevent the existence of a dynamic path between p and q. Formally:

• Let Dyn (p, q) be the set of node sets {u 1 , . . . , u n } such that (p, u 1 , . . . , u n , q) is a dynamic path.

• For a set of node sets Ω = {S 1 , . . . , S n }, let Cut (Ω) be the set of node sets C such that, ∀i ∈ {1, . . . , n}, C ∩ S i = ∅ (C contains at least one node from each set S i ).

• Let MinCut (Ω) = min CCut(Ω) |C| (the size of the smallest element of Cut (Ω)). If Cut(Ω) is empty, we assume that MinCut (Ω) = +∞.

• Let DynMinCut (p, q) = MinCut (Dyn (p, q)).

Problem specification

We say that a node multicasts a message m when it sends m to all nodes in its current local topology. Now, a node u accepts a message m from another node v when it considers that v is the author of this message. We now define our problem specification, that is, reliable communication.

Definition 2 (Reliable communication). Let p and q be two correct nodes. An algorithm ensures reliable communication from p to q when the following two conditions are satisfied:

• When q accepts a message from p, p is necessarily the author of this message.

• When p sends a message, q eventually receives and accepts this message from p.

Non-cryptographic reliable communication

In this section, we consider that cryptography is not available. We first provide a Byzantine-resilient multihop broadcast protocol. This algorithm is used as a constructive proof for the sufficient condition for reliable communication. We then prove the necessary and sufficient condition for reliable communication.

Informal description of the algorithm

Consider that each correct node p wants to broadcast a message m 0 to the rest of the network. Let us first discuss why the naive flood-based solution fails. A naive first idea would be to send a tuple (p, m 0 ) through all possible dynamic paths: thus, each node receiving m 0 knows that p broadcast m 0 . Yet, Byzantine nodes may forward false messages, e.g., a Byzantine node could forward the tuple (p, m 1 ), with m 1 = m 0 , to make the rest of the network believe that p broadcast m 1 .

To prevent correct nodes from accepting false message, we attach to each message the set of nodes that have been visited by this message since it was sent (that is, we use (p, m, S), where S is a set of nodes already visited by m since p sent it). As the Byzantine nodes can send any message, in particular, they can forward false tuples (p, m, S). Therefore, a correct node only accepts a message when it has been received through a collection of dynamic paths that cannot be cut by k nodes (where k is a parameter of the algorithm, and supposed to be an upper bound on the total number of Byzantine nodes in the network).

Variables

Each correct node u maintains the following variables:

• u.m 0 , the message that u wants to broadcast.

• u.Ω, a dynamic set registering all tuples (s, m, S) received by u.

• u.Acc, a dynamic set of confirmed tuples (s, m). We assume that whenever (s, m) ∈ u.Acc, u accepts m from s.

Initially, u.Ω = {(u, u.m 0 , ø)} and u.Acc = {(u, u.m 0 )}.

Algorithm

Each correct node u obeys the three following rules:

1. Initially, and whenever u.Ω or the local topology of u change: multicast u.Ω.

2. Upon reception of Ω through channel (v, u): ∀(s, m, S) ∈ Ω , if v / ∈ S then append (s, m, S ∪ {v}) to u.Ω.

3. Whenever there exist s, m and {S 1 , . . . , S n } such that ∀i ∈ {1, . . . , n}, (s, m, S i ∪ {s}) ∈ u.Ω and MinCut ({S 1 , . . . , S n }) > k: append (s, m) to u.Acc.

Condition for reliable communication

Let us consider a given dynamic graph, and two given correct nodes p and q. Our main result is as follows:

Theorem 1. For a given dynamic graph, a k-Byzantine tolerant reliable communication from p to q is feasible if and only if DynMinCut (p, q) > 2k.

Proof. The proof of the "only if" part is in Lemma 1. The proof of the "if" is in Lemma 4.

Lemma 1 (Necessary condition). For a given dynamic graph, let us suppose that there exists an algorithm ensuring reliable communication from p to q. Then, we necessarily have DynMinCut (p, q) > 2k.

Proof. Let us suppose the opposite: there exists an algorithm ensuring reliable communication from p to q, and yet, DynMinCut (p, q) ≤ 2k. Let us show that it leads to a contradiction.

As we have DynMinCut (p, q) = MinCut (Dyn (p, q)) ≤ 2k and MinCut (Dyn (p, q)) = min C∈Cut(Dyn(p,q)) |C|, there exists an element C of Cut (Dyn (p, q)) such that |C| ≤ 2k. Let C 1 be a subset of C containing k elements, with k = min(k, |C|).

Let C 2 = C -C 1 . Thus, we have |C 1 | ≤ k and |C 2 | ≤ k.
According to the definition of Cut (Dyn (p, q)), C contains a node of each possible dynamic path from p to q. Therefore, the information that q receives about p are completely determined by the behavior of the nodes in C.

Let us consider two possible placements of Byzantine nodes, and show that they lead to a contradiction:

• First, suppose that all nodes in C 1 are Byzantine, and that all other nodes are correct. This is possible since

|C 1 | ≤ k.
Suppose now that p broadcasts a message m. Then, according to our hypothesis, since the algorithm ensures reliable communication, q eventually accepts m from p, regardless of what the behavior of the nodes in C 1 may be.

• Now, suppose that all nodes in C 2 are Byzantine, and that all other nodes are correct. This is also possible since

|C 2 | ≤ k.
Then, suppose that p broadcasts a message m = m, and that the Byzantine nodes have exactly the same behavior as the nodes of C 2 had in the previous case.

Thus, as the information that q receives about p is completely determined by the behavior of the nodes of C, from the point of view of q, this situation is indistinguishable from the previous one: the nodes of C 2 have the same behavior, and the behavior of the nodes of C 1 is unimportant. Thus, similarly to the previous case, q eventually accepts m from p.

Therefore, in the second situation, p broadcasts m, and q eventually accepts m = m. Thus, according to Definition 2, the algorithm does not ensure reliable communication, which contradicts our initial hypothesis. Hence, the result.

Lemma 2 (Safety). Let us suppose that all correct nodes follow our algorithm. If (p, m) ∈ q.Acc, then m = p.m 0 .

Proof. As (p, m) ∈ q.Acc, according to rule 3 of our algorithm, there exists {S 1 , . • As S ∈ {S 1 , . . . , S n }, (p, m, S∪{p}) ∈ q.Ω. Thus, P 0 is true if we take u 0 = q and X 0 = S∪{p}.

• Let us now suppose that P i+1 is true, for i < n . As (p, m, X i ) ∈ u i .Ω, according to rule 2 of our algorithm, it implies that u i received Ω from a node v, with (p, m, X) ∈ Ω , v / ∈ X and

X i = X ∪ {v}. Thus, |X| = |X i | -1 = |S ∪ {p}| -(i + 1).
As v ∈ X i and X i is a set of correct nodes, v is correct and behaves according to our algorithm. Then, as v sent Ω , according to rule 1 of our algorithm, we necessarily have Ω ⊆ v.Ω. Thus, as (p, m, X) ∈ Ω , we have (p, m, X) ∈ v.Ω. Hence, P i+1 is true if we take u i+1 = v and X i+1 = X.

By induction principle, P n is true. As |X n | = 0, X n = ø and (p, m, ø) ∈ u n . As u n is a correct node and follows our algorithm, the only possibility to have (p, m, ø) ∈ u n .Ω is that u n = p and m = p.m 0 . Thus, the result. Lemma 3 (Communication). Let us suppose that DynMinCut (p, q) > 2k, and that all correct nodes follow our algorithm. Then, we eventually have (p, p.m 0 ) ∈ q.Acc.

Proof. Let {S 1 , . . . , S n } be the set of node sets S ∈ Dyn (p, q) that only contain correct nodes. Similarly, let {X 1 , . . . , X n } be the set of node sets X ∈ Dyn (p, q) that contain at least one Byzantine node.

Let us suppose that MinCut ({S 1 , . . . , S n }) ≤ k. Then, there exists C ∈ Cut ({S 1 , . . . , S n }) such that |C| ≤ k. Let C be the set containing the nodes of C and the Byzantine nodes. Thus, and C ∈ Cut ({S 1 , . . . , S n } ∪ {X 1 , . . . , X n }) = Cut (Dyn (p, q)), and |C | ≤ 2k. Thus, MinCut (Dyn (p, q)) ≤ 2k, which contradicts our hypothesis. Therefore, MinCut ({S 1 , . . . , S n }) > k.

In the following, we show that ∀S ∈ {S 1 , . . . , S n }, we eventually have (p, p.m 0 , S ∪ {p}) ∈ q.Ω, ensuring that q eventually accepts p.m 0 from p.

Let S ∈ {S 1 , . . . , S n }. As S ∈ Dyn (p, q), let (u 1 , . . . , u N ) be the dynamic path such that p = u 1 , q = u N and S = {u 2 , . . . , u N -1 }. Let (t 1 , . . . , t N ) be the corresponding dates, according to Definition 1. Let us show the following property P i by induction, ∀i ∈ {1, . . . , N }: at date t i , (p, p.m 0 , X i ) ∈ u i .Ω, with X i = ø if i = 1 and {u 1 , . . . , u i-1 } otherwise.

• P 1 is true, as we initially have (p, p.m 0 , ø) ∈ p.Ω.

• Let us suppose that P i is true, for i < N . According to Definition 1, ∀t ∈ [t i , t i + ζ(t i , u i )],
ρ(e i , t) = 1, e i being the edge connecting u i to u i+1 .

-Let t A ≤ t i be the earliest date such that, ∀t ∈ [t A , t i + ζ(t i , u i )], ρ(e i , t) = 1.

-Let t B ≤ t i be the date where (p, m, X i ) is added to u i .Ω.

-Let t C = max(t A , t B ).
Then, at date t C , either u i .Ω or the local topology topology of u i changes. Thus, according to rule 1 of our algorithm, u i multicasts Ω = u i .Ω at date t C , with (p, p.m 0 , X i ) ∈ Ω .

As

ζ(e i , t i ) ≤ t i+1 -t i ≤ t i+1 -t C , u i+1 receives Ω from u i at date t C + ζ(e i , t i ) ≤ t i+1 .
Then, according to rule 2 of our algorithm, (p, p.m 0 , X i ∪ {u i }) is added to u i+1 .Ω.

Thus, P i+1 is true if we take X i+1 = X i ∪ {u i }.

By induction principle, P N is true. As u 1 = p, X N = {u 1 , . . . , u N -1 } = S ∪ {p}, and we eventually have (p, p.m 0 , S ∪ {p}) ∈ q.Ω.

Thus, ∀S ∈ {S 1 , . . . , S n }, we eventually have (p, p.m 0 , S∪{p}) ∈ q.Ω. Then, as MinCut ({S 1 , . . . , S n }) > k, according to rule 3 of our algorithm, (p, p.m 0 ) is added to q.Acc.

Lemma 4 (Sufficient condition). Let there be any dynamic graph. Let p and q be two correct nodes, and k denote the maximum number of Byzantine nodes. If DynMinCut (p, q) > 2k, our algorithm ensures reliable communication from p to q.

Proof. Let us suppose that the correct nodes follow our algorithm, as described in Section 3. First, according to Lemma 2, if (p, m) ∈ q.Acc, then m = p.m 0 . Thus, when q accepts a message from p, p is necessarily the author of this message. Then, according to Lemma 3, we eventually have (p, p.m 0 ) ∈ q.Acc. Thus, q eventually receives and accepts the message broadcast by p. Therefore, according to Definition 2, our algorithm ensures reliable communication from p to q.

Cryptographic reliable communication

If cryptography is available, then it becomes possible to authenticate the sender of a message across multiple hops.

The setting is now the following. Each node p has a private key priv p (only known by p) and a public key pub p (known by all nodes). The node p can encrypt a message m with the function crypt(priv p , m). Any node q can decrypt a message from p with the function decrypt(pub p , m). This function returns NULL if the message was not correctly encrypted. We assume that the Byzantine nodes do not know the private keys of correct nodes.

Then, we modify the previous algorithm as follows. Initially, u.Ω = {(u, crypt(priv u , u.m 0 ))} and u.Acc = {(u, u.m 0 )}. Then, each correct node u obeys to the three following rules:

1. Initially, and whenever u.Ω or the local topology of u change: multicast u.Ω.

2. Upon reception of Ω from a neighbor node: u.Ω = u.Ω ∪ Ω .

3. Whenever there exists (s, m) ∈ u.Ω such that m = decrypt(pub s , m) = N U LL: append (s, m ) to u.Acc.

Theorem 2. If cryptography is available, for a given dynamic graph, a k-Byzantine tolerant reliable communication from p to q is feasible if and only if DynMinCut (p, q) > k.

Proof. If DynMinCut (p, q) ≤ k, then it is possible to cut all dynamic paths between p and q with Byzantine nodes. Thus, q never receives any message from p. Thus, the condition is necessary. Now, let us show that the condition is sufficient.

First, q cannot accept a message (p, m) with m = p.m 0 . Indeed, let us suppose the opposite. According to step 3 of the algorithm, it implies that we have (p, m ) ∈ q.Ω, with decrypt(pub p , m ) = m. Implying that m = crypt(priv p , m). Let v be the first node to have (p, m ) ∈ v.Ω. According to steps 1 and 2 of the algorithm, v cannot be a correct node. Thus, v is Byzantine, implying that a Byzantine node knows priv p : contradiction.

Besides, if DynMinCut (p, q) > k, then there exists at least one dynamic path from p to q. Thus, for the same argument as in Lemma 3, we eventually have (p, crypt(priv p , p.m 0 )) ∈ q.Ω. Thus, according to step 3 of the algorithm, (p, p.m 0 ) is added to q.Acc, and the condition is sufficient.

Case Studies

In this section, we apply our conditions for reliable communication to several case studies: participants interacting in a conference, robots moving on a grid and agents moving in the subway. We show the interest of multihop reliable communication.

A real-life dynamic network: the Infocom 2005 dataset

In this section, we consider the Infocom 2005 dataset [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF], which is obtained in a conference scenario by iMotes capturing contacts between participants. This dataset can represent a dynamic network where each participant is a node and where each contact is a (temporal) edge.

We consider an 8-hour period during the second day of the conference. In this period, we consider the dynamic network formed by the 10 most "sociable" nodes (our criteria of sociability is the total number of contacts reported). We assume that at most one on these nodes may be Byzantine (that is, k = 1). Let p and q be two correct nodes. Let us suppose that p wants to transmit a message to q within a period of 10 minutes. Within 10 minutes, three types of communication can be achieved:

• Direct communication: p meets q directly.

• Non-cryptographic communication: the condition for reliable non-cryptographic communication (Theorem 1) is satisfied.

• Cryptographic communication: the condition for reliable cryptographic communication (Theorem 2) is satisfied.

If we want to ensure reliable communication despite one Byzantine node, the simplest strategy is to wait until p meets q directly. Let us show now that relaying the message is usually beneficial and that our approach realizes a significant gain of performance.

Figure 2 represents the percentage of pairs of nodes (p, q) that communicate within 10 minutes, according to the date of beginning of the communication. We can correlate the peaks with the program of the conference: the first period corresponds to morning arrivals during the keynotes; the peak between 10:30 and 11:00 corresponds to the morning break; the peak starting at 12:30 corresponds to the end of parallel sessions and the departure for lunch.

As it turns out, many pairs of nodes are able to communicate reliably, even though they are unable to meet directly. For instance, at 9:15, 60% of pairs of nodes meet directly, 80% can communicate reliably without cryptography, and 100% can communicate reliably with cryptography. This means that relaying the information is actually effective and desirable.

Probabilistic mobile robots on a grid

We consider a network of 10 mobile robots that are initially randomly scattered on a 10 × 10 grid.

Definition 3 (Grid). An N × N grid is a topology such that:

• Each vertex has a unique identifier (i, j), with 1 ≤ i ≤ N and 1 ≤ j ≤ N .

• Two vertices (i 1 , j 1 ) and (i 2 , j 2 ) are neighbors if and only if:

|j 1 -j 2 | + |i 1 -i 2 | = 1
At each time unit, a robot randomly moves to a neighbor vertex, or does not move (the new position is chosen uniformly at random among all possible choices). Let position(u, t) be the current vertex of the robot u at date t. We consider that two robots can communicate if and only if they are on the same vertex. Our setting induces the following dynamic graph G = (V, E, ρ, ζ): V = {u 1 , . . . , u 10 }, E = V × V , ρ((u, v), t) = 1 when position(u, t) = position(v, t) and ζ((u, v), t) = 0. Let p and q be two correct robots, and suppose that up to k other robots are Byzantine. We aim at evaluating the communication time, that is: the mean time to satisfy the condition for reliable communication with cryptography (Theorem 2) and without cryptography (Theorem 1). For this purpose, we ran more than 10000 simulations, and represented the results on Figure 3 and4. Let us comment on these results.

In Figure 3, we represented the mean communication time varying the maximal number of Byzantine failures k when cryptography is available. This time increases regularly. The case k = 8 corresponds to the case where all the nodes (except p and q) are Byzantine. In this limit case, the only possibility for p and q to communicate is to meet directly.

In Figure 3, we represented the case where cryptography is not available. Here, the aforementioned limit case is reached for k = 4, as the condition for non-cryptographic reliable communication is harder to satisfy.

As we can see, the reliable multihop communication approach can be an interesting compromise. For instance, let us suppose that we want to tolerate one Byzantine failure (k = 1). Let us consider the mean time for p and q to meet directly. If we use our algorithms, this time decreases by 38% without cryptography, and by 51% with cryptography.

Mobile agents in the Paris subway

We consider a dynamic network consisting of 10 mobile agents randomly moving in the Paris subway. The agents can use the classical subway lines (we exclude tramways and regional trains). Each agent is initially located at a randomly chosen junction station -that is, a station that connects at least two lines. Then, the agent randomly chooses a neighbor junction station, waits for the next train, moves to this station, and repeats the process. We use the train schedule provided by the local subway company (http://data.ratp.fr). The time is given in minutes from the departure of the first train (i.e., around 5:30). We consider that two agents can communicate in the two following cases:

1. They are staying together at the same station.

2. They cross each other in trains. For instance, if at a given time, one agent is in a train moving from station A to station B while the other agent moves from B to A, then we consider that they can communicate.

Similarly to the previous case study, we represented the mean communication time with and without cryptography (see Figure 5 and6). The qualitative observations are the same.

Again, let us suppose that we want to tolerate one Byzantine failure (k = 1). Let us consider the mean time for p and q to meet directly. If we use our algorithms, this time decreases by 36% without cryptography, and by 49% with cryptography.

Conclusion

In this paper, we gave the necessary and sufficient condition for reliable communication in a dynamic multihop network that is subject to Byzantine failures. We considered both cryptographic and non-cryptographic cases, and provided algorithms to show the sufficient condition. We then demonstrated the benefits of these algorithms in several case studies.

Our experiments explicitly quantify the benefits of a cryptographic infrastructure (fewer dynamic paths are required, less computations are necessary at each node for accepting genuine messages), but additional tradeofs are worth examining. In practice, ensuring hop by hop integrity through cryptography requires every node on the (dynamic) path to collect the public key of the sender (as it is unlikely that all public keys are initially bundled into the node, for memory size reasons and inclusion/exclusion node dynamics). Actually reaching a trusted authority from a guenuinely dynamic network to obtain this public key raises both bootstrapping and performance issues.

Our result implicitly considers a worst-case placement of the Byzantine nodes, which is the classical approach when studying Byzantine failures in a distributed setting. Studying variants of the Byzantine node placement (e.g. a random placement according to a particular distribution), and the associated necessary and sufficient condition for enabling multihop reliable communication, constitutes an interesting path for future research.

Figure 1 :

 1 Figure 1: Counterexample to Menger's theorem in dynamic graphs.

Figure 2 :

 2 Figure 2: Reliable communication between 10 most sociable nodes of the Infocom 2005 dataset

Figure 3 :

 3 Figure 3: Mean communication time without cryptography (robots)

Figure 4 :

 4 Figure 4: Mean communication time with cryptography (robots)

Figure 5 :Figure 6 :

 56 Figure 5: Mean communication time without cryptography (subway)

  the latency function: ζ(e, t) = T indicates that a message sent at date t takes T time units to cross edge e.

	The discrete time model is a special case, where time and latency are restricted to integer values.

  Let us show the following property P i by induction, ∀i ∈ {0, . . . , n }: there exists a correct node u i and a set of correct nodes X i such that (p, m, X i ) ∈ u i .Ω and |X i | = |S ∪ {p}| -i.

. . , S n } such that, ∀i ∈ {1, . . . , n}, (p, m, S i ∪ {p}) ∈ q.Ω, and MinCut ({S 1 , . . . , S n }) > k. Suppose that each node set S ∈ {S 1 , . . . , S n } contains at least one Byzantine node. If C is the set of Byzantine nodes, then C ∈ Cut ({S 1 , . . . , S n }) and |C| ≤ k. This is impossible because MinCut ({S 1 , . . . , S n }) > k. Therefore, there exists S ∈ {S 1 , . . . , S n } such that S does not contain any Byzantine node. Now, let us use the correct dynamic path corresponding to S to show that m = m 0 . Let n = |S ∪ {p}|.


Cédric Join
email: cedric.join@univ-lorraine.fr

Hassane Abouaïssa
email: hassane.abouaissa@univ-artois.fr

Michel Fliess
email: michel.fliess@polytechnique.edu

A fresh look at ramp metering control: ALINEA without any tedious calibration

Keywords: Highway, ramp metering, critical density, free-flow speed, closed-loop control, ALINEA, estimation, calibration

ALINEA is a well known ramp metering closed-loop control the aim of which is to improve highway traffic. This report shows that ALINEA may be slightly modified in order to be efficiently implemented without any need of crucial time-varying quantities, like the critical density and the free-flow speed, which are most difficult to estimate correctly online. Some convincing computer experiments, which employ real data, are displayed and discussed.

Introduction

The goal of ramp metering is to improve the highway traffic conditions by an appropriate regulation of the inflow from the on-ramps to the highway mainstream (see, e.g., [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF]). This is depicted in Figure 1 where • q r , in veh/s, is the ramp flow related to the control variable r,

• w represents the queue length in vehicles,

• d, in veh/s, is the ramp demand,

• q e , in veh/s, is the upstream segment flow,

• q s , in veh/s, is the downstream segment flow,

• ρ s , in veh/m, is the segment density,

• v s , in m/s, is the segment speed.

Quite diverse approaches have been proposed. Among the various feedback control laws which may be found in the literature, ALINEA, which

• is an acronym of the French words Asservissement LINéaire d'Entrée Autoroutière,

• was introduced more than twenty five years ago ([8, 9, 20]), certainly still is the most popular one, thanks to the numerous variants which have been published (see, e.g, [START_REF] Papamichail | Traffic-responsive linked ramp-metering control[END_REF][START_REF] Smaragdis | A series of new local ramp metering strategies[END_REF][START_REF] Smaragdis | A flow-maximizing adaptive local ramp metering strategy[END_REF], and the references therein). Moreover, ALINEA is, to the best of our knowledge, one on the very few closed-loop control synthesis which has been implemented in practice. Notice that some open-loop control strategies have also been used (see, e.g, [START_REF] Middelham | Ramp metering in the Netherlands: An overview[END_REF][START_REF] Owens | Access control on the M6 motorway : evaluation of Britain's first ramp metering scheme[END_REF]). The quality of any control law depends on a good knowledge of the highway characteristics, especially the critical density and the free-flow speed, which are unfortunately most difficult to estimate in real time. The purpose of this study is to show that a slight change of the ALINEA algorithm may be successfully implemented without the need of such a knowledge. This is an adaptation of a similar result [START_REF] Abouaïssa | Freeway ramp metering control made easy and efficient[END_REF] for an "intelligent" controller derived from model-free control [START_REF] Fliess | Model-free control[END_REF].

Our paper is organized as follows. Short reviews on the traffic parameter estimation and on the usual ALINEA control algorithm are provided respectively in Sections 2 and 3.1. Section 3.2 displays our modified ALINEA algorithm. Computer experiments are discussed in Section 4. The conclusion in Section 5 explains why we are publishing this research report neither in a journal nor in the proceedings of a conference.

Fundamental diagram: a short overview

Most important parameters for obtaining a good traffic characterization may be obtained from May's fundamental diagram [START_REF] May | Traffic Flow Fundamentals[END_REF], depicted in Figure 2. This diagram is defined by

V (ρ i ) = v f exp - 1 a ρ i ρ c a (1)
where

• ρ i is the density of the segment i of the highway,

• V is the corresponding the mean speed,

• v f is the free-flow speed,

• ρ c the critical density,

• a is a model parameter.

Let us stress that Formula (1) is

• not derived from any law of pure physics,

• a rather rough heuristic approximation.

Offline techniques like, e.g, [START_REF] Alessandri | Nonlinear optimization for freeway control using variablespeed signaling[END_REF][START_REF] Chien | Traffic density control for automated highway systems[END_REF][START_REF] Karaaslan | Two proposals to improve freeway traffic flow[END_REF][START_REF] Nanthawichit | Parameter estimation of macroscopic traffic simulation model[END_REF] do not permit to take into account of the parameter variations. This explains the development of several online settings, like 1. extended Kalman filters (see, e.g., [START_REF] Ozbay | Improved online estimation methods for feedback-based freeway ramp metering strategy[END_REF][START_REF] Wang | Real-time freeway traffic state estimation based on extended Kalman filters: general approach[END_REF][START_REF] Wang | Real-time freeway traffic state estimation based on extended Kalman filter: Adaptive capabilities and real data testing[END_REF]), 2. adaptive least square techniques (see, e.g., [START_REF] Wang | Real-time parallel estimators for a second-order macroscopic traffic flow model[END_REF]),

algebraic estimation techniques [1, 2],

4. various other viewpoints (see, e.g., [START_REF] Bellemans | Model predictive control with repeated model fitting for ramp metering[END_REF][START_REF] Herrera | Incorporation of Lagrangian measurements in freeway traffic state estimation[END_REF][START_REF] Work | A traffic model for velocity data assimilation[END_REF]).

Although the third approach yields often fair results, it should be stressed that the approximate nature of Equation (1) does not allow until today fully satisfactory estimates.

ALINEA

Basic ALINEA

The feedback loop defining ALINEA reads

r(k) = r(k -1) + K I (ρ -ρ s )
where • r(k), which is the rate of ramp inflow (see Figure 1), stands for the control variable,

• the gain K I is the only adjustment parameter,

• the segment density ρ s (see Figure 1) stands for the output variable,

• ρ is the reference trajectory,

• e = ρ -ρ s is the tracking error.

ALINEA may be therefore viewed as

• a discrete-time analogue of a simple integrator,

• corresponding to the I in the classic PID controllers,

The reference ρ is usually close to the critical density ρ c , i.e., a quantity which is, as already stated, most difficult to estimate.

Modifying ALINEA

The following rules for choosing ρ permit to bypass the above calibration:

• Let V filtered be the filtered mean speed and V threshold the speed threshold. 1

1 Concrete studies (see, e.g., [START_REF] Cete Méditerranée | Niveaux de service des réseaux routiers en PACA : Etat en 2004, Evolution estimée à l'horizon[END_REF]) have demonstrated that the level of service is highly damaged and that the congestion phenomenon is reaching its maximum, when the mean speed of individual vehicle is about 5 m/s. The threshold of discomfort is reached, when this speed is equal to 20 m/s.

• ρ d0 , ρ inc , ρ dec denote respectively the initial density, the increment and decrement of the desired density.

• If V filtered > V threshold , then ρ = ρ d0 + ρ inc .

• If V filtered < V threshold , then ρ = ρ d0 -ρ dec .

Computer experiments

Our computer simulations are based on numerical data which are collected from the French highway A4Y with one on-ramp: see Figures 3 and4-(d). The macroscopic models (see, e.g., [START_REF] Papageorgiou | Some remarks on macroscopic traffic flow modelling[END_REF]), which are employed for computer simulations, are

• heuristic,
• quite sensitive to parameter variations and uncertainties.

The only available accurate physical law is the conservation equation. All other equations, which for instance are connected to the speed and the fundamental diagram, are based on empirical observations which yield coarse approximations. The main parameters such as the critical density and the free-flow speed are moreover subject to variations. Two cases are studied:

1. ALINEA control by setting, as in Section 3.1, ρ = ρ c , which is assumed to be well estimated and constant: see Figures 4 and5, 2. ALINEA control by selecting ρ as in Section 3.2: see Figures 6 and7.

The control is relaxed if the queue length w (see Figure 1) is greater than 500. Some numerical results for important quantities are reported in Tables 1 and2. The differences between those results for the two cases is rather small. It confirms that the tedious estimation of the critical density may be avoided without any harm.

Conclusion

Due the difficulties related to the online estimation, only real data with a constant critical density were available. Although computer simulations with an artificial time-varying critical density were achieved, which show a great superiority of our modified ALINEA, we decided not to show them here. We hope that some future work will confirm this fact via real data and concrete experiments.

Figure 1 .

 1 Figure 1. Highway ramp metering principle

Figure 2 .

 2 Figure 2. Fundamental diagram: an example

Figure 3 .

 3 Figure 3. Aerial view of the site (Source: DiRIF (Direction des Routes Île-de-France))

  (a) Control r (b) Density ρs (blue) and ρ (red) (c) Flow qs (d) Demands d (red) and qe (blue)

Figure 4 .Figure 5 .Figure 6 .Figure 7 .

 4567 Figure 4. Case 1: simulation results

Table 1 .

 1 Summary of a single day

		Total Time Spent Mean Speed Mean Speed (with queue)
	Case 1	9.2270e+06	15.1810	7.5590
	Case 2	9.1320e+06	15.3388	7.2552
		Total Time Spent Mean Speed Mean Speed (with queue)
	Case 1	6.3191e+06	11.4727	5.0550
	Case 2	6.2654e+06	11.5734	5.0309

Table 2 .

 2 Congestion times between 7.30am and 9.30am, and between 3pm and 8pm