Yves Mocquard
email: yves.mocquard@irisa.fr

Bruno Sericola
email: bruno.sericola@inria.fr

Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Balanced allocations and global clock in population protocols: An accurate analysis

The context of this paper is the two-choice paradigm which is deeply used in balanced online resource allocation, priority scheduling, load balancing and more recently in population protocols. The model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represent the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded and the one in the least loaded bin. At time t, this difference is denoted by Gap(t). A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all t ≥ 0, n ≥ 2 and σ > 0, the variable Gap(t) is less than a(1 + σ) ln(n) + b with probability greater than 1 -1/n σ , where the constants a and b, which are independent of t, σ and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

Introduction

In this paper we address the important issue of the two-choice paradigm analysis [START_REF] Mitzenmacher | The power of two random choices: A survey of techniques and results[END_REF]. To illustrate the multi-choice paradigm, suppose that we have a set of m balls which are sequentially throws into n bins, where each ball is placed in the least filled bin among d ≥ 1 ones randomly chosen among the n bins. Azar et al. [START_REF] Azar | Balanced allocations (extended abstract)[END_REF] have characterized this problem by those three values (m, n, d). A natural question is the analysis of the maximum load in any of the bins, or the maximal gap that may exist between the least loaded bin and the most loaded one. It has been proven that in the simplest case where d = 1 (see for example [START_REF] Raab | Balls into bins" -a simple and tight analysis[END_REF]), the maximum load is equal to m/n + Θ (m/n) ln n , leading to a gap that increases with the square root of m. Now, instead of choosing a single bin at random, d ≥ 2 bins are independently and randomly chosen, and the least loaded bin one among those d ones receives a ball. Then Azar et al. [START_REF] Azar | Balanced allocations (extended abstract)[END_REF] have shown that when m = n the maximum load is ln(ln(n))/ ln(2) + O(1), and the largest gap is also equal to ln(ln(n))/ ln(2) + O [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF]. These results show that by simply introducing a small choice we get a drastically improved balanced load among all the urns. Citing Mitzenmacher et al [START_REF] Mitzenmacher | The power of two random choices: A survey of techniques and results[END_REF], "having just two random choices (i.e., d = 2) yields a large reduction in the maximum load over having one choice, while each additional choice beyond two decreases the maximum load by just a constant factor". Hence the name of the two-choice paradigm. Later Berenbrink et al. [START_REF] Berenbrink | Balanced allocations: The heavily loaded case[END_REF] have studied the case (m, n, d) for d ≥ 2 and m n, and proved that the maximum load is equal to m/n + O(ln(ln(n))). Note that a simpler proof of this result has been recently found by Talwar and Wieder [START_REF] Talwar | Balanced allocations: A simple proof for the heavily loaded case[END_REF]. Very recently, Peres et al. [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF][START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF], using a measurement based on the hyperbolic cosine, have generalized the problem in the (1 + β)-choice problem. The (1 + β)-choice consists, with probability 1 -β, in choosing one bin uniformly at random and to throw a ball in it, and with probability β, in choosing two bins uniformly at random and to throw a ball in the least loaded one. The name comes from the fact that E{d} = 1 + β. We can note that in their model, each ball is assigned with a random weight. They found a logarithmic bound for both the gap between the maximum loaded bin and the average one [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF], and for the gap between the maximum loaded bin and the minimum one [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. In both cases the gap is

O (log(n)/β).
The two-choice paradigm can be used in a multitude of applications, including balanced online resource allocation (where jobs need to be dynamically allocated to the least loaded processor) [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF][START_REF] Berenbrink | Infinite parallel job allocation (extended abstract)[END_REF][START_REF] Berenbrink | Allocating weighted jobs in parallel[END_REF], priority scheduling [START_REF] Alistarh | The power of choice in priority scheduling[END_REF], load balancing [START_REF] Adler | Parallel randomized load balancing[END_REF][START_REF] Berenbrink | Balanced allocations: The heavily loaded case[END_REF][START_REF] Mitzenmacher | Load balancing and density dependent jump Markov processes[END_REF], and very recently, population protocols [START_REF] Alistarh | Space-optimal majority in population protocols[END_REF]. In the later case, the model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represents the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded and the one in the least loaded bin. At time t, this difference is denoted by Gap(t). A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all t ≥ 0, n ≥ 2 and σ > 0,

P {Gap(t) ≥ a(1 + σ) ln(n) + b} ≤ 1 n σ , (1)
where the constants a and b, which are independent of t, σ and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

The remaining of the paper is structured as follows. In Section 2 we present the addressed problem and a simple algorithm to solve it. Section 3 is the main contribution of our work which consists in providing an accurate bound of the distribution of the gap between any two nodes. Section 4 evaluates constants a and b obtained by our analysis and compares it to constants that we derived from the work of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]. The gain in accuracy we obtained by our analysis is significant. Finally Section 5 provides a summary of simulations results.

Problem description

We consider a very large set of n nodes (also called agents), interconnected by a complete graph, that asynchronously start their execution in a given state. Agents do not maintain nor use identifiers (agents are anonymous and cannot determine whether any two interactions have occurred with the same agents or not). However, for ease of presentation the agents are numbered 1, 2, . . . , n. Each agent keeps a local counter, initialized at 0. Agents communicate through random pairwise interactions. On each interaction, the two interacting agents compare their counters, and the one with the lower counter value increments its local counter. The objective of this simple algorithm is the construction of a global clock by guaranteeing that the values of all agent counters are concentrated according to Relation [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF]. As interactions are uniformly random, this can be related to the classic two choices load balancing process [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. The goal of the paper is to evaluate the gap between any two agents, that is the maximal difference that may exist at any time t between any two local counters, by accurately evaluating constants a and b. By accurately estimating the maximal gap between any two counter nodes, other population protocols can use it as a global clock to perform actions in a probabilistic synchronized way.

We denote by C (i) t the state of agent i at time t. The stochastic process C = {C t , t ≥ 0}, where C t = (C (1) t , . . . , C

(n) t ), represents the vector state of the system at time t.

The choice of the two agents which interact is made using a uniform distribution. Given the pair (i, j) of agents which interact at time t, we consider the following evolution of the agents states

C (i) t+1 , C (j) t+1 =        C (i) t + 1, C (j) t if C (i) t ≤ C (j) t C (i) t , C (j) t + 1 if C (i) t ≥ C (j) t .
Note that in the case where agents i and j interact at time t with

C (i) t = C (j) t
then either of two agents can be chosen to have its value increased by 1 at time t + 1. A particular choice is made below.

The state space of process C is thus N n and a state of this process is also called a protocol configuration. At time 0, we set C (i) t = 0, for every i = 1, . . . , n. At each instant the value of only one agent is increased by 1 which means that we have, for every t ≥ 0,

n i=1 C (i) t = t.
For every i = 1, . . . , n, we introduce the quantities

x i (t) = C (i) t -t/n, which leads, for every t ≥ 0, to n i=1 x i (t) = 0. The value C (i)
t maintained by agent i is its own view of the global clock t of the system divided by n. More precisely, the approximation of time t, provided by agent i, is nC

(i) t .
At each discrete time t ≥ 0, any two indices i and j are uniformly chosen to interact, independently of the vector state with probability 1/(n(n -1)).

In order to simplify the presentation, we suppose without any loss of generality that at each instant t, the values of x i (t) are reordered in a decreasing way, assigning an arbitrary order to agents with the same value. More precisely, at time t the reordering gives

x 1 (t) = max i=1,...,n (C (i) t -t/n) ≥ • • • ≥ x n (t) = min i=1,...,n (C (i) t -t/n).
We denote by X the rank of the agent whose value is incremented when interaction occurs between 2 agents. In the case where two agents interacting, say i and j, are such that

C (i) t = C (j)
t , we choose to increase by 1 the one with the highest rank. If X 1 and X 2 are the ranks of the successive agents which interact, then the probability p that agent of rank is incremented is, for = 1, . . . , n,

p = P{X = } = P{X 1 = , X 2 < } + P{X 1 < , X 2 = } = 2( -1) n(n -1) (2)
As mentioned in the introduction, the goal of the paper is the evaluation of the distribution of difference between the maximum and the minimum of the entries of vector C t . This difference is denoted by Gap(t) and is given, for t ∈ N, by

Gap(t) = max 1≤i≤n C (i) t -min 1≤i≤n C (i) t = x 1 (t) -x n (t).
In order to bound the complementary distribution of Gap(t), we introduce the following potential functions defined, for α ∈ R, by

Φ(t) = n i=1 e αxi(t) , Ψ (t) = n i=1 e -αxi(t) and Γ (t) = Φ(t) + Ψ (t).
The use of these two functions has been proposed in a very clever way by Y. Peres et al. in [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. The potential function Γ (t) is then related to function Gap(t) by the following lemma.

Lemma 1 For every t ≥ 0, we have

Γ (t) ≥ 2e αGap(t)/2 . ( 3
)
Proof. The exponential function being convex, we have, for every a, b ∈ R, 2e (a+b)/2 ≤ e a + e b . Recalling that Gap(t) = x 1 (t) -x n (t), we obtain

Γ (t) = n i=1 e αxi(t) + n i=1
e -αxi(t) ≥ e αx1(t) + e -αxn(t) ≥ 2e αGap(t)/2 , which completes the proof. This result will be used at the end of the paper for the evaluation of the distribution of Gap(t) which is based on the evaluation of the one of Γ (t), which forms the main part of the paper.

Analysis

We first need the two following technical lemmas which are proved in [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

Lemma 2 For all x ∈ R, we have 1+x ≤ e x . For all x ∈ (-∞, c], we have e x ≤ 1 + x + x 2 , where c is the unique positive solution to equation e c -1 -c -c 2 = 0. The value of c satisfies 1.79 < c < 1.8.

Lemma 3 Let u = (u k ) k≥1 and v = (v k ) k≥1
be two monotonic sequences of real numbers and let m n be the sequence of mean values of sequence v defined, for n ≥ 1, by

m n = 1 n n k=1 v k .
If the sequences u and v are both non-decreasing or both non-increasing then we have

n k=1 u k v k ≥ m n n k=1 u k .
If one of these two sequences is non-increasing and the other is non-decreasing then we have

n k=1 u k v k ≤ m n n k=1 u k .
For every t ≥ 0, we introduce the notation x(t) = (x 1 (t), . . . , x n (t)).

Lemma 4 For all α ∈ (-1, 1), we have

E{Φ(t+1)-Φ(t) | x(t)} ≤ α + α 2 1 -2 n n i=1 p i e αxi - α n - α 2 n 2 Φ(t). ( 4
)
Proof. Since the x i (t)'s are ordered, they may change value at each time. We can thus define a permutation on {1, 2, . . . , n} named σ t such that, for every

u = 1, . . . , n, if x i (t) = C (u) t -t/n then x σt(i) (t + 1) = C (u)
t+1 -(t + 1)/n. Suppose that the rank of the agent (say agent u), whose value is incremented at time t, is equal to i. In this case, we have

x σt(i) (t + 1) = C (u) t+1 - t + 1 n = C (u) t + 1 - t + 1 n = C (u) t - t n + 1 + t n - t + 1 n = x i (t) + 1 - 1 n .
This leads, for every i = 1, . . . , n, to x σt(i

) (t + 1) = x i (t) + 1 {X=i} -1 n
, where 1 A is the indicator function of event A. We then get

Φ(t + 1) -Φ(t) = n i=1 e αxi(t+1) -e αxi(t) = n i=1 e αx σ t (i) (t+1) -e αxi(t) = n i=1 e α(1 {X=i} -1/n) -1 e αxi(t) .
Using the fact that e x ≤ 1 + x + x 2 for x ≤ 1, see Lemma 2, we obtain, since

α(1 {X=i} -1/n) ≤ 1, e α(1 {X=i} -1/n) -1 ≤ α(1 {X=i} -1/n) + α 2 (1 {X=i} -1/n) 2 = α(1 {X=i} -1/n) + α 2 1 {X=i} (1 - 2 n ) + 1 n 2 = α + α 2 1 - 2 n 1 {X=i} - α n - α 2 n 2 .
Taking the expectation of Φ(t+1)-Φ(t), given x(t), we obtain since E{1 {X=i} } = p i ,

E{Φ(t + 1) -Φ(t) | x(t)} ≤ n i=1 p i α + α 2 1 - 2 n - α n - α 2 n 2 e αxi = α + α 2 1 - 2 n n i=1 p i e αxi - α n - α 2 n 2 Φ(t),
which completes the proof.

The following relations will be frequently used in the sequel. Since, for i = 1, . . . , n, p i = 2(i -1)/(n(n -1)), we have for all λ ∈ (0, 1) with λn ∈ N,

1 n n i=1 p i = 1 n (5) 1 λn λn i=1 p i = λn -1 n(n -1) ≤ λ n (6) 1 (1 -λ)n n i=λn+1 p i = (1 + λ)n -1 n(n -1) ≥ 1 + λ n (7)
Corollary 5 For all α ∈ (0, 1), we have

E{Φ(t + 1) -Φ(t) | x(t)} ≤ α 2 n 1 - 1 n Φ(t).
Proof. To prove this result, observe that sequence (e αxi ) i is a non-increasing sequence and (p i ) i is an non-decreasing sequence, so using Relation (5) and applying Lemma 3 we obtain

n i=1 p i e αxi(t) ≤ 1 n n i=1 p i n i=1 e αxi(t) = Φ(t) n .
Putting this result in inequality (4), we get

E{Φ(t + 1) -Φ(t) | x(t)} ≤ α + α 2 1 -2 n n i=1 p i e αxi - α n - α 2 n 2 Φ(t) ≤ α n + α 2 n 1 - 2 n - α n - α 2 n 2 Φ(t) = α 2 n 1 - 1 n Φ(t),
which completes the proof.

Lemma 6 For all α ∈ (-1, 1), we have

E{Ψ(t+1)-Ψ(t) | x(t)} ≤ -α + α 2 1 -2 n n i=1 p i e -αxi + α n + α 2 n 2 Ψ (t). ( 8
)
Proof. It suffices to replace α by -α in the proof of Lemma 4.

Corollary 7 For all α ∈ (0, 1), we have

E{Ψ(t + 1) -Ψ (t) | x(t)} ≤ α 2 n 1 - 1 n Ψ (t)
Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

The two previous lemmas, which give a bound of the increase of functions Φ(t) and Ψ (t), will be used to prove Theorem 12. The proof of the results follow the clever ideas of the seminal paper [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF] in which the authors prove that Gap(t) is less than O(ln(n)) with high probability. In [START_REF] Alistarh | The power of choice in priority scheduling[END_REF], Alistarh et al. provide a more rigorous proof from which we have extracted constants associated with this asymptotic behavior. Those constants are given at the end of Section 4. The main original idea of our paper is to parametrize as much as possible the proofs in order to obtain the smallest values of constants a and b used in Relation [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF] which is proved in Theorem 14. The numerical evaluation of these constants, obtained in Section 4, shows that they are remarkably small with respect to the ones of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF].

In the following, we introduce two variable parameters µ, ρ ∈ (0, 1/2) (which are fixed to 1/4 in [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF] and [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]). Since x i 's are non-increasing we have x ρn ≥ x (1-µ)n . Lemmas 8 and 9 deal with the balanced conditions case that is x ρn ≥ 0 ≥ x (1-µ)n . The unbalanced conditions that are the complementary cases x ρn ≥ x (1-µ)n > 0 and 0 > x ρn ≥ x (1-µ)n are considered respectively in Lemmas 10 and 11. Theorem 12 examines systematically each case which lead to recurrence relation for E{Γ(t)}. Theorem 13 uses this recurrence relation to bound E{Γ(t)}.

Finally, Theorem 14 gives a precise lower bound of Γ (t) with high probability.

Lemma 8 Let α, µ ∈ (0, 1) with µn ∈ N and µ > α/(1 + α). If x (1-µ)n (t) ≤ 0 then we have

E{Φ(t + 1) | x(t)} ≤ 1 - α n µ -α(1 -µ) + α(1 -2µ) n Φ(t) + α + α 2 1 - 2 n ≤ 1 - α n [µ -α(1 -µ)] Φ(t) + α + α 2 . (9)
Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

An analogous result is obtained for Ψ (t) in the following lemma.

Lemma 9 Let α, ρ ∈ (0, 1) with ρn ∈ N and ρ > α/(1 -α). If x ρn (t) ≥ 0 then we have

E {Ψ (t + 1) | x(t)} ≤ 1 -α n ρ -α(1 + ρ) + α(1 + 2ρ) n Ψ (t) + αρ(1 + ρ) ≤ 1 - α n [ρ -α(1 + ρ)] Ψ (t) + αρ(1 + ρ). (10)
Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

Lemma 10 Let α, µ ∈ (0, 1/2) with µn ∈ N and µ ∈ (α/(1 + α), (1 -2α)/(1α)), let µ ∈ (0, 1) with µ n ∈ N and µ ∈ (µ/(1-µ), 1/(1+α)) and let γ 1 ∈ (0, 1).

If x (1-µ)n > 0 and E{Φ(t + 1) -Φ(t) | x(t)} ≥ -(1 -µ (α + 1)) αγ 1 n Φ(t)
and Φ(t) ≥ λ 1 Ψ (t) then we have Γ (t) ≤ c 1 n, where

c 1 = 1 + 1 λ 1 C 1 C 1 µλ 1 µ/((1-µ)µ -µ) , C 1 = (1 -µ ) (2 + α) (1 -γ 1 ) (1 -µ (1 + α))
and

λ 1 = 1 -µ -α(2 -µ) 2α .
The condition µ < (1 -2α)/(1 -α) is needed ta assure that constant λ 1 > 0. The value of λ 1 will be used in Theorem 12. The condition µ > µ/(1 -µ) is needed to assure that the power involved in constant c 1 is positive.

Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

Lemma 11 Let α, ρ ∈ (0, 1/2) with ρn ∈ N and ρ ∈ (α/(1 -α), 1/(1 + α)), let ρ ∈ (ρ/(1 -ρ), (1 -2α)/(1 -α)) with ρ n ∈ N and let γ 2 ∈ (0, 1). If x ρn < 0 and E{Ψ(t + 1) -Ψ (t) | x(t)} ≥ -[1 -2α -ρ (1 -α)] αγ 2 n Ψ (t)
and Ψ (t) ≥ λ 2 Φ(t) then we have Γ (t) ≤ c 2 n, where

c 2 = 1 + 1 λ 2 C 2 C 2 ρλ 2 ρ/((1-ρ)ρ -ρ) , C 2 = (1 -ρ ) (2 -2α -ρ (1 -α)) (1 -γ 2 ) (1 -2α -ρ (1 -α))
and

λ 2 = 1 -ρ(1 + α) 2α .
The condition ρ < 1/(1 + α) is needed ta assure that constant λ 2 > 0. The value of λ 2 will be used in Theorem 12. The condition ρ > ρ/(1 -ρ) is needed to assure that the power involved in constant c 2 is positive.

Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

Theorem 12. Let α, µ, ρ ∈ (0, 1/2) with µn, ρn ∈ N, µ ∈ (α/(1 + α), (1 - 2α)/(1 -α)) and ρ ∈ (α/(1 -α), 1/(1 + α)). Let µ ∈ (µ/(1 -µ), 1/(1 + α)) with µ n ∈ N and let ρ ∈ (ρ/(1 -ρ), (1 -2α)/(1 -α)) with ρ n ∈ N. Let γ 1 , γ 2 ∈ (0, 1). We then have E{Γ(t + 1) | x(t)} ≤ 1 -c 4 α n Γ (t) + c 3 ,
where

c 4 = min µ -α(1 -µ), ρ -α(1 + ρ), γ 1 (1 -µ (α + 1)) , α (1 -µ -α(2 -µ)) 1 -µ(1 -α) , γ 2 (1 -2α -ρ (1 -α)) , α (1 -ρ(1 + α)) 1 -ρ(1 -α) + 2α
and

c 3 = max α (1 + α + ρ(1 + ρ)) , α(1 -µ)(2 -µ), (α + c 4 )αc 1 , α + α 2 , (α + c 4 )αc 2 } , in which c 1 = 1 + 1 λ 1 C 1 C 1 µλ 1 µ/((1-µ)µ -µ) , C 1 = (1 -µ ) (2 + α) (1 -γ 1 ) (1 -µ (1 + α)) , c 2 = 1 + 1 λ 2 C 2 C 2 ρλ 2 ρ/((1-ρ)ρ -ρ) , C 2 = (1 -ρ ) (2 -2α -ρ (1 -α)) (1 -γ 2 ) (1 -2α -ρ (1 -α)) , λ 1 = 1 -µ -α(2 -µ) 2α , λ 2 = 1 -ρ(1 + α) 2α .
Proof. See [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF].

We are now able to give a upper bound of the expected value of Γ (t).

Theorem 13. For all t ≥ 0, under the hypothesis of Theorem 12, we have

E{Γ(t)} ≤ c 3 n/(αc 4 ).
Proof. We prove this result by induction. For t = 0, we have Γ (0) = 2n. Moreover, we have

c 3 ≥ α (1 + α + ρ(1 + ρ)) ≥ α and c 4 ≤ µ -α(1 -µ) ≤ µ ≤ 1/2,
which implies that c 3 /(αc 4 ) ≥ 2. We thus have E{Γ(0)} = 2n ≤ c 3 n/(αc 4 ).

Suppose that the result is true for a fixed t ≥ 0. From Theorem 12, we have

E{Γ(t + 1)} = E {E{Γ (t + 1) | x(t)}} ≤ E 1 -c 4 α n Γ (t) + c 3 ≤ 1 -c 4 α n c 3 αc 4 n + c 3 = c 3 αc 4 n.
which completes the proof.

Theorem 14. For all t ≥ 0 and σ > 0, under the hypothesis of Theorem 12, we have

P Gap(t) ≥ 2(1 + σ) α ln (n) + 2 α ln c 3 2αc 4 ≤ 1 n σ
Proof. From Lemma 1 and Theorem 13, we have Γ (t) ≥ 2e αGap(t)/2 and c 3 n αc 4

≥ E{Γ(t)}.

It follows that

2e αGap(t)/2 ≥ n σ c 3 n αc 4 =⇒ Γ (t) ≥ n σ c 3 n αc 4 =⇒ Γ (t) ≥ n σ E{Γ(t)}.
Using Markov inequality, we obtain

P Gap(t) ≥ 2(σ + 1) α ln (n) + 2 α ln c 3 2αc 4 = P 2e αGap(t)/2 ≥ n σ c 3 n αc 4 ≤ P {Γ (t) ≥ n σ E{Γ(t)}} ≤ 1 n σ ,
which completes the proof.

The following corollary shows that at any time, and for any agent, its local counter approximates the global clock with high probability.

Corollary 15 For all t ≥ 0 and σ > 0, under the hypothesis of Theorem 12, we have

P C (i) t - t n < 2(1 + σ) α ln (n) + 2 α ln c 3 2αc 4 , ∀i = 1, . . . , n ≥ 1 - 1 n σ
Proof. By definition, we have

x i = C (i)
t -t/n, and since x n ≤ 0 ≤ x 1 , we have |x i | ≤ x 1 -x n = Gap(t). It follows, from Theorem 14, that

P C (i) t - t n ≥ 2(1 + σ) α ln (n) + 2 α ln c 3 2αc 4 , ∀i = 1, . . . , n ≤ P Gap(t) ≥ 2(1 + σ) α ln (n) + 2 α ln c 3 2αc 4 ≤ 1 n σ
which completes the proof.

Evaluation of the constants

This section is devoted to the evaluation of constants a and b of Relation (1) and, to compare them with the ones that we can derive from the analysis of Alistarh et al. [START_REF] Alistarh | The power of choice in priority scheduling[END_REF].

From Theorem 14, we have

a = 2 α and b = 2 α ln c 3 2αc 4 ,
where c 3 and c 4 are given by Theorem 12. First of all, note that constraints given in Theorem 12 imply the following inequality:

ρ/(1 -ρ) < (1 -2α)/(1 -α), that is, ρ ≤ (1 -2α)/(2 -3α
), which combined with ρ ≥ α/(1 -α), leads to α ≤ (5 -√ 5)/10 ≈ 0.276. For a fixed value of α, we have to determine the values of parameters µ, ρ, µ , ρ , γ 1 , γ 2 that minimize constant b. This is achieved by applying a simple Monte-Carlo algorithm. Figure 1 shows several optimal values of the constants a and b, used in Theorem 14, and computed for several values of α. Let us now evaluate constants a and b obtained in the paper of Alistarh et al. [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]. Note that the goal of their work was not necessarily focused on the optimization of a and b constants. Nevertheless, as we will see, the evaluation of a and b constants is an important motivation of our work. From Relations (1) and (2) of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF] and as β = 1, we get 0 < δ ≤ ε = 1/16 and thus we obtain, for γ > 0 and c ≥ 2,

1 + γ + cα(1 + γ) 2 1 -γ -cα(1 + γ) 2 ≤ 17 16 , which gives, α ≤ 1 33c(1 + γ) 2 - 1 c(1 + γ) 2 ≤ 1 33c(1 + γ) 2 ≤ 1 66
.

Considering the difference between the lower bound and the upper bound of the inequality following [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF], we obtain

exp αB n 3 - 1 1 -λ ≤ 16λC(ε) ε ,
which can also be written as

exp αB (1 -λ)n ≤ 16λC(ε) ε 1/(2-3λ)
.

Using the last inequality obtained in the proof of Lemma 4.8, we get

Γ (t) ≤ 4 + ε ε λnC(ε) exp αB (1 -λ)n ≤ 4 + ε ε λnC(ε) 16λC(ε) ε 1/(2-3λ)
.

Using this result, we obtain from Lemma 4.11, E{Γ(t)} ≤ 4Cn/(αε), where

C = 4 + ε ε λC(ε) 16λC(ε) ε 1/(2-3λ) , C(ε) = (1 + δ)/λ -1 + 3ε 3ε -ε/3 and α = α(1 -γ -cα(1 + γ) 2 ).
Following the same ideas we used to prove Theorem 14, we get

C(ε) = (1 + δ)/λ -1 + 3ε 3ε -ε/3 ≥ 1/λ -1 + 3ε 3ε -ε/3 = 1227 280
which leads to It follows that constants a and b obtained from [START_REF] Alistarh | The power of choice in priority scheduling[END_REF] satisfy a ≥ 132 and b ≥ 17354, which are at least two orders of magnitude larger than the ones we derived (see Figure 1).

C = 4 + ε ε λC(ε) 16λC(ε) ε 1/(2-3λ) ≥ 26585

Simulations

We complete this paper by giving a summary of the experiments we have carried out to illustrate the performances of our protocol. Recall that n is the number of nodes in the system, and T = t/n is the total number of interactions divided by n, which is often called the parallel time. We have conducted two types of experiments, the first one illustrates the expected proportion of nodes Y T (n, k) whose counter is equal to T + k at time nT , for different values of n and k. More precisely, Y T (n, k) is defined by

Y T (n, k) = 1 n n i=1 1 {C (i) nT =T +k} .
We show in Figure 2(a) the expected value of Y T (n, k), for n = 1000 and k = -2, -1, 0, 1, as a function of the parallel time T . These results have been obtained after running 10, 000 independent experiments. Figure 2(a) shows that the expected value of Y T (n, k) seems to converge when T goes to infinity, and this convergence is reached very quickly. Note that for other values of k, proportions of nodes are too close to 0 to be depicted, as shown in Table 1. Table 1 shows the expected proportion of nodes Y T (n, k) whose counter is equal to T + k at time T = 50, for different values of n = 10 3 , 10 4 , 10 5 , 10 6 , 10 7 and k = -13, . . . , 4. These results have been obtained after running 5, 000 independent experiments, for each value of n. The expected value of Y 50 (n, k) seems to be almost independent of n for large values of n.

The second experiment illustrates the gaps (i.e., the maximal, average, and minimal) for different values of the size n of the system. Let B = 2 × 10 9 be the total number of interactions considered. The maximal gap is computed as max 100n≤t≤B Gap(t), the minimal one is given by min 100n≤t≤B Gap(t), and the @ @ @ k n 10

Conclusion

In this article we have gone a step further in the study of the two-choice paradigm by providing an accurate analysis of the gap problem. An important application of this study would be the improvement of leaderless population protocols. Indeed, we have shown in this paper that agents can construct a global clock by guaranteeing that the values of all agent counters are concentrated according to Relation (1), and thus can locally use this global clock to determine the instants at which some specific actions need to be triggered, or the instants from which all the agents of the system have converged to a given state. In the former case, this would allow agents to solve more complex problems by triggering a series of population protocols, whereas in the latter case this would allow agents to determine the instant from which all the agents have successfully computed a given feature of the population. The construction of efficient leaderless population protocols inspired from this orchestration is left for future work.

α 0 .Fig. 1 .

 01 Fig. 1. Optimal values of a and b in function of α

  Since α ≤ 1/66, we have a ≥ 132. Moreover, since 0 ≤ δ ≤ ε = 1/16, λ = 2/3 -1/54 = 35/54, γ > 0 and c ≥ 2, we obtain

144 6544 9 18 .

 18 Regarding α, we have α = α(1 -γ -cα(1 + γ) 2 ) ≤ α ≤ 1/66. Therefore, we have

  Expected proportion YT (n, k) of nodes as a function of parallel time T , for n = 1000, and k = -2, -1, 0, 1, from bottom to the top.

  Minimum, average and maximum gap as a function of n.

Fig. 2 .

 2 Fig. 2. Expected proportion and gap

Figure 2 (

 2 Figure 2(b) shows respectively the minimal, average and maximal gap in a system of size n over the interval [100n, B] of interactions. As one may expect, the logarithmic progression of the Gap is clearly shown.

Table 1 .

 1 Expectation of Y 50 (n, k) from number of nodes n and shift k

		3	10 4	10 5		10 6	10 7
	-13	0.0	0.0	0.0		1.4E-9	1.42E-9
	-12	0.0	2.0E-8	8.0E-9		9.0E-9	6.14E-9
	-11	2.0E-7	4.0E-8	2.2E-8		2.8E-8	3.048E-8
	-10	2.0E-7	8.0E-8	1.88E-7 1.436E-7 1.4814E-7
	-9	4.0E-7	8.0E-7	7.7E-7	7.438E-7 7.2784E-7
	-8	3.0E-6	3.6E-6 3.586E-6 3.48E-6 3.6029E-6
	-7	1.42E-5	1.8E-5 1.8222E-5 1.7767E-5 1.7758E-5
	-6	8.98E-5 8.602E-5 8.7176E-5 8.7372E-5 8.72753E-5
	-5 4.372E-4 4.2706E-4 4.2957E-4 4.2901E-4 4.29349E-4
	-4 0.0021144 0.0021023 0.0021071 0.0021092 0.0021086
	-3 0.0102474 0.0102890 0.0102777 0.0102800 0.0102810
	-2 0.0481626 0.0483366 0.0483382 0.0483465 0.0483437
	-1 0.1930704 0.1932864 0.1933165 0.1933143 0.1933182
	0 0.4389352 0.4380932 0.4380715 0.4380374 0.4380346
	1 0.2824746 0.2827344 0.2826797 0.2827057 0.2827070
	2 0.0243744 0.0245499 0.0245973 0.0245953 0.0245949
	3	7.6E-5 7.224E-5 7.2248E-5 7.27752E-5 7.27974E-5
	4	0.0	0.0	0.0		4.0E-10	3.6E-10
	average gap is given by
			1 B -100n	B-1 t=100n	Gap(t).

This work was partially funded by the French ANR project SocioPlug (ANR-13-INFR-0003), and by the DeSceNt project granted by the Labex CominLabs excellence laboratory (ANR-10-LABX-07-01)