Achour Mostéfaouil

Hamouma Moumen

Michel Raynal

A Mostéfaoui

Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n 2 ) Messages

Keywords: Abstraction, Asynchronous message-passing system, Broadcast abstraction, Byzantine process, Common coin, Consensus, Distributed algorithm, Optimal resilience, Randomized algorithm, Signature-free algorithm, Simplicity. Consensus Byzantin Asynchrone Abstraction, Diffusion, Nombre aléatoire, Processus byzantin, Système asynchrone, Optimalité

This paper presents a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes, where n is the total number of processes. In addition of being signature-free and optimal with respect to the value of t, this algorithm has several noteworthy properties: the expected number of rounds to decide is four, each round is composed of two or three communication steps and involves O(n 2 ) messages, and a message is composed of a round number plus a single bit. To attain this goal, the consensus algorithm relies on a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main target when designing this algorithm was to obtain a cheap and simple algorithm. This was motivated by the fact that, among the first-class properties, simplicity -albeit sometimes under-estimated or even ignored-is a major one.

Protocol

n > signatures msgs/round bits/msg steps/round Rabin 1983 [START_REF] Rabin | Randomized Byzantine generals[END_REF] 10t yes O(n 2 ) O(1) 2 Berman Garay 1993 [START_REF] Berman | Randomized distributed agreement revisited[END_REF] 5t no O(n 2 ) O(1) 2 Friedman Mostefaoui Raynal 2005 [START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF] 5t no O(n 2 ) O(1) 1 Bracha 1987 [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] 3t no O(n 3 ) O(log(n)) 9 Srikanth Toueg 1987 [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF] 3t no O(n 3 ) O(log(n)) 5 Toueg 1984 [START_REF] Toueg | Randomized Byzantine agreement[END_REF] 3t yes O(n 3 ) O(n) 3 Canetti Rabin 1993 [START_REF] Canetti | Fast asynchronous Byzantine agreement with optimal resilience[END_REF] 3t yes O(n 2 ) poly(n) 9 Cachin Kursawe Shoup 2000 [START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF] 3t 1. All these algorithms, which address binary consensus, are round-based, and, in each of them, each message carries a round number. Hence, when comparing their message size, we do not consider round numbers. We have the following.

• The first algorithm is such that n < 10t, has an O(n 2 ) message complexity, and requires signatures.

• The algorithms of the two next lines are such that t < n/5, and their message complexity is O(n 2 ). These algorithms are simple, signature-free, and use one or two communication steps per round, but none of them is optimal with respect to t-resilience. • The algorithms of the next three lines are optimal with respect to t, but have an O(n 3 ) message complexity. Moreover, [START_REF] Toueg | Randomized Byzantine agreement[END_REF] uses signed messages, while [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] does not use a common coin, and may consequently execute an exponential number of rounds. Due to their message complexity, and their number of communication steps per round, these algorithms are costly. • The algorithm proposed in [START_REF] Canetti | Fast asynchronous Byzantine agreement with optimal resilience[END_REF], although polynomial, has a huge bit complexity. The algorithm presented in [START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF] is optimal with respect to t, uses only O(n 2 ) messages per round, has two communication steps per round, and uses signed messages (the value ℓ in the bit complexity corresponds to the size of RSA signatures). However, as noticed by its authors, "because of public key operations, the computational complexity of this protocol is typically higher than those using authentication codes".

Content of the paper

The paper first introduces a simple broadcast abstraction suited to binary values, that we call BV-broadcast. This broadcast focuses on values and not on processes, which means that it does not consider the fact that "this" value has been broadcast by "this" process. BV-broadcast, whose implementation is particularly simple, reduces the power of Byzantine processes, in such a way that a value broadcast only by Byzantine processes is never delivered to the correct processes. This value-oriented broadcast abstraction is then used to solve asynchronous Byzantine binary consensus is asynchronous systems enriched with a common coin. The resulting consensus algorithm is a round-based asynchronous algorithm that has the following noteworthy features.

• The algorithm requires t < n/3 and is consequently optimal with respect to t.

• The algorithm uses 2 or 3 communication steps per round (2 steps when the correct processes start a round with the same estimate of the decision value). • The expected number of rounds to decide is 4.

• The message complexity is O(n 2 ) messages per round.

• Each message carries its type, a round number plus a single data bit.

• Finally, the algorithm does not require signed messages.

Hence, contrarily to what one could believe from existing asynchronous Byzantine binary consensus algorithms, the formula [quadratic message complexity] ⇒ [(use of signatures) ∨ (t < n/5)] is false. The proposed algorithm shows that t < n/3 (as in [START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF]), quadratic message complexity (as in [START_REF] Berman | Randomized distributed agreement revisited[END_REF][START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF]), and absence of signatures (as in [START_REF] Berman | Randomized distributed agreement revisited[END_REF][START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF]) are not incompatible.

Simplicity is a first class property When designing this algorithm, an important issue was to obtain a simple Byzantine consensus algorithm. Our guiding mantra while designing the proposed algorithm was the famous sentence of Einstein "make it as simple as possible, but not simpler". This was not an easy task as simplicity is rarely obtained for free. Let us also remember the following sentence written by Pascal at the end of a letter to a friend "I apologize for having written such a long letter, I had not enough time to write a shorter one". The implication "simple ⇒ easy" is rarely true for non-trivial problems [START_REF] Aigner | Proofs from THE BOOK[END_REF]. Simplicity requires effort, but is very rewarding. It is a first class scientific property which participates in the beauty of science1 and makes pedagogy easier.

Roadmap

The paper is composed of 5 sections. Section 2 presents the computation model. Section 3 presents and proves correct the binary-value broadcast abstraction, while Section 4 presents and proves correct the consensus algorithm. Finally, Section 5 concludes the paper.

Computation Model

Asynchronous processes The system is made up of a finite set Π of n > 1 asynchronous sequential processes, namely Π = {p 1 , . . . , p n }. "Asynchronous" means that each process proceeds at its own pace, which may vary arbitrarily with time, and remains always unknown to the other processes.

Communication network

The processes communicate by exchanging messages through an asynchronous reliable point-to-point network. "Asynchronous" means that a message that has been sent is eventually received by its destination process, i.e., there is no bound on message transfer delays. "Reliable" means that the network does not loss, duplicate, modify, or create messages. "Point-to-point" means that there is a bi-directional communication channel between each pair of processes. Hence, when a process receives a message, it can identify its sender.

A process p i sends a message to a process p j by invoking the primitive "send TAG(m) to p j ", where TAG is the type of the message and m its content. To simplify the presentation, it is assumed that a process can send messages to itself. A process receives a message by executing the primitive "receive()".

The operation broadcast TAG(m) is a macro-operation which stands for "for each j ∈ {1, . . . , n} send TAG(m) to p j end for".This operation is usually called unreliable broadcast (if the sender crashes in the middle of the for loop, it is possible that only an arbitrary subset correct processes receives the message).

Failure model Up to t processes may exhibit a Byzantine behavior. A Byzantine process is a process that behaves arbitrarily: it may crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, perform arbitrary state transitions, etc. Hence, a Byzantine process, which is assumed to send a message m to all the processes, can send a message m 1 to some processes, a different message m 2 to another subset of processes, and no message at all to the other processes. Moreover, Byzantine processes can collude to "pollute" the computation. A process that exhibits a Byzantine behavior is called faulty. Otherwise, it is correct.

Let us notice that, as each pair of processes is connected by a channel, no Byzantine process can impersonate another process. Byzantine processes can modify the message delivery schedule, but cannot affect network reliability.

Notation This computation model is denoted BZ_AS n,t [∅]. In the following, this model is both restricted with a constraint on t and enriched with an object providing processes with additional computational power. More precisely, BZ_AS n,t [n > 3t] denotes the model BZ_AS n,t [∅] where the number of faulty processes is smaller than n/3, and BZ_AS n,t [n > 3t, CC] denotes the model BZ_AS n,t [n > 3t] enriched with the common coin (CC) abstraction as defined in [START_REF] Rabin | Randomized Byzantine generals[END_REF].

The Binary-Value Broadcast Abstraction

Binary-value broadcast

Definition This communication abstraction (in short, BV-broadcast) in an all-to-all abstraction that provides the processes with a single operation denoted BV_broadcast(). When a process invokes BV_broadcast TAG(m), we say that it "BV-broadcasts the message TAG(m)". The content of a message m is 0 or 1 (hence the term "binary-value" in the name of this communication abstraction).

In a BV-broadcast instance, each correct process p i BV-broadcasts a binary value and obtains binary values. To store the values obtained by each process, BV-broadcast provides each correct process p i with a read-only local variable denoted bin_values i . This variable is a set, initialized to ∅, which increases when new values are received. VB-broadcast is defined by the four following properties.

• BV-Obligation. If at least (t+1) correct processes BV-broadcast the same value v, v is eventually added to the set bin_values i of each correct process p i . • BV-Justification. If p i is correct and v ∈ bin_values i , v has been BV-broadcast by a correct process.

• BV-Uniformity. If a value v is added to the set bin_values i of a correct process p i , eventually v ∈ bin_values j at every correct process p j . • BV-Termination. Eventually the set bin_values i of each correct process p i is not empty.

The following property is an immediate consequence of the previous properties.

Property 1.

Eventually the sets bin_values i of the correct processes p i become non-empty and equal, contain all the values broadcast by correct processes and no value broadcast only by Byzantine processes.

A BV-broadcast algorithm

A simple algorithm implementing the BV-broadcast abstraction is described in Figure 1. This algorithm is based on a particularly simple "echo" mechanism. Differently from previous echo-based algorithms (e.g., [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF]), echo is used here with respect to each value that has been received (whatever the number of processes that broadcast it), and not with respect to each pair composed of a value plus the identity of the process that broadcast this value. In the algorithm of Figure 1, a value entails a single echo, whatever the number of processes that have broadcast this value.

When a process invokes BV_broadcast MSG(v), v ∈ {0, 1}, it broadcasts B_VAL(v) to all the processes (line 01). Then, when a process p i receives (from any process) a message B_VAL(v), (if not yet done) it forwards this message to all the processes (line 03) if it has received the same message from at least (t + 1) different processes (line 02). Moreover, if p i has received v from at least (2t + 1) different processes, the value v is added to bin_values i .

operation BV_broadcast MSG(v i ) is (01) broadcast B_VAL(v i ). when B_VAL(v) is received (02) if B_VAL(v) received from (t +
1: An algorithm implementing BV-broadcast in BZ_AS n,t [n > 3t]
Remark It is important to notice that no correct process p i can know when its set bin_values i has obtained its final value. (Otherwise, consensus will be directly obtained by directing each process p i to deterministically extract the same value from bin_values i ). This impossibility is due to the net effect of asynchrony and process failures [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF].

Proof and cost of the algorithm

Theorem 1. The algorithm described in Figure 1 implements the BV-broadcast abstraction in the system model BZ_AS n,t [t < n/3].

Proof Proof of the BV-Obligation property. Let v be a value such that (t + 1) correct processes invoke BV_broadcast MSG(v). It follows from the predicate of line 02 that each correct process eventually receives these (t + 1) messages, and consequently each correct process broadcasts exactly once the message B_VAL(v) to all the processes. As the channels are reliable, it follows that the predicate of line 05 is eventually satisfied at each correct process, and consequently, the property follows.

Proof of the BV-Justification property. To show this property, we prove that a value BV-broadcast only by faulty processes cannot be added to the set bin_values i of a correct process p i . Hence, let us assume that only faulty processes BV-broadcast v. It follows that a correct process can receive the message B_VAL(v) from at most t different processes. Consequently the predicate of line 02 cannot be satisfied at a correct process. Hence, the predicate of line 05 cannot be satisfied either at a correct process, and the property follows.

Proof of the BV-Uniformity property. If a value v is added to the set bin_values i of a correct process p i (local delivery), this process has received B_VAL(v) from at least (2t+1) different processes (line 05), i.e., from at least (t+1) different correct processes. As each of these correct processes has sent this message to all the processes, it follows that the predicate of line 02 is eventually satisfied at each correct process, which consequently broadcasts B_VAL(v) to all. As nt ≥ 2t + 1, the predicate of line 05 is then eventually satisfied at each correct process, and the BV-Uniformity property follows.

Proof of the BV-Termination property. As (a) there are at least (nt) correct processes, (b) each of them invokes BV_broadcast MSG(), (c) nt ≥ 2t + 1 = (t + 1) + t, and (d) only 0 and 1 can be BV-broadcast, it follows that there is a value v ∈ {0, 1} that is BV-broadcast by at least (t + 1) correct processes. The proof of the BV-Termination property is then an immediate consequence of the BV-Obligation property.

✷ T heorem 1

Cost of the algorithm As far as the cost of the algorithm is concerned, we have the following for each BV-broadcast instance.

• If all correct processes BV-broadcast the same value, the algorithm requires a single communication step. Otherwise, it can require two communication steps. • Let c ≥ nt be the number of correct processes.

The correct processes send c n messages if they BV-broadcast the same value, and send 2 c n messages otherwise.

• In addition to the control tag B_VAL, a message carries a single bit. Hence, message size is constant.

The Byzantine Consensus Algorithm

Byzantine consensus and enriched model

Binary Byzantine consensus The Byzantine consensus problem has been informally stated in the Introduction. Assuming that each correct process p i proposes a value v i ∈ {0, 1}, each of them has to decide a value such that the following property are satisfied.

• BC-Validity. A decided value was proposed by a correct process.

• BC-Agreement. No two correct processes decide different values.

• BC-One-shot. A correct process decides at most once.

• BC-Termination. Each correct process decides.

The BC-Validity property states that no value proposed only by faulty processes can be decided. As we consider binary consensus, it is equivalent to the following property: if all correct processes propose the same value v, the value v cannot be decided (where v is the other binary value).

From binary to multivalued Byzantine consensus Interestingly, asynchronous multivalued Byzantine consensus (i.e., when more than two values can be proposed) can be solved on top of binary Byzantine consensus. Such constructions are described in [START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF][START_REF] Mostéfaoui | Signature-free broadcast-based intrusion tolerance: never decide a Byzantine value[END_REF][START_REF] Song | Bosco: one-step Byzantine asynchronous consensus[END_REF] (see [START_REF] Turpin | Extending binary Byzantine agreement to multivalued Byzantine agreement[END_REF] for synchronous systems).

Enriching the basic asynchronous model: Rabin's common coin

As indicated in the Introduction, the basic system model BZ_AS n,t [t < n/3] has to be enriched so that Byzantine consensus can be solved. The additional computational power we consider here is a common coin (CC) as defined by Rabin [START_REF] Rabin | Randomized Byzantine generals[END_REF]. As already indicated, the corresponding enriched system model is denoted BZ_AS n,t [t < n/3, CC]. A common coin can be seen as a global entity that delivers the very same sequence of random bits b 1 , b 2 , . . . , b r , . . . to processes, each bit b r has the value 0 or 1 with probability 1/2.

More precisely, this oracle provides the processes with a primitive denoted random() that returns a bit each time it is called by a process. In addition to being random, this bit has the following global property: the r th invocation of random() by a correct process p i returns it the bit b r . This means that the r th invocations of random() by any pair of correct processes p i and p j return them b r . A common coin is built in such a way that the processes need to cooperate to compute the value of each bit b r . This is required to prevent Byzantine processes from computing bit values in advance and exploit these values to produce message delivery schedule that would prevent termination2 . The reader interested in the implementation of such a common coin can consult [START_REF] Aspnes | Lower bounds for distributed coin flipping and randomized consensus[END_REF][START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF].

On randomized consensus When using additional computing power provided by common coins, the consensus termination property can no longer be deterministic. Randomized consensus is defined by BC-Validity (Obligation), BC-Agreement, plus the following BC-Termination property [START_REF] Ben-Or | Another advantage of free choice: completely asynchronous agreement protocols[END_REF][START_REF] Rabin | Randomized Byzantine generals[END_REF]: Every non-faulty process decides with probability 1. For round-based algorithms, this termination property is re-stated as follows: For any correct process p i : lim r→+∞ Probability [p i decides by round r] = 1.

Randomized Byzantine consensus algorithm

Principles and description of the algorithm The consensus algorithm is described in Figure 2. It requires t < n/3 and is consequently optimal with respect to the maximal number t of Byzantine processes that can be tolerated. A process p i invokes propose(v i ) where v i ∈ {0, 1} is the value it proposes. It decides when it executes the statement decide(v) at line 08.

The local variable est i of a process p i keeps its current estimate of the decision (initially est i = v i ). The processes proceed by consecutive asynchronous rounds and a BV-broadcast instance is associated with each round. The local variable r i denotes the current round of process p i , while the local variable bin_values i [r i ] denotes the local read-only variable bin_values i associated with the BV-broadcast instance used at round r i .

operation propose(v i ) est i ← v i ; r i ← 0; repeat forever (01) r i ← r i + 1; (02) BV_broadcast EST[r i ](est i ); (03) wait until (bin_values i [r i ] = ∅); % bin_values i [r i ]
has not necessarily obtained its final value when the wait statement terminates % (04

) broadcast AUX[r i ](w) where w ∈ bin_values i [r i ]; (05) wait until ∃ a set of (n -t) AUX[r i ](x) messages delivered from distinct processes such that values i ⊆ bin_values i [r i ]
where values i is the set of values x carried by these (nt) messages✁ : The behavior of a correct process p i during a round r i can be decomposed in three phases.

(06) s ← random(); (07) if (values i = {v}) % i.e.,|values i | = 1 % (08) then if (v = s) then decide(v) if not yet done end if; (09) est i ← v (10) else est i ← s (11) end if end repeat.
• Phase 1: lines 01-03. This first phase is an exchange phase. During a round r i , a process p i first invokes BV_broadcast EST[r i ](est i ) (line 02) to inform the other processes of the value of its current estimate est i . This message is tagged EST and associated with the round number r i (hence the notation EST[r i ]()). Then, p i waits until its underlying read-only BV-broadcast variable bin_values i [r i ] is no longer empty (line 03). Due to the BV-Termination property, this eventually happens. When the predicate becomes satisfied, bin_values i [r i ] has not yet necessarily its final value, but it contains at least one value ∈ {0, 1}. Moreover, due to the BV-Justification property, the values in bin_values i [r i ] were BV-broadcast by correct processes. • Phase 2: lines 04-05. The second phase is also an exchange phase during which each correct process p i invokes broadcast AUX[r i ](w) where w is a value that belongs to bin_values i [r i ] (line 04). Let us notice that all the correct processes p j broadcast a value of their set bin_values j [r j ] (i.e., an estimate value of a correct process), while a Byzantine process can broadcast an arbitrary binary value. To summarize, the broadcasts of the second phase inform the other processes of estimate values that have been BV-broadcast by correct processes.

A process p i then waits until the predicate of line 05 becomes satisfied. This predicate is used to discard values sent only by Byzantine processes. From an operational point of view, it states that there is a set values i containing only the values broadcast at line 04 by (nt) distinct processes, and these values originated from correct processes (which BV-broadcast them at line 02). Said in another way, the set values i of a correct process p i cannot contain an estimate value broadcast only by Byzantine processes. Hence, after line 05, we have values i ∈ {0, 1}, and for any v ∈ values i , v is an estimate VB-broadcast by a correct process. • Phase 3: lines 06-11. This last phase is a local computation phase. A correct process p i first obtains the common coin value s associated with the current round (line 06).

-If |values i | = 2, both the value 0 and the value 1 are estimate values of correct processes. In this cases, p i adopts the value s of the common coin (line 10).

following observations: during round r, (a) the set bin_values i [r] of each correct process contains only values BV-broadcast by correct processes (BV-Justification), and eventually the sets of all the correct processes are equal (BV-Uniformity); (b) each of the at least (nt) correct processes p i broadcasts a message AUX[r](w) such that w ∈ bin_values i [r]; (c) each of these messages is eventually received by each correct process.

Claim. With probability 1, there is a round r at the end of which all the correct processes have the same estimate value. (End of the claim.) Assuming the claim holds, it follows from Lemma 1 that all the correct processes p i keep their estimate value est i = v and consequently the predicate values i = {v} at line 07 is true at every round. Due to the common coin CC, it follows that, with probability 1, there is eventually a round in which random() outputs v. Then, the predicates of the lines 07 and 08 evaluate to true, and all the correct processes decide.

Proof of the claim. We need to prove that, with probability 1, there is a round at the end of which all the correct processes have the same estimate value. Let us consider a round r.

• If all the correct processes execute line 10, they all adopt the value of the common coin at the end of round r, and the claim directly follows. • Similarly, if all the correct processes execute line 09, they adopt the same value v as their new estimate, and the claim follows.

• The third case is when some correct processes execute line 09 and adopt the same value v, while others execute line 10 and adopt the same value s.

Due to the properties of the common coin, the value it computes at a given round is independent from the values it computes at the other rounds (and also from the Byzantine processes and the network scheduler). Thus, s is equal to v with probability p = 1/2. Let P (r) be the following probability (where x r is the value of x at round r): P Proof As indicated in the proof of Lemma 5, termination is obtained in two phases. First, all the correct processes must adopt the same value v. Second, the outcome of the common coin has to be the same as the commonly adopted value v.

(r) = Probability[∃r ′ : r ′ ≤ r : v r ′ = s r ′ ]. We have P (r) = p + (1 -p)p + • • • + (1 -p) r-1 p. So, P (r) = 1 -(1 -p) r .
It follows from the proof of Lemma 5 that there is only one situation in which the correct processes do not adopt the same value. This is when the predicate of line 07 is satisfied for a subset of correct processes and not for the other correct processes. Thus, the expected number of rounds for this to happen is 2. As for the second phase, here again, the probability that the value output by the common coin is the same as the value held by all the correct processes is 1/2. Thus, the expected time for this to occur is also 2. Combining the two phases, the expected termination time is 4 rounds (i.e., a small constant).

✷ T heorem 3

Cost of the algorithm As far as the cost of the algorithm is concerned, we have the following, where c ≥ nt denotes the number of correct processes.

• If the correct processes propose the same value, each round requires two communication steps (one in the BV-broadcast and one broadcast), and the expected number of rounds to decide is two. Moreover, the total number of messages sent by correct processes is then 2 c n. • If the correct processes propose different values, each round requires three communication steps (two in the BV-broadcast and one broadcast), and the expected number of rounds to decide is four. Moreover, the total number of messages sent by the correct processes is then 4 c n per round. • In addition to a round number, both a message EST[r]() and a message AUX[r]() sent by a correct process carry a single bit.

An underlying message B_VAL() has to carry a round number and a bit. • The total number of bits exchanged by the correct processes is O(n 2 r log r) where r is the number of rounds executed by the correct processes. Hence, the expected bit complexity is O(n 2 ).

Conclusion

This paper has presented a new consensus algorithm suited to asynchronous systems composed of n processes, and where up to t < n/3 processes may have a Byzantine behavior. This algorithm relies on Rabin's common coin and an underlying binary-value broadcast algorithm which guarantees that a value broadcast only by Byzantine processes is never delivered to the correct processes.

In addition to being t-resilient optimal, the algorithm, which is round-based and signature-free, uses two or three communication steps per round (this depends on the estimate values of the correct processes at the beginning of a round), and O(n 2 ) messages per rounds. Moreover, each message carries a round number and a single bit, and the expected number of rounds to decide is four. Finally, as claimed in the Introduction, and in addition to its efficiency-related properties, a very important first class property of the proposed algorithm lies in its design simplicity.

Collection des Publications Internes de l'Irisa c IRISA

Figure

  Figure 1: An algorithm implementing BV-broadcast in BZ_AS n,t [n > 3t]

Figure 2 :

 2 Figure 2: A BV-broadcast-based algorithm implementing binary consensus in BZ_AS n,t [n > 3t, CC]

5 Theorem 2 .T heorem 2 Theorem 3 .

 5223 As lim r→+∞ P (r) = 1, the claim follows. (End of the proof of the claim.) ✷ Lemma The algorithm described in Figure 2 solves the randomized binary consensus problem in the system model BZ_AS n,t [t < n/3, CC]. Proof BC-Validity follows from Lemma 3. BC-Agreement follows from Lemma 4. BC-One-shot follows from line 08. BC-Termination follows from Lemma 5.✷ Let n > 3t. The expected decision time is constant (four rounds).

Table 1 :

 1 Cost and constraint of different Byzantine binary consensus algorithms Round-based asynchronous Byzantine algorithms based on a common coin are listed in Table

	yes	O(n 2 )	O(ℓ)	2

Collection des Publications Internes de l'Irisa c IRISA

To quote Dijkstra: "When we recognize the battle against chaos, mess, and unmastered complexity as one of computing science's major callings, we must admit that "Beauty is our Business"."[START_REF] Dijkstra | Some beautiful arguments using mathematical induction[END_REF].Collection des Publications Internes de l'Irisa c IRISA

As just indicated, this assumption on the common coin computation is due to the fact that Byzantine processes are not prevented from controlling message delivery schedule, thereby rendering random numbers helpless. It would be possible to let Byzantine processes know in advance the sequence of random bits, as long as they cannot control message delivery schedules (this assumption corresponds to the oblivious scheduler model[START_REF] Aspnes | Lower bounds for distributed coin flipping and randomized consensus[END_REF]).Collection des Publications Internes de l'Irisa c IRISA

-If |values i | = 1, p i decides v (the single value present in values i ) if additionally s = v (line 08). Otherwise it adopts v as its new estimate (line 09).

The statement decide() used at line08 allows the invoking process p i to decide but does not stop its execution. A process executes round forever. This facilitates the description and the understanding of the algorithm.

Proof and cost of the algorithm

Notation Let p i be a correct process. values r i denotes the value of the local variable values i which makes satisfied the predicate of line 05 at round r.

Lemma 1.

Let n > 3t. Consider the situation where, at the beginning of a round r, all the non-faulty processes have the same estimate value v. These processes will never change their estimates, thereafter.

Proof If all the correct processes (which are at least nt > t + 1) have the same estimate value v at beginning of a round r, they all BV-broadcast EST[r](v) at line 02. It follows that the set bin_values i [r] of each correct process p i contains v (BV-Obligation property) and only v (BV-Justification property). Hence, due to the lines 04, 07, and 09, the estimate est i of any correct process p i is set to v, which concludes the proof of the lemma.

✷ Lemma 1

Lemma 2. Let n > 3t, and p i and p j be two correct processes. (values

Proof Let us consider a correct process p i and assume that value r i = {v}. It follows from the predicate of line 05 that p i has received the same message AUX[r](v) from at least (nt) different processes. As at most t processes can be Byzantine, it follows that p i has received AUX[r](v) from at least (n -2t) different correct processes, i.e., as n -2t ≥ t + 1, from at least (t + 1) correct processes.

Let us consider another correct process p j such that value r j = {w}. This process received the message AUX[r](w) from at least (nt) different processes. As (nt) + (t + 1) > n, it follows that one correct process p x sent AUX[r](v) to p i and AUX[r](w) to p i . As p x is correct, it sent the same message to all the processes. Hence v = w, which concludes the proof of the lemma. ✷ Lemma 2 Lemma 3. Let n > 3t. A decided value is a value proposed by a correct process.

Proof Let us consider the round r = 1. It follows from (a) the BV-Justification property of the BV-broadcast (line 02), (b) the wait statement at line 03, and (c) the broadcast by each correct process p j of a value taken from its set bin_values j [START_REF] Aigner | Proofs from THE BOOK[END_REF], that, the set values i computed at line 05 by any correct process p i contains only estimate values of correct processes. Then, if values i = {v} and v is equal to the value s of the common coin, v is decided. Be the value v decided or not, p i adopts it as new estimate (line 09). If values i = {0, 1}, both values have been proposed by correct processes and p i adopts the one defined by the common coin as its new estimate (line 10). In all cases, the estimate value of a correct process is equal to a proposed value. Then the same reasoning applies to all other rounds, from which it follows that a decided value is an estimate value that was proposed by a correct process.

✷ Lemma 3

Lemma 4. No two non-faulty processes decide different values.

Proof Let r be the first round at which processes decide. If two correct processes p i and p j decide at round r, they decide the same value, namely, the value of the common coin associated with round r, and update their estimates to the value of the common coin. Moreover, due to Lemma 2, if p i decides v during round r, there is no correct process p j such that value r i = {w}, with w = v. Hence, if a process p j does not decide during r, we necessarily have values r j = {v, w} = {0, 1}. It follows that such a process p j executes line 10, and assigns the value of the common coin to its estimate est j .

Hence, at the beginning of round (r + 1), the estimates of all the correct processes are equal to the common coin, which is itself equal to the decided value v. It then follows from Lemma 1 that they keep this value forever. As a decided value is a an estimate value, only v can be decided.

✷ Lemma 4

Lemma 5. Each non-faulty process decides with probability 1.

Proof Let us first prove that no correct process remains blocked forever during a round r. There are two wait statements. Due to the BV-Termination property, no correct process can block forever at line 03. To show that no correct process can block forever at line 05, we have to show that the predicate of line 05 becomes eventually true at every correct process p i . This follows from the Collection des Publications Internes de l'Irisa c IRISA


We study the information propagation speed in multi-lane vehicle-to-vehicle networks such as roads or highways. We focus on the impact of time-varying radio ranges and of multiple lanes of vehicles, varying in speed and in density. We assess the existence of a vehicle density threshold under which information propagates on average at the fastest vehicle speed and above which information propagates dramatically faster. We first prove that no such phase transition occurs if there is only one lane, regardless of the density of vehicles, when one takes into account real-time radio communication range variations at the MAC layer. We then prove that, on the other hand, a phase transition exists as soon as there are multiple lanes with different vehicle speeds and appropriate densities. We characterize conditions under which the phase transition occurs and we derive bounds on the corresponding threshold as a simple relationship between the vehicle density on the fastest lane and the sum of densities on the other lanes. Our results intrinsically encompass a wide range of vehicular network scenarios, including one-way and two-way roads, as well as special cases such as road side units and/or parked cars being used as relays. We confirm our analytical results using simulations.

Multi-lane Vehicle-to-Vehicle Networks with Time-Varying Radio Ranges: Information Propagation Speed Properties Emmanuel Baccelli * , Philippe Jacquet † , Bernard Mans ‡ , Georgios Rodolakis § I. INTRODUCTION We investigate the information propagation speed in vehicleto-vehicle networks such as multi-lane roads or highways. Large countries typically cover a great number of miles with multi-lane roads or highways, in part without telecommunication infrastructure. Our analysis shows the conditions under which a phase transition occurs in this context, concerning information propagation speed, with respect to the vehicle density. We prove that under a certain threshold, information propagates on average at the fastest vehicle speed, while above this threshold, information propagates significantly faster.

With applications such as safety on the road, ad hoc vehicular networks and vehicle-to-vehicle are receiving increasing attention (see recent survey in [START_REF] Dressler | Research challenges in intervehicular communication: lessons of the 2010 Dagstuhl Seminar[END_REF]). Vehicular DTNs (Delay Tolerant Networks, i.e., networks in which end-to-end paths may not exist and communication routes may only be available through mobility and accumulation over time) have thus been considered in recent studies, and various analytical models have been proposed. The papers [START_REF] Agarwal | Phase Transition of Message Propagation Speed in Delay-Tolerant Vehicular Networks[END_REF], [START_REF] Baccelli | Highway Vehicular Delay Tolerant Networks: Information Propagation Speed Properties[END_REF] focus on information propagation speed in one-dimensional vehicle-to-vehicle with constant speeds in each direction. In [START_REF] Agarwal | Phase Transition of Message Propagation Speed in Delay-Tolerant Vehicular Networks[END_REF] the authors introduce a model based on space discretization to derive upper and lower bounds in the highway model under the assumption that the radio propagation speed is finite. Their bounds indicate the existence of a phase transition phenomenon for the information propagation speed. Comparatively in [START_REF] Baccelli | Highway Vehicular Delay Tolerant Networks: Information Propagation Speed Properties[END_REF], the authors introduce a model based on Poisson point process on continuous space, that allows both infinite and finite radio propagation speed, and derive more fine-grained results above and below the threshold. Using the model, the authors prove and explicitly characterize the phase transition. In [START_REF] Wang | The process of information propagation in a traffic stream with a general vehicle headway: A revisit[END_REF], the authors derive equations for the expected value and variance of propagation distance through inter-vehicle communication when the distance between vehicle follows a general distribution.

Studies such as [START_REF] Zhang | On the Information Propagation Process in Multi-lane Vehicular Ad-hoc Networks[END_REF], [START_REF] Zhang | On the Information Propagation Speed in Mobile Vehicular Ad Hoc Networks[END_REF] are the closest related work. In [START_REF] Zhang | On the Information Propagation Speed in Mobile Vehicular Ad Hoc Networks[END_REF], the authors consider a one-dimensional vehicle-tovehicle network with unit-disk radio range where all vehicle travel in the same direction, with random speeds following a Gaussian distribution. The paper derives the impact of various parameters on information propagation speed. The authors extend their results in [START_REF] Zhang | On the Information Propagation Process in Multi-lane Vehicular Ad-hoc Networks[END_REF] to a multi-stream case where vehicles in different streams have different speed distributions and derived analytical formulas. Comparatively, we here consider a model accommodating real time variation of radio ranges for vehicle-to-vehicle communications on multi-lane roads, where vehicles on a particular lane all have the same speed. Since we consider the speed of vehicles only relatively to the speed of vehicles on the fastest lane, our model naturally encompasses both cases of one-way and two-way roads, as well as special cases such as road side units and/or parked cars being used as relays The goal of this paper is to increase our understanding of the fundamental performance limits of mobile vehicle-tovehicle networks with time-varying radio ranges and to thus complement the above-cited works.

In this context, our contributions are as follows: (1) in Section II we present a time-varying radio range model for information propagation in multi-lane vehicle-to-vehicle networks that takes into account real-time radio communication range variations at the MAC layer and list our corresponding results for all cases of number of lanes; (2) we prove that no such phase transition occurs concerning the information propagation speed with respect to the vehicle densities if there is only one lane, regardless of the car densities in Section III, and (3) we prove that a phase transition exists as soon as there is a second lane with different vehicle speed and sufficient density in Section IV; [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF] in Section V, we focus on information propagation speed when there are three lanes or more. We show that under certain conditions a phase transition exists and we derive bounds on the threshold as a simple relationship between the vehicle density on the fastest lane and the sum of the vehicle densities on the other lanes. We also prove that there are still cases where no such phase transition occurs; (5) Finally we validate the provided analysis with simulations in Section VI.

II. MODEL AND RESULTS

We consider a highway with multiple lanes of vehicles at fixed speed, numbered 0 to k: on lane i, the vehicle speed is v i . The vehicle density on lane i is Poisson of intensity λ i . Vehicle speeds are in decreasing order: lane 0 is called the fast lane, determined as the lane of vehicles with the fastest eastbound speed. Lanes from 1 to k are conversely called the slow lanes. In the following, we consider vehicle speeds in the referential of the vehicles of the fast lane. For instance, in Figure 1, we depict an example of a four-lane highway, with two eastbound and two westbound lanes. We number lanes in decreasing eastbound speed: 0. fast eastbound lane, 1. slow eastbound lane, 2. slow westbound lane, and 3. fast westbound lane. We note that, once we have defined the lane numbering, the actual directions of the lane speeds do not matter anymore in our model. Note that this also allows to account for static lanes where cars are parked along the road. As we consider the speeds in the referential of the fast lane, the speed of lane 0 will be 0, and the speeds of the remaining lanes will be negative.

The radio propagation, as well as the store-and-forward time are considered instantaneous. For radio transmissions, we will consider alternatively (i) a fixed radio range, or, more realistically, (ii) a time-varying radio range.

In the former case (i), we will assume that the radio range of each transmission is of length R in each direction.

In the latter case (ii), we suppose that the radio range R varies in time in a random way and is unbounded (i.e., for any distance x, P (R > x) ̸ = 0). We suppose that each vehicle transmits according to a time Poisson process of intensity ν > 0, with a random range R. We assume the following properties concerning the random variable R. Let ζ be a complex quantity with the dimension of inverse distance. For all ζ,

1) f (ζ) = E(e -ζR
) is defined and is not infinite; 2) for all x, E(e -(R-x)ζ |R > x) is defined and bounded by some function g(ζ). The first condition implies that, lim x→∞ e αx P (R > x) = 0, for all α > 0. It is satisfied, e.g., when there exist D > 0 and δ > 1, such that P (R > x) ∼ exp(-Dx δ ). The second condition is satisfied when, for all x, the random variable Rx, under the condition that R > x, is smaller or equal in probability to a certain random variable R, such that E(e -ζ R) is defined; in this case, we can take

g(ζ) = E(e -ζ R).
Assuming such conditions makes sense in relevant contexts, such as slotted Aloha in the Poisson shot noise model [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF]. For example, in a one-dimensional highway network, when the power attenuation is of path-loss exponent 2,

P (R > x) is of the form e -x 2 .
Without loss of generality, we focus on the propagation of information in the eastbound direction. An information packet propagates in the following manner: it moves toward the east jumping from car to car until it stops because the next car is beyond radio range; the information packet waits on the rightmost car until either a transmission of large enough radio range occurs to move forward, or the gap is filled by cars of other lanes (in the case of fixed range, this is the only way for the information to propagate further). We consider the distance L(t), traveled by the information during time t, with respect to the referential of the fast-lane cars. We define the average information propagation speed v p as:

v p = lim t→∞ E(L(t)) t
.

A. Results

The main results presented in this paper are the proofs of the following five theorems, corresponding to various cases of number of lanes: one (Theorem 1), two (Theorems 2 and 3), and three or more lanes (Theorems 4 and 5). For all five theorems, we analyze the asymptotic average information propagation speed v p (without loss of generality, in the referential of the vehicles of the fastest eastbound lane).

For the remainder of the paper, for x > 0, we denote x * the conjugate of x with respect to the function xe -x : x * is the alternate solution of the equation x * e -x * = xe -x . Notice that x * * = x and 1 * = 1.

Theorem 1. In a vehicular network with a single (one-way) lane where the radio range varies, the average asymptotic information propagation speed v p with respect to the referential of the cars is null, regardless of the vehicle density λ 0 .

Theorem 2. Consider a vehicular network with two lanes, where the radio range R varies, with respective car densities λ 0 and λ 1 , and respective speeds v 0 and v 1 . Let a distance r 0 > 0 such that P (R ≥ r 0 ) ̸ = 0. For all 0 < a < 1/2, and for ρ = -log

( 1 -exp(-P (R ≥ r 0 ) νa v0-v1 )
)

, the average asymptotic information propagation speed v p with respect to the referential of the fastest cars is strictly larger than 0, when r 0 λ 0 > 1 1-2a (2ρ + (r 0 λ 1 ) * ). Theorem 3. Consider a vehicular network with two lanes, where the radio range R varies, with respective car densities λ 0 and λ 1 , and respective speeds v 0 and v 1 . There exists ρ 0 > 0, which is a function of (v 0 -v 1 ) and λ 1 , such that, when λ 0 < ρ 0 , the average asymptotic information propagation speed v p with respect to the referential of the fastest cars is null. Theorem 4. Consider a vehicular network with three or more lanes, numbered 0 to k, where the radio range varies. For all 0 < a < 1/2, there exists a distance r 0 > 0 and a scalar ρ > 0, such that the average asymptotic information propagation speed v p with respect to the referential of the fastest cars (lane 0) is strictly larger than 0, when r 0 λ 0 ≥

1 1-2a ( 2ρ + (r 0 ∑ i=k i=1 λ i ) *
) .

Theorem 5. Consider a vehicular network with three or more lanes, numbered 0 to k. There exists a tuple of car densities, such that ∀i: λ i ̸ = 0, for which the average information propagation speed v p is null.

III. SINGLE LANE: PROOF OF THEOREM 1

As the information propagation speed is considered in the referential of the vehicles (say, in eastbound direction), we can equivalently assume that the cars are fixed, and consider the information propagation speed v p toward the east, solely based on the transmissions. We recall that the emission process of the vehicles is a time Poisson process of intensity ν > 0, with a random radio range R.

We call the rightmost car that has received the information at a given time t, the current car at time t. Without loss of generality, we consider that only the current car transmits the information; and, similarly, we can assume that the random radio range process includes the overlap from the ranges of previous cars to the left, if they participate in the transmission.

In the following, we describe a process to provide an upper bound on the information propagation speed vp . If the gap from the current car to the next car to the right is x, then one has to wait that the radio range exceeds x, before the information reaches the next car. When the radio range R exceeds x, all the cars that are located between x and R receive the information. The speed upper-bound process consists in assuming that the next current car is located exactly at the range limit, i.e. at distance R from the previous current car.

Therefore, under the upper bound model, the gaps x between the current cars and the following cars are i.i.d. random exponential variables, with rate λ 0 . Given that the gap is of length x, the time T (x) needed to move the message to the next current car satisfies: E(T (x)) = 1 νP (R>x) , and the distance D(x) traveled by the information at this time satisfies: E(D(x)) = E(R|R > x). Since this is a memoryless process, the average information propagation speed upper-bound vp is:

vp = ∫ ∞ 0 E(D(x))λ 0 e -λ0x dx ∫ ∞ 0 E(T (x))λ 0 e -λ0x dx
.

From the condition lim x→∞ e λ0x P (R > x) = 0, we get

∫ ∞ 0 E(T (x))λ 0 e -λ0x dx = ∞. From the condition E(R|R > x) ≤ x + E( R), we have ∫ ∞ 0 E(D(x))λ 0 e -λ0x dx ≤ 1 λ0 + E( R) < ∞.
Thus, the information propagation speed vp is 0.

IV. TWO LANES

A. Proof of Theorem 2

For the purpose of the proof, we define a lower bound process on the information propagation speed. Let r 0 > 0 be such that P (R ≥ r 0 ) ̸ = 0. We bound the radio range R with a new range R ′ , as follows:

• when R ≥ r 0 , then R ′ = r 0 ; • when R < r 0 , then R ′ = 0. We consider the information propagation on the fast (say eastbound) lane. In the lower bound model, cars must be separated by less than r 0 , in order to be able to communicate. We call r 0 -cluster a set of consecutive cars such that two consecutive cars are separated by distance less than r 0 . We call length of a cluster the distance between the first and the last car of a cluster. A recursive definition of an r 0 -cluster, spreading eastwards from position y, namely C r0 (y), is:

C r0 (y) = I r0 (y) ∪ C r0 (z),
where I r0 (y) is the set of cars located in the segment [y, y + r 0 ], and z is the position of the rightmost car in I r0 (y).

Therefore, if the current car on lane 0 (the fast lane) is separated from the next car on lane 0 by a gap of length r 0 (1 + x), for x > 0, then it needs to wait for a slow lane cluster of length at least r 0 x to bridge the gap.

The number of retransmissions of radio range r 0 , to cover a cluster of length r 0 x, cannot exceed ⌈2x⌉. Let a > 0 be a real number, and assume that the time between two retransmissions is smaller than a r0 v0-v1 . The latter occurs with probability e -ρ = 1 -exp(-P (R ≥ r 0 )νa r0 v0-v1 ), for some ρ > 0 (since, we recall that the node emission process is a Poisson process of intensity ν > 0). This also implies that the cluster of length xr 0 travels a distance smaller than ⌈2x⌉ar 0 . Assuming now that a < 1/2, a cluster of length xr0

1-2a

would suffice to bridge a gap of length r 0 (1 + x), provided that successive retransmissions are all separated by less than a r0 v0-v1 time units (which occurs with probability greater than e -ρ2x/(1-2a) ). From [2, equation (10)], with a lane density normalized by the radio range, we know that the average time to get an r 0 -cluster of length yr 0 is Θ(e (r0λ1) * y ), as expressed in the following lemma.

Lemma 1. The average distance to a car on the slow lane, which begins an r 0 -cluster of slow lane cars of length larger than r 0 x, is Θ(e (r0λ1) * x ), when x → ∞.

The time needed to get an r 0 -cluster of length r 0 y, where all successive retransmissions are separated by less than a r0 v0-v1 time units, is Θ(e (2ρ+(r0λ1) * )y ). Using the methodology in [2, Section III-A, eq. ( 9)], the average distance to such a cluster on the slow lane is Θ(exp

( 2ρ+(r0λ1) * 1-2a x
) ), and thus the time T ′ (x) needed to bridge a gap of length r 0 (1 + x) is:

E(T ′ (x)) = Θ(exp ( 2ρ + (r 0 λ 1 ) * 1 -2a x
)

).

The distance D ′ (x) traveled by the information (in the referential of fast-lane cars) satisfies:

E(D ′ (x)) ≥ r 0 (1 + x).
Therefore, the information propagation speed v p is:

v p ≥ ∫ x 0 E(D ′ (x))λ 0 r 0 e -λ0r0x dx ∫ x 0 E(T ′ (x))λ 0 e -λ0r0x dx ≥ r 0 + 1/λ 0 ∫ x 0 E(T ′ (x))λ 0 r 0 e -λ0r0x dx
.

It turns out that the integral in the denominator converges when r 0 λ 0 > 2ρ+(r0λ1) *

1-2a

and, with this condition, v p > 0.

B. Proof of Theorem 3

See technical report [3, Section 7.1].

V. THREE OR MORE LANES

A. Proof of Theorem 4

We take the framework of the proof of Theorem 2, with r 0 such that P (R > r 0 ) ̸ = 0. We will first consider the case where ν → ∞, i.e., when the channel access delay1 ν tends to 0. In this case, we have ρ = a = 0, and we are in the framework of [START_REF] Baccelli | Highway Vehicular Delay Tolerant Networks: Information Propagation Speed Properties[END_REF] with a unit disk graph model, but with the difference that instead of 1, the range here is r 0 .

To simplify the notation, we denote Λ s = ∑ i=k i=1 λ i . We consider that the information is blocked by a gap of length r 0 (1 + x) on the fast lane. The aim is to give an upper bound of the time needed to have an r 0 -cluster of length at least r 0 x, made of cars on slow lanes, which covers the gap. But, since clusters are not permanent in time, and experience continuous changes due to the differences of car motions, we will consider here instantaneous r 0 -clusters. A recursive definition of an instantaneous r 0 -cluster, spreading eastwards from position y and at time t, namely C r0 (y, t), is:

C r0 (y, t) = I r0 (y, t) ∪ C r0 (z, t),
where I r0 (y, t) is the set of cars located in the segment [y, y + r 0 ] at time t, and z is the position of the rightmost car in I r0 (y, t) at time t. Thus, we use a version of lemma 1 adapted to the case where the cars on slow lanes have relative motions. The following is directly derived from [2, Lemma 2].

Lemma 2. The probability that a given car, at a given time, begins an instantaneous r 0 -cluster, of slow lane cars of length longer than r 0 x, is Θ(e -(r0Λs) * x ), when x → ∞.

The main point now is to track the correlation between cars and time, since cars move relatively to one another. To this end, we consider the process of cluster formation that starts with a car on lane 1, the fastest among the slow lanes. Without loss of generality, we assume that λ 1 ̸ = 0.

We place ourselves in the referential of cars on lane 1. We consider a road segment [A, B) in this referential, for some A < B. Since the cars on the other slow lanes have a relative westbound motion, and since Poisson processes are memoryless, the events in the interval [A, B), at a given time t, and the future events in the interval [B, ∞) are independent.

To make use of this property for instantaneous cluster formations, we split the slowest lane k into segments of length (1 + x)r 0 , numbered from 1 and onwards.

We concentrate on the first segment. Let us consider the first car in lane 1. The probability that this lane 1 car starts a slow lane r 0 -cluster, of length smaller than xr 0 , at the time when this lane 1 car arrives in range of the current car on lane 0, is smaller than 1 -Ce -(r0Λs) * x (with C > 0, as deduced from Lemma 2). Similarly, if we include the probability that no car of lane 1 is present in this segment, (i.e., e -(1+x)r0λ1 ), then the probability that there is no instantaneous r 0 -cluster, starting in the first segment, with a length greater than r 0 x when in range with the current car, is smaller than 1 -C(1e -(1+x)r0λ1 )e -(r0Λs) * x .

Since this event only depends on the car positions in the first and second segments when the first car arrives in range of the current car, this event is independent of what will happen in the next segments. Thus, the occurrences of further r 0 -clusters of length smaller than r 0 x on odd segments are i.i.d. The average number of segments, before the formation of an instantaneous r 0 -cluster of length greater than r 0 x, is smaller than:

∑ n≥0 2(1-(1-e -(1+x)r0λ1 )Ce -(r0Λs) * x ) n = 2 exp((r 0 Λ s ) * x) C(1 -e -r0λ1
) .

Therefore, the time T ′ (x), before the gap of length (1+x)r 0 is bridged by an instantaneous cluster made of slow lane clusters, satisfies the inequality:

E(T ′ (x)) ≤ 2(x + 1)r 0 v 0 -v 1 exp((r 0 Λ s ) * x) (1 -e -r0λ1 )C .
Thus, this average time ∫ ∞ 0 E(T ′ (x))λ 0 r 0 e -xr0λ0 dx is finite as soon as r 0 λ 0 < (r 0 Λ s ) * . This terminates the proof for ν → ∞. Notice again that, in this case, ρ = a = 0.

When ν < ∞, we cannot use the same approach: indeed, in this case, the time between retransmissions does not allow us to work with instantaneous clusters. In this case, we must consider a refined version of Lemma 2, where instantaneous r 0 -clusters are replaced by τ -timed r 0 -clusters, i.e., r 0 -clusters obtained with retransmissions delayed each by τ seconds exactly. A recursive definition of an instantaneous (r 0 , τ )cluster, spreading eastbound from position y and at time t, namely C r0,τ (y, t), is:

C r0,τ (y, t) = I r0 (y, t) ∪ C r0,τ (z, t + τ ),
where z is the position of the rightmost car in I r0 (y) at time t + τ . We have the following lemma, equivalent to lemma 2: Lemma 3. Let τ > 0, the probability that a given car, at a given time, begins an instantaneous τ -timed r 0 -cluster of slow lane cars of length larger than r 0 x is Θ(e -(r0Λs) * x ), when x → ∞.

The end of the proof follows an approach similar to Theorem 2. We define τ = a r0 v0-v1 for some a > 0 small enough, and we consider timed clusters larger than (1 + x)r 0

VI. SIMULATIONS

We present simulation results obtained with the Opportunistic Network Environment (ONE [START_REF] Keranen | The ONE Simulator for DTN Protocol Evaluation[END_REF]) simulator. Vehicles are distributed uniformly on the length of two or more lanes of a road, and move at a constant speed. The total number of vehicles varies from 300 to 4000. We measure the fastest possible information propagation speed using epidemic broadcast, assuming that radio transmissions are instantaneous and that there are no buffering or congestion delays. We vary the vehicle densities λ i (vehicles per radio range), and we perform several simulation iterations of randomly generated traffic.

Figure 2 plots the information propagation speed versus the total vehicle density for three lanes, when λ 0 = λ 1 = λ 2 , with a fixed radio range R = 1. The fast lane speed is 0 (as measured in the referential of the fast cars), the slow lane speeds are 0.4 radio range per second and 0.6 radio range per second. We observe the existence of a threshold near ∑ i=k i=0 λ i = 2 , which confirms the analysis: below the threshold the information propagation speed is null, while above the threshold, it increases rapidly. We then simulate the case of time-varying radio range. We consider that P (R > x) = e -x 2 , corresponding to the Poisson shot noise model of a one dimensional highway, with path-loss exponent 2. Vehicles transmit packets of information with Poisson intensity ν = 5 transmissions per second. Figures 3 and4 plot the information propagation speed versus the total vehicle density (with λ i = λ 0 , for all i, and vehicle speeds as above), for two and three lanes respectively. Again, we notice the existence of a threshold, where a phase transition occurs.

VII. CONCLUSION

In this paper, we provided a detailed analysis of information propagation speed in multi-lane vehicle-to-vehicle networks. We considered both the case of constant radio transmission range, and the more realistic case of time-varying radio transmission range (due to environment versatility and interferences). We have shown the existence of a vehicle density threshold, under which information propagates on average at the speed of the fastest vehicle, and above which information propagates significantly faster. Our model covers scenarios including one-way and two-way roads, and cases where road side units or parked cars are used as relays. Our methodology is also extendable to cases where car speeds may take an infinite number of values within a given speed range, which corresponds to an infinite number of lanes in our model.

Fig. 1 .

 1 Fig. 1. Vehicular network on a bidirectional highway with four lanes.

Fig. 2 .

 2 Fig. 2. 3 lanes, fixed radio range. Information propagation speed vp for λ 0 = λ 1 = λ 2 , versus the total vehicle density.

Fig. 3 .

 3 Fig. 3. 2 lanes, varying radio range (P (R > x) = e -x 2 )). Information propagation speed vp for λ 0 = λ 1 , versus the total vehicle density.

Fig. 4 .

 4 Fig. 4. 3 lanes, varying radio range (P (R > x) = e -x 2 )). Information propagation speed vp for λ 0 = λ 1 = λ 2 , versus the total vehicle density.

1-2a , ensuring they can actually bridge a gap of length (1 + x)r 0 . We then consider (r 0 -ε)-clusters instead of r 0 -clusters, in order to cope with the small local modification of the clusters, since the retransmissions are not exactly after a time τ , but within a time τ (we take ε = τ (v 1 -v k )).

ACKNOWLEDGMENT

The work of G. Rodolakis was supported in part by the EU grants INFLOW (FP7-294236) and STAMINA (FP7-265496).