# Average-based Population Protocols : Explicit and Tight Bounds of the Convergence Time

Yves Mocquard, Frédérique Robin, Bruno Sericola, Emmanuelle Anceaume

► To cite this version:

Yves Mocquard, Frédérique Robin, Bruno Sericola, Emmanuelle Anceaume. Average-based Population Protocols: Explicit and Tight Bounds of the Convergence Time. [Research Report] Irisa. 2019. hal-02178618

HAL Id: hal-02178618

https://hal.science/hal-02178618

Submitted on 10 Jul 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Average-based Population Protocols : Explicit and Tight Bounds of the Convergence Time

YVES MOCQUARD, Univ. Rennes, CNRS, INRIA, IRISA

FRÉDÉRIQUE ROBIN, Inria, Université Paris-Saclay - LMS, Ecole Polytechnique, CNRS, Université Paris-Saclay

BRUNO SERICOLA, Inria, Univ. Rennes, CNRS, IRISA

EMMANUELLE ANCEAUME, CNRS, Univ. Rennes, Inria, IRISA

The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. Among the different problems addressed in this model, average-based problems have been studied for the last few years. In these problems, agents start independently from each other with an initial integer state, and at each interaction with another agent, keep the average of their states as their new state. In this paper, using a well chosen stochastic coupling, we considerably improve upon existing results by providing explicit and tight bounds of the time required to converge to the solution of these problems. We apply these general results to the proportion problem, which consists for each agent to compute the proportion of agents that initially started in one predetermined state, and to the counting population size problem, which aims at estimating the size of the system. Both protocols are uniform, i.e., each agent's local algorithm for computing the outputs, given the inputs, does not require the knowledge of the number of agents. Numerical simulations illustrate our bounds of the convergence time, and show that these bounds are tight in the sense that among extensive simulations, numerous ones exactly fit with our bounds.

CCS Concepts: • Mathematics of computing → Probabilistic algorithms.

Additional Key Words and Phrases:

**ACM Reference Format:**

Yves Mocquard, Frédérique Robin, Bruno Sericola, and Emmanuelle Anceaume. 2019. Average-based Population Protocols: Explicit and Tight Bounds of the Convergence Time. 1, 1 (July 2019), 26 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

Authors' addresses: Yves Mocquard, yves.mocquard@irisa.fr, Univ. Rennes, CNRS, INRIA, IRISA, Campus de beaulieu, Rennes, France; Frédérique Robin, frederique.robin@inria.fr, Inria, Université Paris-Saclay - LMS, Ecole Polytechnique, CNRS, Université Paris-Saclay, 1 Rue Honoré d'Estienne d'Orves, Palaiseau, France; Bruno Sericola, bruno.sericola@inria.fr, Inria, Univ. Rennes, CNRS, IRISA, Campus de beaulieu, Rennes, France; Emmanuelle Anceaume, emmanuelle.anceaume@irisa.fr, CNRS, Univ. Rennes, Inria, IRISA, Campus de beaulieu, Rennes, France.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

© 2019 Association for Computing Machinery.

XXXX-XXXX/2019/7-ART $15.00

https://doi.org/10.1145/nnnnnnn.nnnnnnn
# 1 INTRODUCTION

This paper focuses on the deep analysis of average-based problems in the population protocol model, a model in which agents are identically programmed, with no identity, and progress in their computation through random pairwise interactions. A considerable amount of work has been done so far to determine which properties can emerge from pairwise interactions between finite-state agents, together with the derivation of bounds on the time and space needed to reach such properties (e.g., [3, 7, 16, 18, 25]).

In this work, we are primarily interested in problems that aim at precisely quantifying properties on the system population. Specifically, assuming that each agent starts independently of each other in one of two input states, say A and B, we are interested in determining the exact number of interactions that allows each agent to locally estimate with any high probability the proportion of agents that started in state A, and in estimating the population size. Both problems can be solved by relying on average-based population protocols. We denote by $n$, $n_A$ and $n_B$ the total number of agents, the number of agents which start in state A and the number of agents which start in state B, respectively. Briefly, the $n$ agents start independently from each other with an initial integer state, interact randomly by pairs, and at each interaction, keep the average of both states as their new state. As usual, the time unit is discrete and corresponds to an interaction.

*State of the art.* In 2004, Angluin et al. [4, 5] have formalized the population protocol model, and have shown how to express and compute predicates in this model. Then in [6] the authors have completely characterized the computational power of the model by establishing the equivalence between predicates computable in the population model and those that can be defined in the Presburger arithmetic. Since then, there has been a lot of work on population protocols including the majority problem [3, 7, 16, 18, 25], the leader election problem [10, 19], in presence of faults [14], and on variants of the model [13, 17].

Draief and Vojnovic [16] and Mertzios et al. [18] propose a four-state protocol that solves the majority problem with a parallel convergence time logarithmic in $n$ but only in expectation. Moreover, the expected convergence time is infinite when $n_A$ and $n_B$ are close to each other. Angluin et al. [7] and Perron et al. [25] propose a three-state protocol that converges with high probability after a parallel convergence time logarithmic in $n$ but only if $|n_A - n_B| \ge \sqrt{n} \ln n$.

Regarding the majority problem, Alistarh et al. [3] present a solution based on an average-and-conquer method to exactly solve the majority problem. While their convergence time analysis needs to assume a large number of states, in practice, their algorithm does not require more than $n$ states to converge to the majority. Bilke et al. [12] propose a majority-based protocol that converges in $O(\log^2 n)$ parallel steps and requires $O(\log^2 n)$ states. Their protocol consists in a series of cycles, each cycle comprising two phases. Orchestration of the phases relies on a local logical clock whose evolution is based on the 1-choice strategy. By following the same design principles, Alistarh et al. [2] improve upon Bilke et al. [12] solution by relying on the 2-choice strategy to maintain the logical clock which guarantees that $O(\log n)$ states are sufficient to converge in $O(\log^2 n)$ parallel steps. Berenbrick et al. [11] continue to improve upon the performance of this type of protocol by decreasing the time allocated to each cycle (i.e., $O(\log^{2/3} n)$ parallel steps instead of $O(\log n)$ ones) which allows their solution to converge in $O(\log^{5/3} n)$ parallel steps.

Focusing on the proportion problem, Mocquard et al. [23] provide optimal bounds in terms of order complexity (i.e. in big O notation) on the time it takes for each agent of the system to solve the proportion
problem in the general case, and explicit and tight bounds under some restrictive assumptions. The
present paper extends [23] by removing those assumptions.

Regarding the estimation of the population size, Alistarh et al. [1] propose a protocol that in $O(\log n)$
expected time and states converges to an approximation of the true size $n$. This is achieved by computing
an integer $k$ such that with high probability $\sqrt{n} \le 2^k \le n^9$. Doty and Eftekhari [15] improve this result
by estimating the population size to within a constant multiplicative factor, i.e. $|k - \log n| \le 5.7$ but use
$O(\log^2 n)$ parallel time to converge and $O(\log^6 n)$ states.

*Our contributions.* The objective of the present paper is to improve upon previous results, and in particular results of [23] by removing some restrictive hypotheses made in the analysis of the convergence time of average-based protocols. Indeed, in [23] tight bounds on the convergence time of those protocols were obtained assuming that the fractional part of the mean value $\ell$ of the sum of all the initial states of all the agents is equal to $1/2$. In the present paper, we generalize this analysis to all values of this fractional part, i.e., $\ell - \lfloor \ell \rfloor \in [0, 1)$.

Specifically, our analysis is based on an original approach consisting in associating with the stochastic
process $C = \{C_t, t \ge 0\}$ representing the evolution of the global state of the protocol, a shadow
stochastic process $D = \{D_t, t \ge 0\}$ whose initial state is the same as the one of $C$ except for a fixed
number $b$ of agents whose initial state values are incremented by 1. We prove in Lemma 5.4, that under
the same interactions, $D$ follows the same evolution as $C$ (remains in the shadow of $C$), i.e., $D_t$ and
$C_t$ are equal except for $b$ agents whose state values are incremented by 1. The number $b$ of agents is
chosen so that $D$ satisfies the same hypotheses as those stated in Theorem 5.3. We extend the results of
Theorem 5.3 to give rise to Theorem 5.6 which does not require any restrictive hypotheses.

Note that in all our works, we always exhibit the constants arising in the complexity of our solutions.
This is extremely important in the case where these complexities are in $O(\log n)$ because the logarithm
function increases with $n$ so slowly that even small constants rend the value of $\ln n$ meaningless with
respect to these constants even for large values of $n$.

Hence, we show that after no more than $(n-1)(2\ln(K + \sqrt{n}) - \ln \delta - \ln 2)$ total interactions, where $K$ is a parameter that depends explicitly on the initial configuration of the system, with any predefined probability $1 - \delta$, the difference between any two agents' states is less than or equal to 2, and any agent's state is no more than $3/2$ away from the mean value of the states of the agents.

We then apply those results to the proportion problem, which consists for each agent to compute
the proportion $\gamma$ of agents that initially started in one predetermined state. We show that after no
more than $(n-1)(\ln n - \ln \delta + 2\ln(2+1/\epsilon) + \ln(9/32))$ total interactions, and by using $\lceil 3/(2\epsilon) \rceil$ states,
with $\epsilon \in (0, 1)$, at any agent $i$ the difference between $i$'s approximation of the proportion and the exact
proportion is less than $\epsilon$ with any high probability $1 - \delta$.

We then solve the system size problem which aims at approximating the size $n$ of the system
population. We prove that each agent is able to determine either the exact value of the number $n$
of nodes or an approximation of this number, depending on the initial input value $m$. Suppose that
the designer knows an upper bound $N$ of the number $n$ of agents. By taking $m = 3N(N+1)$, each
agent $i$ possesses the exact value of $n$ with probability at least $1 - \delta$ and after a parallel time equal to
$2\ln m - \ln \delta$. Suppose now that the designer under estimates the value $N$, which should have been an
upper bound of $n$. We have thus $n > N$. If $n \le 9(\ln^2 2)N^2(N+1)^2/4$, then by taking $m = 3N(N+1)$ we
have $m^2 \ge 4n/\ln^2 2$. In that case each agent $i$ possesses an approximated value of $n$ with probability at
least $1 - \delta$ and after a parallel time equal to $2 \ln m - \ln \delta$. The value of this approximation lies within lower and upper bounds computed by each agent $i$.

Numerical simulations illustrate our bounds of the convergence time, and show that these bounds are tight in the sense that among extensive simulations, numerous ones exactly fit with our bounds.

The remaining of the paper is orchestrated as follows. Section 2 presents the problem addressed in the population protocol model, whose formalization in terms of states, interactions and output functions is recalled in Section 3. Section 4 defines the interaction function (i.e. the protocol) applied by the agents when they randomly meet each other. Analysis of the protocol, whose main contribution is the use of shadow process, is presented in Section 5. In Section 6, we apply our results to both the proportion problem and the counting population size. The accuracy of our analytic study has been illustrated through numerous simulations whose main results are presented in Section 7. Finally Section 8 concludes the paper.

## 2 THE ADDRESSED PROBLEMS

We consider a set of $n$ agents, interconnected by a complete graph, that asynchronously start their execution in one of two distinct states $A$ and $B$. Recall that $n_A$ (resp. $n_B$) is the number of agents whose initial state is $A$ (resp. $B$).

*Proportion problem.* A population protocol ran by all the nodes of the system solves the proportion problem in $\tau$ steps with probability at least $1 - \delta$, for any $\delta \in (0, 1)$, if for any $t \ge \tau$, any node of the system is capable of computing the ratio $n_A/n$ with any precision $\varepsilon \in (0, 1)$, without the knowledge of the population size $n$.

*System size problem.* A population protocol ran by all the nodes of the system solves the system size problem in $\tau$ steps with probability at least $1 - \delta$, for any $\delta \in (0, 1)$, if for any $t \ge \tau$, any node of the system is capable of computing a lower bound $\omega_{min}$ and an upper bound $\omega_{max}$ of $n$.

## 3 MODEL

In this section, we present the population protocol model, introduced by Angluin et al. [5]. This model describes the behavior of a collection of agents that interact pairwise. The following definition is from Angluin et al. [8]. A population protocol is characterized by a 6-tuple $(Q, \Sigma, \Xi, t, \omega, f)$, over a complete interaction graph linking the set of $n$ agents, where $Q$ is a finite set of states, $\Sigma$ is a finite set of input symbols, $\Xi$ is a finite set of output symbols, $t: \Sigma \to Q$ is the input function that determines the initial state of an agent, $\omega: Q \to \Xi$ is the output function that determines the output symbol of an agent, and $f: Q \times Q \to Q \times Q$ is the transition function that describes how two agents interact and update their states. Initially all the agents start with an initial symbol from $\Sigma$, and update, upon pairwise interactions, their state according to the transition function $f$. Interactions between agents are orchestrated by a random scheduler: at each discrete time, any two agents are randomly chosen to interact with a given distribution. Note that it is assumed that the random scheduler is fair, which means that the interactions distribution is such that any possible interaction cannot be avoided forever.

The notion of time in population protocols refers to as the successive steps at which interactions occur, while the parallel time refers to as the mean number of steps each agent executes. The parallel time is thus essentially the time divided by the number $n$ of agents [9]. 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.

In this paper, we denote by $C_t^{(i)}$ the state of agent $i$ at time $t$. The stochastic process $C = \{C_t, t \ge 0\}$, where $C_t = (C_t^{(1)}, \dots, C_t^{(n)})$, represents the evolution of the population protocol. The state space of $C$ is thus $Q^n$ and a state of this process is also called a protocol configuration. We denote by $X_t$ the random pair of distinct nodes chosen at time $t$ to interact, and for every $i, j = 1, \dots, n$, with $i \neq j$, we define

$$p_{i,j}(t) = \mathbb{P}\{X_t = (i, j)\}.$$

We suppose that the sequence $\{X_t, t \ge 0\}$ is a sequence of independent and identically distributed random variables. Since $C_t$ is entirely determined by the values of $C_0, X_0, X_1, \dots, X_{t-1}$, this means in particular that the random variables $X_t$ and $C_t$ are independent and that the stochastic process $C = \{C_t, t \ge 0\}$ is a discrete-time homogeneous Markov chain. Classically, we suppose that $X_t$ is uniformly distributed, that is,

$$p_{i,j}(t) = \frac{1_{\{i \neq j\}}}{n(n-1)},$$

where $1_A$ denotes the indicator function, which is equal to 1 if condition A is true and 0 otherwise.

# 4 AVERAGE-BASED POPULATION PROTOCOLS

Average-based population protocols use the average technique to compute for instance the proportion of agents that started their execution in a given state A. This section describes the rules applied during the interactions. At each discrete instant $t$, two distinct indices $i$ and $j$ are chosen among $1, \dots, n$ with probability $1/(n(n-1))$. Once chosen, the couple $(i, j)$ interacts, and both agents update their respective local state $C_t^{(i)}$ and $C_t^{(j)}$ by applying the transition function $f$, leading to state $C_{t+1}$, given by $f(C_t^{(i)}, C_t^{(j)}) = (C_{t+1}^{(i)}, C_{t+1}^{(j)})$ with

$$\begin{gathered} (C_{t+1}^{(i)}, C_{t+1}^{(j)}) = \left( \left\lfloor \frac{C_t^{(i)} + C_t^{(j)}}{2} \right\rfloor, \left\lfloor \frac{C_t^{(i)} + C_t^{(j)}}{2} \right\rfloor \right) \quad (1) \\ \text{and } C_{t+1}^{(r)} = C_t^{(r)} \text{ for } r \neq i, j. \end{gathered}$$

Section 5 is devoted to the study of the bounds of the convergence time of average-based protocols. This analysis will be applied in Section 6 to both the proportion problem and the size counting one.

# 5 ANALYSIS OF THE CONVERGENCE TIME OF AVERAGE-BASED PROTOCOLS

## 5.1 Notations

We will use in the sequel the Euclidean norm denoted simply by $||.||$ and the infinite norm denoted by $||.||_\infty$ and defined for all $x = (x_1, \dots, x_n) \in \mathbb{R}^n$ by

$$\|x\| = \left( \sum_{i=1}^{n} x_i^2 \right)^{1/2} \quad \text{and} \quad \|x\|_{\infty} = \max_{i=1, \dots, n} |x_i|.$$
## 5.2 Preliminaries

We recall the following well-known invariant result on average-based population protocols (see [22]).

**LEMMA 5.1.** For every $t \ge 0$, we have

$$ \sum_{i=1}^{n} C_{t}^{(i)} = \sum_{i=1}^{n} C_{0}^{(i)}. $$

**PROOF.** Using that for all integers $k, k = \lfloor k/2 \rfloor + \lceil k/2 \rceil$, we deduce that the transformation from $C_t$ to $C_{t+1}$ described in Relation (1) does not change the sum of the entries of $C_{t+1}$. $\square$

We denote by $\ell$ the mean value of the sum of the entries of $C_t$ and by $L$ the row vector of $\mathbb{R}^n$ with all its entries equal to $\ell$, that is

$$ \ell := \frac{1}{n} \sum_{i=1}^{n} C_{t}^{(i)} \quad \text{and} \quad L := (\ell, \dots, \ell). \qquad (2) $$

The Markov chain $C$, ruled by the transition function $f$ defined by Relation (1), approaches vector $L$ in the sense that the random vector $C_t$ converges in probability towards vector $L$ when $t$ goes to infinity [24]. Remark that $C$ has a finite state space composed of a set of transient vector states and an absorbing class of vector states whose entries are equal to $\lfloor \ell \rfloor$ or $\lceil \ell \rceil$. This absorbing class is reduced to a single absorbing state when $\ell$ is an integer.

## 5.3 General Results

We first show that the expected value $\mathbb{E}(\|C_t - L\|^2)$ is bounded by an affine recurrence relation.

**THEOREM 5.2.** For every $t \ge 0$, we have

$$ \mathbb{E} (\|C_t - L\|^2) \le \left(1 - \frac{1}{n-1}\right)^t \mathbb{E} (\|C_0 - L\|^2) + \frac{n}{4} - \frac{1}{4n} \quad (3) $$

**PROOF.** The proof is based on a finer evaluation of the difference $\|C_{t+1} - L\|^2 - \|C_t - L\|^2$ than the one proposed in [23]. For sake of completeness we detail the proof in Appendix A.1. $\square$

## 5.4 A First Bound on the Convergence Time

We introduce $\lambda$, the distance between $\ell$ and its nearest integer, that is

$$ \lambda := \min \{\ell - \lfloor \ell \rfloor, \lceil \ell \rceil - \ell\} = \min \{\ell - \lfloor \ell \rfloor, 1 - (\ell - \lfloor \ell \rfloor)\}. $$

It is easily checked that we have $0 \le \lambda \le 1/2$.

In Theorem 4 of [23] or Theorem 5.2.8 of [20], we dealt with the case where $\lambda$ is equal to $1/2$. In the following, we extend the results obtained in [23] or in [20] first to the case where $\lambda = (n - 1_{\{n \text{ odd}\}}) / (2n)$ (see Theorem 5.3) and then, for all $\lambda \in [0, 1/2]$ (see Section 5.5).

**THEOREM 5.3.** For all $\delta \in (0, 1)$, if $\lambda = (n - 1_{\{n \text{ odd}\}}) / (2n)$ and if there exists a constant $K$ such that $\|C_0 - L\| \le K$ then, for every $t \ge (n-1)(2 \ln K - \ln \delta - \ln 2)$, we have

$$ \mathbb{P} \left\{ \|C_t - L\|_{\infty} > \frac{n + 1_{\{n \text{ odd}\}}}{2n} \right\} = \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \right\} \le \delta $$
or equivalently,

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} = \min_{1 \le i \le n} C_t^{(i)} + 1 \right\} \ge 1 - \delta. $$

PROOF. The proof is detailed in Appendix A.2. It uses Theorem 5.2 combined with the Markov inequality. □

Note that $\max_{1 \le i \le n} C_t^{(i)} = \min_{1 \le i \le n} C_t^{(i)} + 1$ implies that $\min_{1 \le i \le n} C_t^{(i)} = \lfloor \ell \rfloor$ and $\max_{1 \le i \le n} C_t^{(i)} = \lceil \ell \rceil$. Hence, Theorem 5.3 assures us that if $\lambda$ is equal to $(n - 1)_{\{n \text{ odd}\}} / (2n)$, then the protocol converges in $O(n \ln K)$ (or $O(\ln K)$ in parallel time) with any high probability towards a class of absorbing vector states which entries are equal to either $\lfloor \ell \rfloor$ or $\lceil \ell \rceil$.

## 5.5 The shadow process and the average-based protocols theorem

We introduce in this section what we call a shadow process of the stochastic process $C = \{C_t, t \ge 0\}$. This shadow process is a stochastic process denoted by $D = \{D_t, t \ge 0\}$ and defined at time $t = 0$ by

$$ D_0^{(i)} = C_0^{(i)} + 1_{\{i \in B_0\}}, $$

where $B_0$ is a non empty subset of $b$ agents with $b \le n - 1$, i.e. $B_0 \subset \{1, \dots, n\}$ and $|B_0| = b$.

For every $t \ge 1$, the shadow process $D_t$ is defined as process $C_t$, that is, when the couple $(i, j)$ is chosen to interact at time $t$ (i.e. when $X_t = (i, j)$), the vector $D_{t+1}$ is given by

$$ (D_{t+1}^{(i)}, D_{t+1}^{(j)}) = \left( \left\lfloor \frac{D_t^{(i)} + D_t^{(j)}}{2} \right\rfloor, \left\lfloor \frac{D_t^{(i)} + D_t^{(j)}}{2} \right\rfloor \right) \text{ and } D_{t+1}^{(r)} = D_t^{(r)} \text{ for } r \ne i, j. $$

In other words, processes $C_t$ and $D_t$ are coupled by process $X_t$: they behave identically in the sense that at each time, the same two nodes are chosen for the interaction. The only difference lies in their initial values. Note that process $C$ is a part of the protocol but not process $D$ which is introduced only for the probabilistic analysis of $C$. Lemma 5.4 shows that if at time $t = 0$ $D_0$ is “in the shadow” of $C_0$ then for any time $t \ge 0$, $D_t$ remains “in the shadow” of $C_t$.

LEMMA 5.4. For all $t \ge 0$, there exists a non empty set $B_t$ of $b$ agents, i.e. $B_t \subset \{1, \dots, n\}$ and $|B_t| = b$, such that for all $i \in \{1, 2, \dots, n\}$, we have

$$ D_t^{(i)} = C_t^{(i)} + 1_{\{i \in B_t\}}, \quad (4) $$

The proof appears in Appendix A.3. As we did for process $C$, we denote by $\ell_D$ the mean value of the sum of the entries of $D_t$ and by $L_D$ the row vector of $\mathbb{R}^n$ with all its entries equal to $\ell_D$, that is

$$ \ell_D := \frac{1}{n} \sum_{i=1}^{n} D_t^{(i)} \text{ and } L_D := (\ell_D, \dots, \ell_D). $$

We use the shadow process to extend the results of Theorem 5.3 to the case of any $\lambda$ value. We show that for any process $C$ associated with any initial condition $C_0$, we can construct a shadow process $D$ verifying the condition of Theorem 5.3, i.e. $\lambda_D = \min \left( \frac{n-1_{\{n \text{ odd}\}}}{2n}, 1 - \left( \frac{n-1_{\{n \text{ odd}\}}}{2n} \right) \right) = \frac{n-1_{\{n \text{ odd}\}}}{2n}$.

LEMMA 5.5. For any process $C$, there exists a shadow process $D$ of parameter $b$ such that $\ell_D - \lfloor \ell_D \rfloor = \frac{n-1_{\{n \text{ odd}\}}}{2n}$. Specifically, let $d \ge 0$ be the smallest integer such that $n$ divides $\sum_{i=1}^n C_0^{(i)} + d$. Then
• If $0 \le d < n/2$, then $b = d + \frac{n-1}{2}$,

• If $n/2 \le d < n$, then $b = d - \frac{n+1}{2}$.

The proof is detailed in Appendix A.3. The shadow process $D$, associated with process $C$, is thus constructed from the rest of the Euclidean division of $n\ell$ by $n$. Taking the complement of this rest to $n$, we deduce the value of parameter $b$ of the shadow process $D$.

**THEOREM 5.6.** For all $\delta \in (0, 1)$, if there exists a constant $K$ such that $\|C_0 - L\| \le K$, then, for all $t \ge (n-1)(2\ln(K+\sqrt{n}) - \ln\delta - \ln 2)$, we have

$$ \mathbb{P} \left\{ \|C_t - L\|_{\infty} \ge \frac{3}{2} \right\} \le \delta. \qquad (5) $$

**PROOF.** Applying Lemma 5.5, we construct a shadow process $D_t$ from a process $C_t$ such that $\lambda_D = (n-1\{n \text{ odd}\})/(2n)$. We conclude by applying Theorem 5.3 to the shadow process so constructed (see details in Appendix A.3). □

Theorem 5.6 thus extends the results of Theorem 6 of [23] to the case of any $\lambda$ value. For any $\lambda$ value, process $C_t$ belongs to the open ball of radius $3/2$ and center $L$, with any high probability in the infinite norm, after no more than $O(n \ln(K+\sqrt{n}))$ time or $O(\ln(K+\sqrt{n}))$ parallel time (Relation (5)).

**COROLLARY 5.7.** For all $\delta \in (0, 1)$, if there exists a constant $K$ such that $\|C_0 - L\| \le K$, then for all $t \ge (n-1)(2\ln(K+\sqrt{n}) - \ln\delta - \ln 2)$,

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 2 \right\} \le \delta \qquad (6) $$

**PROOF.** Using that $\max_{1 \le i \le n} C_t^{(i)} \ge \ell \ge \min_{1 \le i \le n} C_t^{(i)}$, we have that if $\|C_t - L\|_{\infty} < 3/2$, then

$$ \max_{1 \le i \le n} C_t^{(i)} - \ell < 3/2 \text{ and } \ell - \min_{1 \le i \le n} C_t^{(i)} < 3/2 \implies \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} \le 2. $$

Hence, $\mathbb{P}\{\|C_t - L\|_{\infty} < 3/2\} \le \mathbb{P}\{\max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} \le 2\}$. We conclude applying Theorem 5.6. □

# 6 APPLICATIONS

We recall that a population protocol is defined by a 6-tuple $(\Sigma, Q, \Xi, \iota, \omega, f)$, where the set of states is $Q = \{0, 1, \dots, m\}$ and the transition function $f$ is defined by Relation (1) (see Sections 3 and 4). In the averaged-based protocols context, we have $\Sigma = \{A, B\}$, and the input function $\iota$ verifies: $\iota(A) = m$ and $\iota(B) = 0$, where $m$ is a positive integer. Thus, only the set of output symbols $\Xi$, the output function $\omega$ and the integer value $m$ are application dependent. We recall that $n_A$ is the number of nodes starting in state A. Note that we have

$$ \|C_0 - L\|^2 = n_A \left(m - \frac{n_A m}{n}\right)^2 + (n - n_A) \left(\frac{n_A m}{n}\right)^2 = m^2 n_A \left(1 - \frac{n_A}{n}\right). \qquad (7) $$
## 6.1 Solving the Proportion Problem

For solving the proportion problem defined in Section 2, we denote by $\gamma_A$ the proportion of nodes starting with A, i.e. $\gamma_A = n_A/n$. We thus have $\ell = mn_A/n = \gamma_A m$ which also gives $\gamma_A = \ell/m$.

Relation (7) gives a function of $n_A$ which reaches its maximum for $n_A = n/2$. At that value we obtain $\|C_0 - L\|^2 \le m^2n/4$, that is

$$ \|C_0 - L\| \le \frac{m\sqrt{n}}{2}. \qquad (8) $$

In order to clarify the notation and since we are interested in computing the proportion $\gamma_A$ of nodes which started with value A, we add subscript A to the output function $\omega$ applied on the current state $x$ of any agent. We take, for every $x \in Q$,

$$ \omega_A(x) = x/m. $$

The set of output symbols is thus $\Xi = \{0, 1/m, \dots, (m-1)/m, 1\}$. The following theorem gives an evaluation of the first instant $t$ from which the distance between $C_t^{(i)}/m$ and $\gamma_A$, for all the nodes, is less than a fixed $\varepsilon$ with any high probability $1 - \delta$.

**THEOREM 6.1.** For all $\delta \in (0, 1)$ and for all $\varepsilon \in (0, 1)$, by taking $m = \lceil 3/(2\varepsilon) \rceil$, we have, for all $t \ge (n-1)(\ln n - \ln \delta + 2\ln(2+1/\varepsilon) + \ln(9/32))$,

$$ \mathbb{P}\{|\omega_A(C_t^{(i)}) - \gamma_A| < \varepsilon, \text{ for all } i = 1, \dots, n\} \ge 1 - \delta. $$

The proof appears in Appendix A.4.

## 6.2 Solving the System Size Problem

In this subsection, we address the system size problem. Supposing that the number $n_A$ of nodes whose initial value is equal to A is known, we prove that each agent is able to determine either the exact value of the number $n$ of nodes or an approximation of this number, depending on the initial input value $m$.

We introduce the following two output functions, denoted by $\omega_{min}$ and $\omega_{max}$, which give respectively the lower and the upper bound of $n$. They are defined as follows. For all integer $x$,

$$ \omega_{min}(x) = \left\lfloor \frac{2n_A m}{2x + 3} \right\rfloor \quad \text{and} \quad \omega_{max}(x) = \begin{cases} +\infty & \text{if } x \le 1 \\ \left\lfloor \frac{2n_A m}{2x - 3} \right\rfloor & \text{if } x \ge 2. \end{cases} $$

All the proofs of this subsection are detailed in Appendix A.4. We first start by a general result on the convergence time for the system size problem.

**THEOREM 6.2.** For all $\delta \in (0, 1)$ and for all $t \ge (n-1)(2\ln(\sqrt{n_A}m + \sqrt{n}) - \ln \delta - \ln 2)$, we have

$$ \mathbb{P}\{\omega_{min}(C_t^{(i)}) \le n \le \omega_{max}(C_t^{(i)}), \text{ for all } i = 1, \dots, n\} \ge 1 - \delta. $$

Note that Theorem 6.2 has a parallel time of convergence in $O(\log(\sqrt{n_A}m + \sqrt{n}))$ that depends on $n$. Using an additional hypothesis, we can free ourselves from the dependence of the parallel time of convergence on the knowledge of $n$.
**COROLLARY 6.3.** If $n_A m^2 \ge 4n/\ln^2 2$, for all $\delta \in (0, 1)$ and for all $t \ge (n-1)(\ln n_A + 2 \ln m - \ln \delta)$, we have

$$ \mathbb{P} \left\{ \omega_{min} \left( C_t^{(i)} \right) \le n \le \omega_{max} \left( C_t^{(i)} \right), \text{ for all } i = 1, \dots, n \right\} \ge 1 - \delta. \quad (9) $$

Moreover, in the case where $n_A m \ge 3n(n+1)$, we have

$$ \mathbb{P} \left\{ \omega_{min} \left( C_t^{(i)} \right) = \omega_{max} \left( C_t^{(i)} \right) = n, \text{ for all } i = 1, \dots, n \right\} \ge 1 - \delta. \quad (10) $$

The simpler way to use this corollary is to take $n_A = 1$. Suppose that the designer knows an upper bound $N$ of the number $n$ of agents. By taking $m = 3N(N+1)$, each agent $i$ possesses the exact value of $n$ with probability at least $1 - \delta$ and after a parallel time equal to $2 \ln m - \ln \delta$. This value is equal to $\omega_{min} \left( C_t^{(i)} \right) = \omega_{max} \left( C_t^{(i)} \right)$ for all $i = 1, \dots, n$.

Suppose now that the designer under estimates the value $N$, which should have been an upper bound of $n$. We have thus $n > N$. Recall that $m = N(N+1)$. If $n \le 9(\ln^2 2)N^2(N+1)^2/4$, then we have $m^2 \ge 4n/\ln^2 2$. In that case each agent $i$ possesses an approximated value of $n$ with probability at least $1 - \delta$ and after a parallel time equal to $2 \ln m - \ln \delta$. This value belongs to the interval $[\omega_{min} \left( C_t^{(i)} \right), \omega_{max} \left( C_t^{(i)} \right)]$.

# 7 EXPERIMENTAL RESULTS

This section shows how tight our bounds are, by comparing Theorem 6.1, Theorem 6.2 and Corollary 6.3 to the results obtained via extensive simulations. The source code (Java) that allows us to obtain these experiments has been placed in the gitLab publicly accessible archival repository [21]. A simulation consists in the following steps: first, all the $n$ nodes are initialized to 0 or $m$ depending on the problem that must be solved. Then, at each step of the simulation, two nodes are randomly chosen to interact and update their state. The simulation stops when all the nodes are able to give the correct output, that is when the convergence occurs.

## 7.1 The Proportion Problem

For this problem, the $n$ nodes are randomly and independently initialized to 0 or $m$. Recall that $m = \lceil 3/(2\epsilon) \rceil$, where $\epsilon \in (0, 1)$ the sought precision. The number of nodes initialized with $m$ is $n_A$ and the proportion of such nodes if $\gamma_A = n_A/n$. We denote by $\theta$ the parallel convergence time which is defined by

$$ \theta = \frac{\inf \left\{ t \ge 0 \text{ s.t. for all } i = 1, \dots, n, \left| \frac{C_t^{(i)}}{m - \gamma_A} \right| < \epsilon \right\}}{n}. $$

We have run $R$ independent simulations and have stored the $R$ values of the parallel convergence times denoted by $\theta_1, \dots, \theta_R$. Recall that the convergence time $n\theta_k$ is the total number of interactions that have been executed during the $k$-th simulation when the convergence occurs.

We first illustrate the influence of $\gamma_A$ and we show the impact of the distance between $\ell$ and its nearest integer (i.e. $\ell - \lfloor \ell \rfloor$) on the approximated mean parallel convergence time $\bar{\theta} = (\theta_1 + \dots + \theta_R)/R$.

When applying Theorem 5.6, the worst case is obtained when $\|C_0 - L\|^2$ is as large as possible, which leads to the largest possible value of $K$. We have seen in Section 6 that $\|C_0 - L\|^2 = m^2 n_A (1 - n_A/n) = m^2 n \gamma_A (1 - \gamma_A)$. The maximum of this function is obtained when $\gamma_A = 1/2$, which thus gives the largest bound of the convergence time. This is observed in the simulation results illustrated in Figure 1(a). For
<figure><img src="image_2.png" /><figcaption>(a) Mean value $\bar{\theta}$ of the parallel convergence time as a function of $\gamma_A$, with $n = 10^3$, $\varepsilon = 0.0075$ and $R = 10^6$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Mean value $\bar{\theta}$ of the parallel convergence time as a function of $\ell$, with $n = 10^4$, $\varepsilon = 0.0075$ and $R = 10^4$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(a) $\theta_{[R(1-\delta)]}$ as a function of $n$, with $\delta = 0.1$ and $R = 10^3$. From top to the bottom, we have $\varepsilon = 10^{-4} - 10^{-8}/2$, $\varepsilon = 10^{-3} - 10^{-6}/2$ and $\varepsilon = 10^{-2} - 10^{-4}/2$ respectively.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) $\theta_{[R(1-\delta)]}$ as a function of $n$, with $\varepsilon = 10^{-3} - 10^{-6}/2$ and $R = 10^4$. From top to the bottom, we have $\delta = 10^{-3}, 10^{-2}$ and $10^{-1}$ respectively.</figcaption></figure>

<caption>Fig. 2. Comparing the estimation $\theta_{[R(1-\delta)]}$ of $T$ with the theoretical bound $\tau$ as a function of $n$.</caption>

each possible value of $\gamma_A$, we have run $R = 10^6$ independent simulations, and we plot the estimated mean value $\bar{\theta}$ of the parallel convergence time.

We show in Figure 1(b) the impact of $\ell$ on this estimated mean value. We have performed for different initial distributions, $R = 10^4$ simulations in a system with $n = 10^4$ agents with $m = 200$, which corresponds to $\varepsilon = 0.0075$. We have varied $n_A$ from 5000 to 5200, leading to $\ell$ values ranging from 100 to 104 with steps of 0.02. It is interesting to observe that when $\ell - \lfloor \ell \rfloor = 1/2$ (i.e., the fractional part of $\ell$ is equal to $1/2$), the estimated mean value of the parallel convergence time is maximal, while it is minimal when the fractional part of $\ell$ is equal to 0 (i.e. when $\ell$ is an integer).
<figure><img src="image_6.png" /></figure>

(a) $\theta_{[R(1-\delta)]}$ as a function of $\epsilon$, with $\delta = 10^{-1}$ and $R = 10^4$. From top to the bottom, we have $n = 10^5$, $n = 10^4$ and $n = 10^3$ respectively.

<figure><img src="image_7.png" /></figure>

(b) $\theta_{[N(1-\delta)]}$ as a function of $\epsilon$, with $n = 10^3$ and $R = 10^6$. From top to the bottom, we have $\delta = 10^{-5}$, $10^{-3}$ and $10^{-1}$ respectively.

<figure><img src="image_8.png" /><figcaption>Fig. 3. Comparing the estimation $\theta_{[R(1-\delta)]}$ of $T$ with the theoretical bound $\tau$ as a function of $\epsilon$.</figcaption></figure>

(a) $\theta_{[R(1-\delta)]}$ as a function of $\delta$, with $\epsilon = 10^{-2} - 10^{-4}/2$ and $R = 660000$. From top to the bottom, we have $n = 10^5$, $10^4$ and $10^3$ respectively.

<figure><img src="image_9.png" /></figure>

(b) $\theta_{[R(1-\delta)]}$ as a function of $\delta$, with $n = 10^3$ and $R = 10^6$. From top to the bottom, we have $\epsilon = 10^{-4} - 10^{-8}/2$, $\epsilon = 10^{-3} - 10^{-6}/2$ and $\epsilon = 10^{-2} - 10^{-4}/2$ respectively.

<caption>Fig. 4. Comparing the estimation $\theta_{[R(1-\delta)]}$ of $T$ with the theoretical bound $\tau$ as a function of $\delta$.</caption>

The main lessons drawn from these experiments are that the mean convergence time is maximal when $\gamma_A = 1/2$ and $\ell - \lfloor \ell \rfloor = 1/2$. Sufficient conditions to reach this maximum are obtained by setting $n$ even, $n_A = n/2$ and $m$ odd. In the following, all the experiments are run under these conditions, which are denoted by $C$.

We now illustrate our bound. Note that this bound is tight in the sense that among the many simulations we have performed under conditions $C$, a large number of them correspond exactly to this bound. In the following, we sort the parallel convergence times of the $R$ independent simulations, i.e. $\theta_1 \le \dots \le \theta_R$. Let $T$ be the first instant $t$ such that $\mathbb{P}\{\theta < t\} \ge 1 - \delta$. The estimation of $T$ is thus given by $\theta_{[R(1-\delta)]}$. For usual values of $\epsilon$ like $\epsilon = 10^{-p}$, with $p$ integer $\ge 2$, all the values of $m = \lceil 3/(2\epsilon) \rceil$
are even. In order to fit with conditions C, we take $\epsilon = 10^{-p} - 10^{-2p}/2$. We can check that m is odd for every integer $p \ge 2$. Figures 2, 3 and 4 compare simulation results which consist in the estimation $\theta_{[R(1-\delta)]}$ of t with the theoretical bound $\tau$ of the parallel convergence time, given in Theorem 6.1 as

$$ \tau = \ln(n) - \ln(\delta) + 2 \ln(2 + 1/\epsilon) + \ln(9/32). $$

These results are given as a function of n in Figure 2, as a function of $\epsilon$ in Figure 3 and as a function of $\delta$ in Figure 4. As can be seen, simulations exactly fit with our theoretical bound, except for quite small values of n, i.e. $n \le 80$ see Figure 2. This clearly shows the great tightness of our theoretical bound. Note the logarithmic scale of the x-axis.

## 7.2 The System Size Problem

<figure><img src="image_10.png" /><figcaption>Fig. 5. Comparing the estimation $\theta_{[R(1-\delta)]}$ of T with the theoretical bound $\tau$ as a function of m with $n = 10^3$, $\delta = 10^{-4}$ and $R = 10^5$.</figcaption></figure>

For this problem, all the n nodes are initialized to 0, except one node which is initialized to m. We thus have $n_A = 1$. We redefine $\theta$ as the parallel convergence time which is defined here by

$$ \theta = \frac{\inf\{t \ge 0 \text{ s.t. for all } i = 1, \dots, n, n \in \llbracket \omega_{min}(C_t^{(i)}), \omega_{max}(C_t^{(i)}) \rrbracket\}}{n}. $$

Hence the definition of T remains the same using this new definition of $\theta$. As for the proportion problem, we have run R independent simulations and have stored the R values of the parallel convergence times
denoted by $\theta_1, \dots, \theta_R$. Recall that the convergence time $n\theta_k$ is the total number of interactions that have been executed during the $k$-th simulation when the convergence occurs.

Figure 5 compares simulation results which consist in the estimation $\theta_{\lfloor R(1-\delta) \rfloor}$ of $T$, where $R = 10^5$ and $\delta = 10^{-4}$ with the theoretical bound $\tau$ of the parallel convergence time, given in Theorem 6.2 and Corollary 6.3, that is

$$ \tau = \begin{cases} 2 \ln (m + \sqrt{n}) - \ln \delta - \ln 2 & \text{if } m < \lfloor 2\sqrt{n}/\ln 2 \rfloor \\ 2 \ln m - \ln \delta & \text{otherwise} \end{cases} $$

This figure shows tightness of our bounds. Indeed among the many simulations we have performed, a large number of them correspond to these bounds. In this figure, we introduce the values $m_1$ and $m_2$ of $m$ to show the different range in which either Theorem 6.2 or Corollary 6.3 apply. Indeed, since $n_A = 1$ and $n = 10^3$, we define $m_1 = \lfloor 2\sqrt{n}/\ln 2 \rfloor = 92$ and $m_2 = 3n(n+1) = 3003000$. It follows that for $m \in \lfloor 1, m_1 \rfloor$ only Theorem 6.2 applies. For $m \in \lfloor m_1 + 1, m_2 - 1 \rfloor$, we can use Relation (9) of Corollary 6.3 and for $m \ge m_2$ we can use Relation (10) of Corollary 6.3. Clearly, the best result is obtained when $m \ge m_2$ since in that case each agent knows that, after a parallel time $\tau \ge 2 \ln m - \ln \delta$, the total number of agents is equal to $10^3$ with a probability greater than or equal to 0.9999. For $m = m_2$, this parallel time is $2 \ln m_2 - \ln \delta = 39.041$.

## 8 CONCLUSION

In this paper we have presented a thorough analysis of the bound of the convergence time of average-based population protocols, and applied it to both the proportion problem and the system size one. Thanks to a well chosen stochastic coupling, we have considerably improved existing results by providing explicit and tight bounds of the time required to converge to the solution of these problems. Numerical simulations illustrate the tightness of our bounds of convergence times.

## REFERENCES

[1] Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald Rivest. 2017. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. 2560–2579.

[2] Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-optimal Majority in Population Protocols. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

[3] Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. 2015. Fast and Exact Majority in Population Protocols. In Proceedings of the 34th annual ACM symposium on Principles of Distributed Computing (PODC). 47–56.

[4] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2004. Computation in networks of passively mobile finite-state sensors. In Proceedings of the 23rd annual ACM symposium on Principles of distributed computing (PODC).

[5] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed Computing 18, 4 (2006), 235–253.

[6] Dana Angluin, James Aspnes, and David Eisenstat. 2006. Stably computable predicates are semilinear. In Proceedings of the 25th annual ACM symposium on Principles of distributed computing (PODC). 292–299.

[7] Dana Angluin, James Aspnes, and David Eisenstat. 2008. A simple population protocol for fast robust approximate majority. Distributed Computing 20, 4 (2008), 279–304.

[8] Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. 2007. The computational power of population protocols. Distributed Computing 20, 4 (2007), 279–304.

[9] James Aspnes and Eric Ruppert. 2007. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column 93 (2007), 98–117.
[10] Joffroy Beauquier, Peva Blanchard, and Janna Burman. 2013. Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs. In *Proceedings of the International Conference on Principles of Distributed Systems (OPODIS)*.

[11] Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. 2018. A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. In *Proceedings of the International Symposium on Distributed Computing (DISC)*.

[12] Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. 2017. Brief Announcement: Population Protocols for Leader Election and Exact Majority with $O(\log^2 n)$ States and $O(\log^2 n)$ Convergence Time. In *Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC)*.

[13] O. Bournez, J. Cohen, and M. Rabie. 2015. Homonym Population Protocols. In *Proceedings of the 3rd International Conference on Networked Systems (NETYS)*.

[14] C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and E. Ruppert. 2006. When birds die: Making population protocols fault-tolerant. In *Proceedings of the 2nd IEEE Conference on Distributed Computing in Sensor Systems (DCOSS)*. 51–66.

[15] David Doty and Mahsa Eftekhari. 2019. Efficient size estimation and impossibility of termination in uniform dense population protocols. (2019). https://arxiv.org/pdf/1808.08913.pdf

[16] Moez Draief and Milan Vojnovic. 2012. Convergence speed of binary interval consensus. *SIAM Journal on Control and Optimization* 50, 3 (2012), 1087–11097.

[17] R. Guerraoui and E. Ruppert. 2009. Names trump malice: Tiny mobile agents can tolerate byzantine failures. In *Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part II (ICALP)*. 484–495.

[18] George B. Mertzios, Sotiris E. Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. 2014. Determining majority in networks with local interactions and very small local memory. In *Proceedings of the International Colloquium (ICALP)*. 871–882.

[19] Ryu Mizoguchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. 2012. On space complexity of self-stabilizing leader election in mediated population protocol. *Distributed Computing* 25, 6 (2012), 451–460.

[20] Yves Mocquard. 2018. *Analyse probabiliste de protocoles de population*. Ph.D. Dissertation. Université de Rennes 1. https://people.irisa.fr/Yves.Mocquard/theseYvesMocquard.pdf

[21] Y. Mocquard. 2019. Proportion Population Protocol - Java code. (2019). https://gitlab.inria.fr/ymocquard/simuppv1b

[22] Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. 2015. Counting with population protocols. In *Proceedings of the 14th IEEE International Symposium on Network Computing and Applications (NCA)*. 35–42.

[23] Yves Mocquard, Emmanuelle Anceaume, and Bruno Sericola. 2016. Full version. Optimal Proportion Computation with Population Protocols. In *IEEE Symposium on Network Computing and Applications (NCA)*. https://hal.archives-ouvertes.fr/hal-01354352

[24] Yves Mocquard, Bruno Sericola, and Emmanuelle Anceaume. 2017. Probabilistic analysis of counting protocols in large-scale asynchronous and anonymous systems. In *16th IEEE International Symposium on Network Computing and Applications, NCA*. 315–322.

[25] Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. 2009. Using three states for binary consensus on complete graphs. In *Proceedings of the INFOCOM Conference*.
# A APPENDIX

## A.1 Additional results of Subsection 5.3

In order to simplify the writing we use the notation $Y_t := \|C_t - L\|^2$ and to prove Theorem 5.2 we need the following two results.

**THEOREM A.1.** For every $t \ge 0$, we have

$$ \mathbb{E}(Y_{t+1} | C_t) = \left(1 - \frac{1}{n-1}\right) Y_t + \frac{q_t(n - q_t)}{n(n-1)}, $$

where $q_t$ denotes the number of odd entries of vector $C_t$.

**PROOF.** In the same way as in the proof of Theorem 6 in [22], one can deduce from Relations (1), that for all $t \ge 0$,

$$ Y_{t+1} = Y_t - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \left[ \left(C_t^{(i)} - C_t^{(j)}\right)^2 - 1_{\{C_t^{(i)} + C_t^{(j)} \text{ odd}\}} \right] 1_{\{X_t=(i,j)\}}. $$

We recall that $X_t$ and $C_t$ are independent and that $p_{i,j}(t) = 1/(n(n-1))$. Conditioning first by $C_t$, then taking the expectations, we get

$$ \begin{aligned} \mathbb{E}(Y_{t+1}|C_t) &= Y_t - \frac{1}{2} \left( \sum_{i=1}^{n} \sum_{j=1}^{n} \left[ \left(C_t^{(i)} - C_t^{(j)}\right)^2 - 1_{\{C_t^{(i)} + C_t^{(j)} \text{ odd}\}} \right] \right) p_{i,j}(t) \\ &= Y_t - \frac{1}{2n(n-1)} \sum_{i=1}^{n} \sum_{j=1}^{n} \left[ \left(C_t^{(i)} - C_t^{(j)}\right)^2 - 1_{\{C_t^{(i)} + C_t^{(j)} \text{ odd}\}} \right]. \end{aligned} $$

Using that (see in [22])

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} (C_t^{(i)} - C_t^{(j)})^2 = 2nY_t \quad \text{and} \quad \sum_{i=1}^{n} \sum_{j=1}^{n} 1_{\{C_t^{(i)} + C_t^{(j)} \text{ odd}\}} = 2q_t(n - q_t), $$

where integer $q_t$ is the number of odd entries of vector $C_t$, we deduce that

$$ \mathbb{E}(Y_{t+1} | C_t) = \left(1 - \frac{1}{n-1}\right) Y_t + \frac{q_t(n - q_t)}{n(n-1)}, $$

which completes the proof of Theorem A.1. □

**COROLLARY A.2.** For every $t \ge 0$, we have

$$ \mathbb{E}(Y_{t+1}) \le \left(1 - \frac{1}{n-1}\right) \mathbb{E}(Y_t) + \frac{n}{4(n-1)} - \frac{1_{\{n \text{ odd}\}}}{4n(n-1)}. $$

**PROOF.** Integer $q_t$ being the number of odd entries of vector $C_t$, we have $q_t \in \{0, 1, \dots, n\}$. The function $g$ defined, for $x \in [0, n]$, by $g(x) = x(n - x)$ has its maximum at point $x = n/2$, so we have $0 \le g(x) \le n^2/4$. Thus

$$ g(q_t) = q_t(n - q_t) \le \frac{n^2}{4}. $$

We distinguish the following two cases:
* if $n$ is even then $q_t$ can be equal to $n/2$ which means that the best upper bound of $g(q_t)$ is $n^2/4$.

* if $n$ is odd then $q_t$ being an integer, it cannot be equal to $n/2$. The maximum of $g_t(q_t)$ is then reached either at point $q_t = (n-1)/2$ or at point $q_t = (n+1)/2$. For both points, we have $g(q_t) \le (n-1)(n+1)/4 = n^2/4 - 1/4$, so the best upper bound of $g(q_t)$ is $n^2/4 - 1/4$.

Putting together the two cases, we obtain

$$q_t(n - q_t) \le \frac{n^2}{4} - \frac{1_{\{n \text{ odd}\}}}{4}.$$

Using this inequality in Theorem A.1, we get

$$\mathbb{E}(Y_{t+1} | C_t) \le \left(1 - \frac{1}{n-1}\right) Y_t + \frac{n}{4(n-1)} - \frac{1_{\{n \text{ odd}\}}}{4n(n-1)}.$$

Taking the expectation in both sides, we obtain

$$\mathbb{E}(Y_{t+1}) \le \left(1 - \frac{1}{n-1}\right) \mathbb{E}(Y_t) + \frac{n}{4(n-1)} - \frac{1_{\{n \text{ odd}\}}}{4n(n-1)},$$

which completes the proof of Corollary A.2. □

Theorem 5.2 solves the recurrence stated in Corollary A.2.

**Theorem 5.2** For every $t \ge 0$, we have

$$\mathbb{E}(Y_t) \le \left(1 - \frac{1}{n-1}\right)^t \mathbb{E}(Y_0) + \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n} \quad (11)$$

**PROOF.** The proof is made by induction on the time $t$. Clearly, Relation (11) is true for $t = 0$. Suppose that Relation (11) is true for a fixed integer $t$. Using Corollary A.2, we obtain

$$\begin{aligned} \mathbb{E}(Y_{t+1}) &\le \left(1 - \frac{1}{n-1}\right) \mathbb{E}\left(\left(1 - \frac{1}{n-1}\right)^t \mathbb{E}(Y_0) + \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n}\right) \\ &\quad + \frac{n}{4(n-1)} - \frac{1_{\{n \text{ odd}\}}}{4n(n-1)} \\ &\le \left(1 - \frac{1}{n-1}\right)^{t+1} \mathbb{E}(Y_0) + \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n}, \end{aligned}$$

which completes the proof of Theorem 5.2. □

## A.2 Additional results of Subsection 5.4

We start by the following Lemma.

**LEMMA A.3.** Let $h = \lfloor \ell \rfloor + 1/2$ and $H = (h, h, \dots, h) \in \mathbb{R}^n$. If $\lambda = (n - 1_{\{n \text{ odd}\}}) / (2n)$, then

$$\|C_t - L\|^2 = \|C_t - H\|^2 - \frac{1_{\{n \text{ odd}\}}}{4n} \ge \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n} \quad (12)$$
PROOF. Remark that vector $C_t - L$ is orthogonal to the unit vector $e$ (all the entries of $e$ are equal to 1):

$$ \langle C_t - L, e \rangle = \sum_{i=1}^{n} (C_t^{(i)} - \ell) = n\ell - n\ell = 0. $$

Hence, since $L-H = (\ell-h)e$, we deduce that $C_t - L$ and $L-H$ are orthogonal too. Applying Pythagore's Theorem, we obtain

$$ \|C_t - H\|^2 = \|C_t - L\|^2 + \|L - H\|^2 \Rightarrow \|C_t - L\|^2 = \|C_t - H\|^2 - \|L - H\|^2. \quad (13) $$

We have

$$ \|L - H\|^2 = n(\ell - h)^2 = n(1/2 - (\ell - \lfloor \ell \rfloor))^2 $$

By definition of $\lambda$ and since $\lambda = (n - 1_{\{n \text{ odd}\}})/(2n)$, we have either $\ell - \lfloor \ell \rfloor = (n - 1_{\{n \text{ odd}\}})/2n$ or $\ell - \lfloor \ell \rfloor = (n + 1_{\{n \text{ odd}\}})/2n$. In both cases, we get

$$ \|L - H\|^2 = \frac{1_{\{n \text{ odd}\}}}{4n}. \quad (14) $$

Then, remark that

$$ \|C_t - H\|^2 \ge n \min_{1 \le i \le n} |C_t^{(i)} - (\lfloor \ell \rfloor + \frac{1}{2})|^2 \ge n|\frac{1}{2}|^2 = \frac{n}{4}. \quad (15) $$

Injecting Relation (14) in Relation (13), and applying Inequality (15), we conclude Inequality (12). $\square$

LEMMA A.4. If $\lambda = (n - 1_{\{n \text{ odd}\}})/(2n)$, then

$$ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \iff \|C_t - L\|_{\infty} > \frac{n + 1_{\{n \text{ odd}\}}}{2n}. \quad (16) $$

PROOF. Note first that if $\lambda = (n - 1_{\{n \text{ odd}\}})/(2n)$ then we have

$$ \|C_t - L\|_{\infty} \ge 1 - \lambda = \frac{n + 1_{\{n \text{ odd}\}}}{2n}. \quad (17) $$

If $\max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} = 1$, then, using Relation (2), we have

$$ \min_{1 \le i \le n} C_t^{(i)} \le \frac{1}{n} \sum_{i=1}^{n} C_t^{(i)} = \ell \le \max_{1 \le i \le n} C_t^{(i)} = \min_{1 \le i \le n} C_t^{(i)} + 1. $$

It follows easily that $\min_{1 \le i \le n} C_t^{(i)} = \lfloor \ell \rfloor$ and $\max_{1 \le i \le n} C_t^{(i)} = \lceil \ell \rceil$. Hence, we have

$$ \|C_t - L\|_{\infty} = \max \{\ell - \lfloor \ell \rfloor, \lceil \ell \rceil - \ell\} = 1 - \lambda $$

since $\max \{\ell - \lfloor \ell \rfloor, \lceil \ell \rceil - \ell\} + \min \{\ell - \lfloor \ell \rfloor, \lceil \ell \rceil - \ell\} = 1$. We deduce

$$ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} = 1 \implies \|C_t - L\|_{\infty} = \frac{n + 1_{\{n \text{ odd}\}}}{2n}. \quad (18) $$

If $\|C_t - L\|_{\infty} = \frac{n+1_{\{n \text{ odd}\}}}{2n}$, then $\|C_t - L\|_{\infty} = \max \{\ell - \lfloor \ell \rfloor, \lceil \ell \rceil - \ell\}$. Remark that, by definition of the infinity norm,

$$ \|C_t - L\|_{\infty} = \max_{1 \le i \le n} |C_t^{(i)} - \ell| = \max \left( |\max_{1 \le i \le n} C_t^{(i)} - \ell|, |\min_{1 \le i \le n} C_t^{(i)} - \ell| \right) = \max \left( \max_{1 \le i \le n} C_t^{(i)} - \ell, \ell - \min_{1 \le i \le n} C_t^{(i)} \right). $$
By identification, we have either

$$ \max_{1 \le i \le n} C_t^{(i)} - \ell = \ell - \lfloor \ell \rfloor \text{ and } \ell - \min_{1 \le i \le n} C_t^{(i)} = \lceil \ell \rceil - \ell $$

or

$$ \max_{1 \le i \le n} C_t^{(i)} - \ell = \ell - \lfloor \ell \rfloor \text{ and } \ell - \min_{1 \le i \le n} C_t^{(i)} = \lceil \ell \rceil - \ell. $$

Hence,

$$ \left( \max_{1 \le i \le n} C_t^{(i)} - \ell \right) + \left( \ell - \min_{1 \le i \le n} C_t^{(i)} \right) = (\lceil \ell \rceil - \ell) + (\ell - \lfloor \ell \rfloor) \implies \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} = \lceil \ell \rceil - \lfloor \ell \rfloor. $$

If $\ell$ is an integer (i.e. $n$ divides $\sum_{i=1}^n C_0^{(i)}$), then $\lceil \ell \rceil - \lfloor \ell \rfloor = 0$. This involves that $\lambda = 0$, which is impossible here since $\lambda$ is supposed to be equal to $(n - 1_{\{n \text{ odd}\}}) / (2n)$ and $n \ge 2$ (pairwise interactions). Otherwise, if $\ell$ is not an integer, then $\lceil \ell \rceil = \lfloor \ell \rfloor + 1$. Combining this result with Relation (18), we deduce that

$$ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} = 1 \iff \|C_t - L\|_{\infty} = \frac{n + 1_{\{n \text{ odd}\}}}{2n}. $$

Hence, combining this relation with Relation (17), we deduce Relation (16). $\square$

We can now turn to the proof of Theorem 5.3.

**Theorem 5.3** For all $\delta \in (0, 1)$, if $\lambda = (n - 1_{\{n \text{ odd}\}}) / (2n)$ and if there exists a constant $K$ such that $\|C_0 - L\| \le K$ then, for every $t \ge (n - 1)(2 \ln K - \ln \delta - \ln 2)$, we have

$$ \mathbb{P} \left\{ \|C_t - L\|_{\infty} > \frac{n + 1_{\{n \text{ odd}\}}}{2n} \right\} = \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \right\} \le \delta. \quad (19) $$

Equivalently,

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} = \min_{1 \le i \le n} C_t^{(i)} + 1 \right\} \ge 1 - \delta. \quad (20) $$

**PROOF.** We first aim to show that

$$ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \implies \|C_t - L\|^2 \ge \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n} + 2. \quad (21) $$

Let $h = \lfloor \ell \rfloor + 1/2$ and $H = (h, h, \dots, h) \in \mathbb{R}^n$.

In the same way, if $\max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1$, then there exists an agent $i$ such that $|C_t^{(i)} - h| \ge 3/2$, and for all $j \in \{1, 2, \dots, n\} \setminus \{i\}$, $|C_t^{(j)} - h| \ge 1/2$. We can thus write

$$ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \implies \|C_t - H\|^2 \ge \frac{n-1}{4} + \left(\frac{3}{2}\right)^2 = \frac{n}{4} + 2. $$

Applying Lemma A.3, we thus obtain Relation (21), and deduce that

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \right\} \le \mathbb{P} \left\{ \|C_t - L\|^2 \ge \frac{n}{4} - \frac{1_{\{n \text{ odd}\}}}{4n} + 2 \right\}. \quad (22) $$

Then, from Relation (3) of Theorem 5.2, we obtain

$$ \mathbb{E} \left( \|C_t - L\|^2 - \frac{n}{4} + \frac{1_{\{n \text{ odd}\}}}{4n} \right) \le \left( 1 - \frac{1}{n-1} \right)^t \mathbb{E} (\|C_0 - L\|^2). $$
Let $\tau = (n-1)(2\ln K - \ln \delta - \ln 2)$. For $t \ge \tau$, we have

$$ \left(1 - \frac{1}{n-1}\right)^t \le e^{-t/(n-1)} \le e^{-\tau/(n-1)} = \frac{2\delta}{K^2}. $$

Moreover, since $\|C_0 - L\| \le K$, we get $\mathbb{E}(\|C_0 - L\|^2) \le K^2$ and thus

$$ \mathbb{E} \left( \|C_t - L\|^2 - \frac{n}{4} + \frac{1_{\{n \text{ odd}\}}}{4n} \right) \le 2\delta. $$

Using the Markov inequality (Lemma A.3 ensures that we take the expectation of a non negative random variable), we obtain for $t \ge \tau$,

$$ \mathbb{P} \left\{ \|C_t - L\|^2 - \frac{n}{4} + \frac{1_{\{n \text{ odd}\}}}{4n} \ge 2 \right\} \le \delta. $$

Hence, we deduce from Relation (22) that, for $t \ge \tau$,

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \right\} \le \delta. $$

Remark that $\max_{1 \le i \le n} C_t^{(i)}$ cannot be equal to $\min_{1 \le i \le n} C_t^{(i)}$ here. Indeed, if so, then vector $C_t$ is equal to vector $L$, implying that $\ell$ is an integer. In such a case, $\lambda = 0$, which is impossible since $n \ge 2$ (pairwise interactions). Hence, $\mathbb{P}\{\max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} \le 1\} = \mathbb{P}\{\max_{1 \le i \le n} C_t^{(i)} = \min_{1 \le i \le n} C_t^{(i)} + 1\}$ and we directly obtain Relation (20).

Finally, applying Lemma A.4, we deduce that

$$ \mathbb{P} \left\{ \max_{1 \le i \le n} C_t^{(i)} - \min_{1 \le i \le n} C_t^{(i)} > 1 \right\} = \mathbb{P} \left\{ \|C_t - L\|_{\infty} > \frac{n + 1_{\{n \text{ odd}\}}}{2n} \right\}, $$

which ends the proof. $\square$

## A.3 Additional proof of Subsection 5.5

**Lemma 5.4** For all $t \ge 0$, there exists a non empty set $B_t$ of $b$ agents, i.e. $B_t \subset \{1, \dots, n\}$ and $|B_t| = b$, such that for all $i \in \{1, 2, \dots, n\}$, we have

$$ D_t^{(i)} = C_t^{(i)} + 1_{\{i \in B_t\}}. \qquad (23) $$

**PROOF.** The proof is made by induction. Relation (23) is clearly true for $t = 0$ by definition of $D_0$. Suppose that at time $t \ge 0$, there exists a set $B_t \subset \{1, 2, \dots, n\}$ with $|B_t| = b$, satisfying Relation (23). Let $i$ and $j$ be the two agents interacting at time $t$, i.e. let $X_t = (i, j)$, for both processes $C_t$ and $D_t$. We distinguish the following cases.

* **Case 1**: $i, j \in B_t$.

In this case, we have

$$ D_{t+1}^{(i)} = \left\lfloor \frac{D_t^{(i)} + D_t^{(j)}}{2} \right\rfloor = \left\lfloor \frac{C_t^{(i)} + C_t^{(j)} + 2}{2} \right\rfloor = C_{t+1}^{(i)} + 1. $$

In the same way, we have $D_{t+1}^{(j)} = C_{t+1}^{(j)} + 1$, which means that $i, j \in B_{t+1}$. The other entries being invariant, we have $B_{t+1} = B_t$.
• **Case 2**: $i, j \notin B_t$.

In this case, we have $D_{t+1}^{(i)} = C_{t+1}^{(i)}$ and $D_{t+1}^{(j)} = C_{t+1}^{(j)}$ which means that $i, j \notin B_{t+1}$. The other entries being invariant, we have $B_{t+1} = B_t$.

• **Case 3**: $i \in B_t$ and $j \notin B_t$.

- **Case 3.1**: $C_t^{(i)} + C_t^{(j)}$ is even.

In this case, we have

$$D_{t+1}^{(i)} = \left| \frac{D_t^{(i)} + D_t^{(j)}}{2} \right| = \left| \frac{C_t^{(i)} + 1 + C_t^{(j)}}{2} \right| = \left| \frac{C_t^{(i)} + C_t^{(j)}}{2} \right| = C_{t+1}^{(i)}.$$

In the same way, we have $D_{t+1}^{(j)} = C_{t+1}^{(j)} + 1$, which means that $i \notin B_{t+1}$ and $j \in B_{t+1}$. We thus have $B_{t+1} = (B_t \setminus \{i\}) \cup \{j\}$ and so $|B_{t+1}| = |B_t| = b$.

- **Case 3.2**: $C_t^{(i)} + C_t^{(j)}$ is odd.

In a similar way to the case 3.1, we have $D_{t+1}^{(i)} = C_{t+1}^{(i)} + 1$ and $D_{t+1}^{(j)} = C_{t+1}^{(j)}$, which means that $i \in B_{t+1}$ and $j \notin B_{t+1}$ and so $B_{t+1} = B_t$.

• **Case 4**: $i \notin B_t$ and $j \in B_t$.

- **Case 4.1**: $C_t^{(i)} + C_t^{(j)}$ is even.

In a similar way to the case 3.2, we have $D_{t+1}^{(i)} = C_{t+1}^{(i)}$ and $D_{t+1}^{(j)} = C_{t+1}^{(j)} + 1$, which means that $i \notin B_{t+1}$ and $j \in B_{t+1}$ and so $B_{t+1} = B_t$.

- **Case 4.2**: $C_t^{(i)} + C_t^{(j)}$ is odd.

In a similar way to the case 3.1, we have $D_{t+1}^{(i)} = C_{t+1}^{(i)} + 1$ and $D_{t+1}^{(j)} = C_{t+1}^{(j)}$, which means that $i \in B_{t+1}$ and $j \notin B_{t+1}$. We thus have $B_{t+1} = (B_t \setminus \{j\}) \cup \{i\}$ and so $|B_{t+1}| = |B_t| = b$.

In all the cases, we have shown that $B_{t+1} \subset \{1, 2, \dots, n\}$, that $|B_{t+1}| = |B_t| = b$ and that (23) is true at time $t+1$, which completes the proof of Lemma 5.4. □

LEMMA A.5. For all $t \ge 0$, we have

$$\|C_t - L\|_{\infty} - \|D_t - L_D\|_{\infty} \le \frac{n-1}{n}$$

PROOF. From Lemma 5.4, we easily get

$$\ell_D = \frac{1}{n} \sum_{i=1}^{n} D_t^{(i)} = \ell + \frac{|B_t|}{n} = \ell + \frac{b}{n}.$$

Observing that

$$\|D_t - L_D\|_{\infty} = \max\{\ell_D - \min_{1 \le i \le n} D_t^{(i)}, \max_{1 \le i \le n} D_t^{(i)} - \ell_D\},$$

$$\|C_t - L\|_{\infty} = \max\{\ell - \min_{1 \le i \le n} C_t^{(i)}, \max_{1 \le i \le n} C_t^{(i)} - \ell\},$$

we first deduce that

$$- \|D_t - L_D\|_{\infty} \le - \left( \ell_D - \min_{1 \le i \le n} D_t^{(i)} \right) \text{ and } - \|D_t - L_D\|_{\infty} \le - \left( \max_{1 \le i \le n} D_t^{(i)} - \ell_D \right). \quad (24)$$

We distinguish two cases:
• Case 1: $\|C_t - L\|_{\infty} = \ell - \min_{1 \le i \le n} C_t^{(i)}$. Applying Relation (24), we deduce that

$$ \|C_t - L\|_{\infty} - \|D_t - L_D\|_{\infty} \le \left( \ell - \min_{1 \le i \le n} C_t^{(i)} \right) - \left( \ell_D - \min_{1 \le i \le n} D_t^{(i)} \right). $$

Since, from Lemma 5.4, we have that $\min_{1 \le i \le n} D_t^{(i)} \le \min_{1 \le i \le n} C_t^{(i)} + 1$, we deduce

$$ \|C_t - L\|_{\infty} - \|D_t - L_D\|_{\infty} \le \ell - \ell_D + 1 = 1 - \frac{b}{n} \le \frac{n-1}{n}. $$

• Case 2: $\|C_t - L\|_{\infty} = \max_{1 \le i \le n} C_t^{(i)} - \ell$. Applying Relation (24), we deduce that

$$ \|C_t - L\|_{\infty} - \|D_t - L_D\|_{\infty} \le \left( \max_{1 \le i \le n} C_t^{(i)} - \ell \right) - \left( \max_{1 \le i \le n} D_t^{(i)} - \ell_D \right). $$

Since, from Lemma 5.4, we have $\max_{1 \le i \le n} C_t^{(i)} \le \max_{1 \le i \le n} D_t^{(i)}$, we deduce again

$$ \|C_t - L\|_{\infty} - \|D_t - L_D\|_{\infty} \le \ell - \ell_D = \frac{b}{n} \le \frac{n-1}{n}, $$

which ends the proof.

□

LEMMA A.6. For all $t \ge 0$, we have

$$ \|D_t - L_D\| - \|C_t - L\| < \sqrt{n}. $$

PROOF. Remark that vector $D_t - L_D$ is orthogonal to the unit vector $e$ (all the entries of $e$ are equal to 1):

$$ \langle D_t - L_D, e \rangle = \sum_{i=1}^{n} (D_t^{(i)} - \ell_D) = n\ell_D - n\ell_D = 0. $$

Hence, since $L_D - L = (\ell_D - \ell)e$, we deduce that $D_t - L_D$ and $L_D - L$ are orthogonal too. It follows, by using the Pythagore's Theorem, that we have

$$ \|D_t - L\|^2 = \|D_t - L_D\|^2 + \|L_D - L\|^2 \implies \|D_t - L_D\| \le \|D_t - L\|. $$

From Relation (4), we have $D_t^{(i)} - C_t^{(i)} = 1_{\{i \in B_t\}}$, for every $i = 1, \dots, n$. Since $|B_t| = b$, this leads to $\|D_t - C_t\| = \sqrt{b}$. From the triangle inequality we get

$$ \|D_t - L\| \le \|C_t - L\| + \|D_t - C_t\| = \|C_t - L\| + \sqrt{b}. $$

Thus

$$ \|D_t - L\| \le \|C_t - L\| + \sqrt{b} \le \|C_t - L\| + \sqrt{n}, $$

since $b < n$.

□

**Lemma 5.5** For any process $C$, there exists a shadow process $D$ of parameter $b$ such that $\ell_D - \lfloor \ell_D \rfloor = \frac{n-1}{2n}$. Specifically, let $d \ge 0$ be the smallest integer such that $n$ divides $\sum_{i=1}^n C_0^{(i)} + d$.

• If $0 \le d < n/2$, then $b = d + \frac{n-1}{2}$,

• If $n/2 \le d < n$, then $b = d - \frac{n+1}{2}$.
**PROOF.** We consider a set $B_0$ of agents with cardinality $b \in \{0, \dots, n-1\}$ and the corresponding shadow process $D_t$ of process $C_t$ defined in Section 5.5. By definition of $\ell_D$, we have, from Lemma 5.4, $\ell_D = \ell + \frac{b}{n}$ which gives $\ell_D - \lfloor \ell_D \rfloor = \ell + \frac{b}{n} - \lfloor \ell + \frac{b}{n} \rfloor$.

Let an integer $d$ such that $n$ divides $n\ell + d$. We thus have $\ell_D - \lfloor \ell_D \rfloor = \frac{b-d}{n} - \lfloor \frac{b-d}{n} \rfloor$.

* Case 1: if $0 \le d < n/2$, we take $b = d + \frac{n-1\{n \text{ odd}\}}{2}$, which leads to $0 \le b \le n-1$ and

$$ \ell_D - \lfloor \ell_D \rfloor = \frac{n-1\{n \text{ odd}\}}{2n} - \lfloor \frac{n-1\{n \text{ odd}\}}{2n} \rfloor = \frac{n-1\{n \text{ odd}\}}{2n}, $$

since $1 > \frac{n-1\{n \text{ odd}\}}{2n} > 0$ and by definition of the floor function.

* Case 2: if $n/2 \le d < n$, we take $b = d - \frac{n+1\{n \text{ odd}\}}{2}$, which leads to $0 \le b \le n-1$ and

$$ \ell_D - \lfloor \ell_D \rfloor = -\frac{n+1\{n \text{ odd}\}}{2n} - \lfloor -\frac{n+1\{n \text{ odd}\}}{2n} \rfloor = -\frac{n+1\{n \text{ odd}\}}{2n} + 1, $$

since $0 > -\frac{n+1\{n \text{ odd}\}}{2n} > -1$ (and by definition of the floor function). Hence, $\ell_D - \lfloor \ell_D \rfloor = \frac{n-1\{n \text{ odd}\}}{2n}$, which ends the proof.

□

**Theorem 5.6** For all $\delta \in (0, 1)$, if there exists a constant $K$ such that $\|C_0 - L\| \le K$, then, for every $t \ge (n-1)(2\ln(K+\sqrt{n}) - \ln\delta - \ln 2)$, we have

$$ \mathbb{P} \left\{ \|C_t - L\|_{\infty} \ge \frac{3}{2} \right\} \le \delta. \qquad (25) $$

**PROOF.** Let $d$ an integer such that $n$ divides $n\ell + d$. Applying Lemma 5.5, we deduce that there exists a shadow process $D$ associated with a set $B_0$ of agents with cardinality $b$ such that

$$ \ell_D - \lfloor \ell_D \rfloor = \frac{b-d}{n} - \lfloor \ell + \frac{b-d}{n} \rfloor = \frac{n-1\{n \text{ odd}\}}{2n}. $$

Hence, $\lambda_D = \min\left(\frac{n-1\{n \text{ odd}\}}{2n}, 1 - \frac{n-1\{n \text{ odd}\}}{2n}\right) = \frac{n-1\{n \text{ odd}\}}{2n}$. In addition, from Lemma A.6, we have $\|D_0 - L_D\| \le \|C_0 - L\| + \sqrt{n} \le K + \sqrt{n}$, by hypothesis. We can thus apply Theorem 5.3 to process $D_t$ and obtain that, for $t \ge (n-1)(2\ln(K+\sqrt{n}) - \ln\delta - \ln 2)$,

$$ \mathbb{P} \left\{ \|D_t - L_D\|_{\infty} > \frac{n+1\{n \text{ odd}\}}{2n} \right\} = \mathbb{P} \left\{ \max_{1 \le i \le n} D_t^{(i)} - \min_{1 \le i \le n} D_t^{(i)} > 1 \right\} \le \delta. $$

From Lemma A.5, we get

$$ \|C_t - L\|_{\infty} \le \|D_t - L_D\|_{\infty} + \frac{n-1}{n}, $$

which gives

$$ \|D_t - L_D\|_{\infty} \le \frac{n+1\{n \text{ odd}\}}{2n} \implies \|C_t - L\|_{\infty} \le \frac{3n-2+1\{n \text{ odd}\}}{2n} < \frac{3}{2}, $$

thus

$$ \mathbb{P} \left\{ \|C_t - L\|_{\infty} < \frac{3}{2} \right\} \ge \mathbb{P} \left\{ \|D_t - L_D\|_{\infty} \le \frac{n+1\{n \text{ odd}\}}{2n} \right\}, $$
or equivalently

$$ \mathbb{P}\left\{\|C_t - L\|_{\infty} \geq \frac{3}{2}\right\} \leq \mathbb{P}\left\{\|D_t - L_D\|_{\infty} > \frac{n + 1_{\{n \text{ odd}\}}}{2n}\right\} \leq \delta, $$

which completes the proof of Theorem 5.6.

□

## A.4 Additional results of Subsection 6

**Theorem 6.1** For all $\delta \in (0, 1)$ and for all $\varepsilon \in (0, 1)$, by taking $m = \lceil 3/(2\varepsilon) \rceil$, we have, for all $t \ge (n-1)(\ln n - \ln \delta + 2\ln(2+1/\varepsilon) + \ln(9/32))$,

$$ \mathbb{P}\{|\omega_A(C_t^{(i)}) - \gamma_A| < \varepsilon, \text{ for all } i = 1, \dots, n\} \geq 1 - \delta. $$

PROOF. Since $m = \lceil 3/(2\varepsilon) \rceil$, we have, from Relation (8),

$$ \|C_0 - L\| \le \frac{m\sqrt{n}}{2} = \left\lceil \frac{3}{2\varepsilon} \right\rceil \frac{\sqrt{n}}{2} \le \left( \frac{3}{2\varepsilon} + 1 \right) \frac{\sqrt{n}}{2} = \left( \frac{3 + 2\varepsilon}{4\varepsilon} \right) \sqrt{n}. $$

By choosing $K = (3 + 2\varepsilon)\sqrt{n}/(2\varepsilon)$, we obtain

$$ 2 \ln(K + \sqrt{n}) = 2 \ln \left[ \left( \frac{3 + 6\varepsilon}{4\varepsilon} \right) \sqrt{n} \right] = \ln n + 2 \ln(3/4) + 2 \ln(2 + 1/\varepsilon). $$

We are now able to apply Theorem 5.6, which leads, for all $\delta \in (0, 1)$ and for all $t \ge (n-1)(\ln n - \ln \delta + 2\ln(2+1/\varepsilon) + \ln(9/32))$, to

$$ \mathbb{P}\{\|C_t - L\|_{\infty} \geq 3/2\} \leq \delta $$

or equivalently, since $\ell = \gamma_A m$, to

$$ \mathbb{P}\left\{\left|C_t^{(i)} - \gamma_A m\right| < 3/2, \text{ for all } i = 1, \dots, n\right\} \geq 1 - \delta. $$

This can be also written as

$$ \mathbb{P}\left\{\left|\frac{C_t^{(i)}}{m} - \gamma_A\right| < \frac{3}{2m}, \text{ for all } i = 1, \dots, n\right\} \geq 1 - \delta $$

and, since $m \ge 3/(2\varepsilon)$, we get

$$ \mathbb{P}\left\{\left|\frac{C_t^{(i)}}{m} - \gamma_A\right| < \varepsilon, \text{ for all } i = 1, \dots, n\right\} \geq 1 - \delta, $$

which completes the proof of Theorem 6.1.

□

Recall that

$$ \omega_{min}(x) = \left\lfloor \frac{2n_A m}{2x + 3} \right\rfloor \quad \text{and} \quad \omega_{max}(x) = \begin{cases} +\infty & \text{if } x \le 1 \\ \left\lfloor \frac{2n_A m}{2x - 3} \right\rfloor & \text{if } x \ge 2. \end{cases} $$

**Theorem 6.2** For all $\delta \in (0, 1)$ and for all $t \ge (n-1)(2\ln(\sqrt{n_A}m + \sqrt{n}) - \ln \delta - \ln 2)$, we have

$$ \mathbb{P}\left\{\omega_{min}(C_t^{(i)}) \le n \le \omega_{max}(C_t^{(i)}), \text{ for all } i = 1, \dots, n\right\} \ge 1 - \delta. $$
PROOF. From Relation (7), we obtain $||C_0 - L|| \le \sqrt{n_A}m\sqrt{1 - n_A/n} \le \sqrt{n_A}m$. Applying Theorem 5.6, we deduce that for all $t \ge (n-1)(2\ln(\sqrt{n_A}m + \sqrt{n}) - \ln \delta - \ln 2)$,

$$ \mathbb{P}\left\{\|C_t - L\|_{\infty} < \frac{3}{2}\right\} \ge 1 - \delta. $$

Then, using that

$$ \|C_t - L\|_{\infty} < \frac{3}{2} \Leftrightarrow \text{ for all } i = 1, \dots, n, \quad C_t^{(i)} - \frac{3}{2} < \ell = \frac{n_A m}{n} < C_t^{(i)} + \frac{3}{2}, \quad (26) $$

we deduce first that, for all $i = 1, \dots, n$, $\frac{n_A m}{C_t^{(i)} + 3/2} < n$, which involves that $\omega_{min}(C_t^{(i)}) = \left| \frac{n_A m}{C_t^{(i)} + 3/2} \right| \le n$.

For the left hand-side of Relation (26), if $C_t^{(i)} \le 2$, then $\omega_{max}(C_t^{(i)}) = +\infty$, thus $n \le \omega_{max}(C_t^{(i)})$.

And if $C_t^{(i)} \ge 2$ we deduce from Relation (26) that

$$ n < \frac{n_A m}{C_t^{(i)} - 3/2} \Rightarrow n \le \left\lfloor \frac{n_A m}{C_t^{(i)} - 3/2} \right\rfloor = \omega_{max}(C_t^{(i)}). $$

We conclude that, for all $i = 1, \dots, n, n \le \omega_{max}(C_t^{(i)})$, which completes the proof. □

**Corollary 6.3** If $n_A m^2 \ge 4n/\ln^2 2$, for all $\delta \in (0, 1)$ and for all $t \ge (n-1)(\ln n_A + 2 \ln m - \ln \delta)$, we have

$$ \mathbb{P}\left\{\omega_{min}(C_t^{(i)}) \le n \le \omega_{max}(C_t^{(i)}), \text{ for all } i = 1, \dots, n\right\} \ge 1 - \delta. $$

Moreover, in the case where $n_A m \ge 3n(n+1)$, we have

$$ \mathbb{P}\left\{\omega_{min}(C_t^{(i)}) = \omega_{max}(C_t^{(i)}) = n, \text{ for all } i = 1, \dots, n\right\} \ge 1 - \delta. $$

PROOF. The first additional hypothesis $n_A m^2 \ge 4n/\ln^2 2$ give us that

$$ \frac{n}{n_A m^2} \le \frac{\ln^2 2}{4}. \quad (27) $$

Using the fact $\ln(1+y) \le y$, for every $y \ge 0$, we obtain, for every $u, v$ with $u, v > 0$, that $\ln(u+v) - \ln(u) = \ln(1+v/u) \le v/u$. Hence, $\ln(u+v) \le \ln(u) + v/u$. Applying this inequality with $u = \sqrt{n_A}m$ and $v = \sqrt{n}$, and using Relation (27), we obtain a lower bound for $2 \ln(\sqrt{n_A}m) + \ln 2$:

$$ \ln(\sqrt{n_A}m + \sqrt{n}) \le \ln(\sqrt{n_A}m) + \frac{\sqrt{n}}{\sqrt{n_A}m} = \ln(\sqrt{n_A}m) + \sqrt{\frac{n}{n_A m^2}} \le \ln(\sqrt{n_A}m) + \frac{\ln 2}{2}. $$

This inequality tells us that if $t \ge (n-1)(\ln n_A + 2 \ln m - \ln \delta) = (n-1)(2 \ln(\sqrt{n_A}m) + \ln 2 - \ln \delta - \ln 2)$, then $t \ge (n-1)(2 \ln(\sqrt{n_A}m + \sqrt{n}) - \ln \delta - \ln 2)$, we can thus apply Theorem 6.2, which completes the first part of the proof.

We turn now to the second part of the proof. First, we have from Theorem 5.6 that

$$ C_t^{(i)} > \frac{n_A m}{n} - \frac{3}{2}, \text{ for all } i = 1, \dots, n. \quad (28) $$
Using the second additional hypothesis ($3n(n+1) \le n_A m$), we first deduce that

$$3n^2 \le n_A m - 3n.$$

Multiplying each side of the inequality by $4n_A m/n^2$, we obtain that

$$12n_A m \le (2n_A m/n)^2 - 12n_A m/n.$$

Then, using that

$$(2n_A m/n)^2 - 12n_A m/n = (2n_A m/n - 3)^2 - 9 = 4(n_A m/n - 3/2)^2 - 9, \quad (29)$$

we deduce

$$12n_A m \le 4(n_A m/n - 3/2)^2 - 9.$$

Combining Relations (28) and (29), we obtain, for all $i = 1, \dots, n$,

$$0 \le 12n_A m < 4(C_t^{(i)})^2 - 9.$$

Hence, for all $i = 1, \dots, n$,

$$\frac{12n_A m}{4(C_t^{(i)})^2 - 9} < 1 \iff \frac{2n_A m}{2C_t^{(i)} - 3} - \frac{2n_A m}{2C_t^{(i)} + 3} = \omega_{max}(C_t^{(i)}) - \omega_{min}(C_t^{(i)}) < 1,$$

since $1/(2x-3) + 1/(2x+3) = 6/(4x^2-9)$, for all real $x$. Hence,

$$\omega_{min}(C_t^{(i)}) = \omega_{max}(C_t^{(i)}) = n, \text{ for all } i = 1, \dots, n,$$

which ends the proof. □