Parsimonious Flooding in Geometric Random-Walks ∗ Andrea Clementi Riccardo Silvestri Dipartimento di Matematica Dipartimento di Informatica Universit`a “Tor Vergata” di Roma Sapienza Universit`a di Roma [email protected] [email protected] 1 January 28, 2011 1 0 2 n a Abstract J 7 Westudytheinformationspreadingyieldedbythe(Parsimonious) 1-FloodingProtocol 2 in geometric Mobile Ad-Hoc Networks. We consider n agents on a convex plane region of diameter D performing independent randomwalks with move radius ρ. At any time step, ] every active agent v informs every non-informed agent which is within distance R from v I S (R > 0 is the transmission radius). An agent is only active at the time step immediately s. after the one in which has been informed and, after that, she is removed. At the initial c time step, a source agent is informed and we look at the completion time of the protocol, [ i.e., the first time step (if any) in which all agents are informed. 1 Thisrandomprocessis equivalenttothe well-knownSusceptible-Infective-Removed (SIR) v infection process in Mathematical Epidemiology. No analytical results are available for 8 this random process over any explicit mobility model. 0 Thepresenceofremovedagentsmakesthisprocessmuchmorecomplexthanthe(standard) 3 5 flooding. We prove optimal bounds on the completion time depending on the parameters . n, D, R, and ρ. The obtained bounds hold with high probability. 1 0 We remark that our method of analysis provides a clear picture of the dynamic shape of 1 the information spreading (or infection wave) over the time. 1 : v i Keywords: Geometric Random Walks, Information/Virus Spreading, Mobile Ad-Hoc Net- X works, Flooding Protocols. r a ∗ This work was partially supported by the PRIN 2008 research project COGENT (COmputational and GamE-theoreticaspectsofuncoordinatedNeTworks),fundedbytheItalianMinistryofEducation,University, and Research. 1 Introduction IntheGeometric Random-Walk Model [7,10,11],nagentsperformindependentrandomwalks over a bounded plane region and we consider the following infection process. Every agent S can be in three different states: non-informed (white) state, informed-active (red), informed- removed (black). During a time step, every agent performs one step of the random walk and every red agent informs (infects) all white agents lying within distance R. A white agent that has been informed (for the first time) at time step t, she becomes red at time step t + 1. Finally, when an agent becomes red she stays red for just one time step and, after that, she becomes black and stays that, forever. At the initial time step, a source agent is in the red state. The completion time of the above infection process is the first time step in which every agent gets into the black state. If this time step does not exist then we say the infection process does not complete. This random process is inspired by two main scenarios: The Susceptible-Infected-Removed (SIR) process which is widely studied in Mathematical Epidemiology [1, 2, 4] and the (Par- simonious) 1-Flooding Protocol [3] in geometric Mobile Ad-Hoc Networks (MANET). The (parsimonious) k-flooding protocol is the generalized version of the above infection process where a white agent, which is informed at time t, will remain red (so active) for the next k time steps. Whilethestandardfloodingisextremely inefficientintermsofagent’s energyconsumption and message complexity, the k-flooding protocol (for small values of k) strongly reduces the agent’s energy consumption and the overall message complexity. However, as discussed later, the infection process yielded by the k-flooding (for small k) over a dynamic network is much more complex than that yielded by the standard flooding. Thek-flooding has been studied in [3] on Edge-Markovian Evolving Graphs (Edge-MEG). An Edge-MEG [6, 7] is a Markovian random process that generates an infinite sequence of graphs over the same set of n agents. If an edge exists at time t then, at time t + 1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p. The stationary distribution of an Edge-MEG with parameter p and q is the famous Erd¨os-R´enyi random graph (n,p˜) wherep˜= p . The work G p+q [3] gives tight bounds on the k-flooding on stationary Edge-MEG for arbitrary values of p, q and k. In particular, it derives the reachability threshold for the k-flooding, i.e., the smallest k = k(n,p,q) over which the protocol completes. Edge-MEG is an analytical model of dynamic networks capturing time-dependencies, an im- portantfeatureobservedinrealscenariossuchas(faulty)wirelessnetworksandP2Pnetworks. However, it does not model important features of MANET. Indeed, in Edge-MEG, edges are independent Markov chains while, in MANET, there is a strong correlation among edges: agents use to act over a geometric space [7, 10, 11, 14]. Our Contribution. We study the 1-flooding protocol in the geometric random-walk model (the resulting MANET will be called geometric-MANET). The move radius ρ determines the maximal distance an agent can travel in one time step. Even though network modelling issues are out of the aims of this work, both the transmission radius and the move radius play a crucial role in our analysis and, thus, a small discussion about them is needed. Both parameters depend on several factors. In mathematical epidemiology, they depend on the agent’s mobility, the kind of infection and on the agent’s social behaviour that all together determine the average rate of “positive” contacts. In typical biological cases, the move radius can besignificantly larger than thetransmission radius. In MANET,the move radius depends on, besides the agent’s mobility, the adopted protocol that tunes the transmission rate of the 1 agents: the larger is the time between two consecutive transmissions the larger is ρ. A larger ρ could yield a better message complexity at the cost of a larger completion time (the correct trade-offs is derived in [8] for the standard flooding). It turns out that setting the “most convenient” value of the move radius is an issue that concernsboththenetworkmodellingandtheprotocoldesign. Forthesereasons,weinvestigate the 1-flooding for a wide range of values for parameters R and ρ. Most of the known analytical studies concern geometric-MANET defined over squares or disks. We instead consider any measurable region of diameter D( ). Informally speaking, a S S bounded region of the plane is said measurable if it is convex and it can be well approximated by a cover of square cells of suitable size. Furthermore, in a measurable region, we require the geometric random-walk model yields an almost-uniform stationary distribution of the agents. Square and disks are in fact the simplest examples of regions having all such properties. We first show a negative result. Given a measurable region , if the transmission radius R S is below the connectivity threshold1 of , then, for any ρ > 0, w.h.p.2 there are m = nα (for S some constant α >0) possible source agents for which the 1-flooding does not complete. This negative result also holds for the k-flooding for any k = O(1) and ρ6 R. We thus study the 1-flooding for R over the connectivity threshold of . We emphasize that, S evenin this case, nothing is known about the connectivity of the subset of red agents over the time and, more generally, about the impact of agent mobility on the 1-flooding process. If ρ R/(2√2), we prove that the information spreads at “optimal” speed Θ(R), i.e., the 1- ≤ flooding protocol w.h.p. completes within O(D( )/R) time steps. Observe that, since ρ < R, S this bound is asymptotically optimal. Then, we consider move radii that can be up to any polynomial of R, i.e. ρ 6 poly(R). We prove that the information spreads at “optimal” speed that is Θ(ρ). So the 1-flooding w.h.p. completes in time O(D( )/ρ) which is optimal for any ρ > R. Notice that this optimal S information speed makes the 1-flooding time smaller than the static diameter O(D( )/R) of S the stationary graph: our bound is thus the first analytical evidence that agent’s mobility actually speeds-up this infection process. Finally, we observe that, in both cases, the energy- efficient 1-flooding protocol is as fast as the standard flooding [7, 8]. Can any upper bound for the 1-flooding time be directly extended to the k-flooding time, for any k > 1? Rather surprisingly, the answer is in general not positive. Indeed, consider the two protocols running independently on the same experiment of the geometric-MANET. In the k-flooding process, an agent might be informed much earlier than what happens in the 1- floodingone: henceshemight turninto theblack state earlier andthis might befatal for some other whiteagents meet later. Soacouplingbetween thetwo processesdoes notseem to exist. Another surprising fact is that, for the same reasons, increasing the transmission R does not necessarily imply the same or a better completion time of the k-flooding, for any k. In other words, it is not easy to establish whether the k-flooding time is a “monotone” function with respect to k or R. These facts provide a good insight about the crucial differences between the flooding process and the k-flooding one. Such differences make the analysis techniques adopted for the flooding almost useless. In particular, percolation theory [11, 10, 16], meeting and cover time of random walks on graphs [17], and the expansion/bootstrap arguments [7, 8] strongly rely on the fact that an informed agent will be active for all the flooding process. Furthermore, the analysis of k-flooding over the Edge-MEG model [3] strongly relies on the stochastic independence among the edges in (n,p): a property that clearly does not hold in G 1The connectivity threshold refers to theuniform distribution of n (static) agents overS. 2Asusual, an event is said to hold with high probability (w.h.p.) if its probability is at least 1−1/n. 2 geometric-MANET. Our method of analysis significantly departs from all those mentioned above. Besides the optimal bounds on the completion time, our analyses provide a clear characterization of the geometric evolution of the infection process. We make use of a grid partition of into cells S of size Θ(R) and define a set of possible states a cell can assume over time depending on the number of red, white and black agents inside it. We then derive the local state-evolution law of any cell. Thanks to the regularity of this law, we can characterize the evolution of the geometric wave formed by the red cells (i.e. cells containing some red agent). A crucial property we prove is that, at any time step, white cells (i.e. cells containing white agents only) will never be adjacent to black cells, so there is always a red wave working between the black region and the white one. Furthermore, we show that the red wave eventually spans the entire region before all agents become black. The generality of our method of analysis has further consequences. Thanks to the regularity of the red-wave shape, we are able to bound the time by which a given subregion will be infected for the first time. This bound is a function of the distance between the subregion and the initial position of the source agent. Actually, it is a function of the distance from the closest red agent at the starting time. So, our technique also works in the presence of an arbitrary set of source agents that aim to spread the same infection (or message). Under the same assumptions made for the single-source case, we can prove the completion time is w.h.p. Θ(ecc(A, )/R) (or Θ(ecc(A, )/ρ)) where A is the set of the positions of the source S S agents at starting time and ecc(A, ) is the geometric eccentricity of A in . Finally, the S S specific arguments of our proofs can be easily adapted to get the same upper bounds for the k-flooding as well. Related Works. As mentioned above, there are no analytical study of the parsimonious flooding process over any geometric mobility model. In what follows, we briefly discuss some analytical results concerning the flooding over some models of MANET. In [13], the flooding time is studied over a restricted geometric-MANET. Approximately, it corresponds to the case ρ = D. Notice that, under this restriction, the stochastic dependence between two consecutiveagentpositionsisnegligible. In[12],thespeedofdatacommunicationbetweentwo agents is studied over a class of Random-Direction models yielding uniform stationary agent’s distributions(including thegeometric-MANET model). They provide an upperboundon this speed that can be interpreted as a lower bound on flooding time when the mobile network is verysparseanddisconnected(i.e. R,ρ =o(1)). Theirtechnique,basedonLaplaciantransform of independent journeys, cannot be extended to provide any upper bound on the time of any version oftheflooding. We observethat, differently fromourmodel, both[13]and[12]assume that when an agent gets informed then all agents of her current connected component (no matter how large it is) will get informed in one time step. The same unrealistic assumption is adopted in [16], where bounds on flooding time (and some other tasks) are obtained in the Poissonapproximationofthegeometric-MANETmodel. In[7,8],thefirstalmosttightbounds for the flooding time over geometric-MANET have been given. As mentioned before, their proofs strongly rely on the fact that informed agents stay always active. Flooding and gossip time for random walks over the grid graph (so, the agent’s space is a graph) have been studied in [17]. Here, an agent informs all agents lying in the same node. Besides the differences between 1-flooding and flooding discussed before, it is not clear whether their results could be extended to the random walk model over geometric spaces. Especially, in their model, there is no way to consider arbitrary values of the move radius. Roadmap of the paper. The rest of the paper is organized as follows. After giving some 3 preliminary definitions in Section 2, we analyze the case ρ 6R/(2√2) in Section 3. In Section 4, we present the results for the case ρ 6 R2/√logn. In Section 5, we introduce a slight different geometric random-walk model and a more powerful technique to extend the bound O(D( )/ρ) to any ρ6 poly(R). In Section 6, we first briefly describe the extension to multi- S source case and, then, derive the completion threshold of R for the 1-flooding. Finally, some open questions are discussed in Section 7. Most of the proofs are given in the Appendix. 2 Preliminaries We first introduce the class of regions that can be considered feasible support spaces for our mobile agents. Definition 1 For any l,γ > 0, a bounded connected plane region is (ℓ,γ)-measurable if it S is convex and there exists a grid-partition of the plane into squared cells of side length ℓ in which a cell cover ( ) of exists such that, for any cell c ( ), area(c )> γℓ2. C S S ∈ C S ∩S We say that two cells are adjacent if they touch each other by side or by corner. The cell- diameter D ( ) of an (ℓ,γ)-measurable is defined as follows. Given two cells c,c′ (cid:3) ( ), define tSheir cell-distance d (c,c′) aSs the length of the shortest cell-path p = c =∈ (cid:3) cC S,c ,...,c = c′ such that for every i, c ( ) and c is adjacent to c . Thenh, we 0 1 s i i i+1 i ∈ C S define D ( ) = max d (c,c′) c,c′ ( ) (cid:3) (cid:3) S { | ∈ C S } Similarly, we can define the cell-distance between a cell and any cell subset , i.e., C d (c, ) = min d (c,c′) c′ (cid:3) (cid:3) C { | ∈ C} Observe that, since is convex, the (Euclidean) diameter D( ) and the cell-diameter D ( ) (cid:3) S S S are tightly related: D ( ) = Θ(D( )/ℓ). For instance, if is the L L-square (L > 0) and (cid:3) S S S × ℓ = o(L), then its cell diameter is Θ(L/ℓ). According to the geometric random-walk model, there are n agents that perform independent random walks over . At any time step, an agent in position x , can move uniformly at S ∈ S random to any position in (x,ρ) , where (x,ρ) is the disk of center x and radius ρ. This B ∩S B is a special case of the Random Trip Model introduced in [14] whereit is proved that it admits a unique stationary agents distribution. In the sequel, we always assume that at time t = 0 agents’ positions are random w.r.t. the stationary distribution. For the sake of simplicity, we assume that the average density of agents in (i.e. the average S number of agents per area unit) is 1. It is straightforward to scale all the definitions and results to an arbitrary average density of agents. Let us consider n mobile agents acting over an (ℓ,γ)-measurable region . We say that the S resultinggeometric-MANETsatisfiesthedensitycondition if,foreverytimestept = 0,1,...,n and for every cell c ( ), the number #c of agents in c at time step t satisfies, with ∈ C S probability at least 1 (1/n)4, the following inequalities − η ℓ2 6 #c 6 η ℓ2,where η ,η are positive constants. (1) 1 2 1 2 We will consider geometric-MANET that satisfy the density condition. For instance, if the region is the √n √n-square, this assumption implies R > β√logn, for a suitable constant × β > 0. More generally, the geometric random-walk model with n agents over an arbitrary 4 (ℓ,Θ(1))-measurable region with area( )/ℓ2 6 βn/logn for a suitable constant β > 0 and S move radius ρ= O(ℓ)satisfies thedensity condition. Theproof of this fact can beobtained by exploiting the same arguments used in [7, 8] for the discrete approximation of the geometric random-walk model on the square. Accordingtothe1-floodingprotocol, atanytimestep,every agentcanbeinthreedifferent states: white (non-informed) state, red (informed-active), and black (informed-inactive). The configuration conf(t) is defined as the set of the positions of the n agents together with their respective states at the end of time t. Theanalysis oftheinformationspreadingwillbeperformedintermsof thenumberofinfected cells. Given a cell c ( ), the neighborhood N(c) is the set of cells formed by c and all its ∈ C S adjacent cells. let us observe that, the density condition implies that w.h.p. the (geometric) source eccentricity in is Ω(D( )); morever the maximal speed of any message in the geometric- S S MANET is R+ρ. We thus easily get the following lower bound. Fact 2 For any k, the k-flooding time is w.h.p. Ω(D( )/(R+ρ)). S 3 High Transmission-Rate or Low-Mobility We warm-up with the case where the move radius is smaller than the transmission radius. More precisely, we assume ρ 6 R/(2√2). Under this assumption, an agent lying in a cell c cannot escape from N(c) in one step. This makes the analysis simpler than the cases with larger ρ. However, some of the crucial ideas and arguments adopted here will be exploited for the harder cases too. We can now state the optimal bound on 1-flooding. Consider a network formed by n mobile agents with transmission radius R and move radius ρ R/(2√2). The agents act over an ≤ (ℓ,γ)-measurable region of diameter D( ) such that ℓ = R/(2√2), and γ is any positive S S constant. Assume also that the resulting geometric-MANET satisfies the density condition. Theorem 3 Under the above assumptions, the 1-flooding time is w.h.p. Θ(D( )/R). S Thegeometric-MANET definedover anL L-square satisfiestheaboveconditionsprovided × Q that R > c L logn/n for a sufficiently large constant c (see [7, 8]). We thus have the 0 0 following p Corollary 4 Let R 6 L be such that R > c L logn/n for a sufficiently large constant c 0 0 and let ρ6 R/(2√2). Then the 1-flooding time over is w.h.p. Θ(L/R). p Q 3.1 Proof of Theorem 3 For the sake of simplicity, we assume that the time step is divided into 2 consecutive phases: the transmission phase where every red agent transmits the information and the move phase where every agent performs one step of the random walk. We need to introduce the feasible states of a cell during the infection process. Definition 5 At (the end of) any time step a cell c can be in 4 different states. It is white if it contains only white agents. It is red if it contains at least one red agent. It is black if it contains black agents only. It is grey if it is not in any of the previous 3 cases. 5 We will show that the infection process, at any time step, has (w.h.p.) a well defined shape in which no white cell is adjacent to a black one and there is no grey cell. This shape is formalized in the following definitions. A subset of white cells is a white component if it is a connected component w.r.t. the subset of all the white cells. Definition 6 A configuration conf(t) is regular if the following properties hold a) No cell is grey. b) Every white component is adjacent to a red cell. c) No white cell is adjacent to a black cell. Observe that the starting configuration conf(0) is regular. Definition 7 A white cell is red-close if it is adjacent to a red cell. Thenextlemma determines thelocal state-evolution of any cell ina regular configuration (the proof is given in the Appendix). Lemma 8 Consider any cell c at time step t and assume conf(t) be regular. Then the following properties hold. 1) If c is red-close then it becomes red in conf(t+1) w.h.p. 2) If c is (no red-close) white then it becomes white or red in conf(t+1). 3) If c is red then it becomes red or black in conf(t+1). 4) If c is black then it becomes red or black in conf(t+1). As an easy consequence of the above lemma, we get the following Lemma 9 For any t 6 n, if conf(t) is regular, then w.h.p. conf(t+1) is regular as well. The above result on regular configurations provides a clear characterization of the shape of the infection process. We now analyze the speed of the process. Observe that we can now assume that all configurations are regular (w.h.p.). The proof of the next lemma is given in the Appendix. Lemma 10 For any t < n, let w be any white cell in conf(t+1) and let Red(t) be the set of red cells in conf(t). It holds w.h.p. that d (w, Red(t+1)) 6 d (w, Red(t)) 1 (cid:3) (cid:3) − Starting from the initial configuration conf(0) (that has one red cell), Lemma 10 implies that every white cell in w.h.p will become red within O(D ( )) = O(D( )/R) time steps. (cid:3) S S S Moreover, thanks to Lemmas 8 and 9, every red cell will become either red or black. Finally, when all cells are black or red, after the next time step there are no more white agent and the theorem follows. 6 4 Low Transmission-Rate or High-Mobility I We consider the network formed by n mobile agents with transmission radius R > c √logn 0 and move radius ρ such that R/2 ρ αR2/√logn for sufficiently small constant α > 0. ≤ ≤ The agents act on a support region that satisfies two measurable conditions. S It is (ℓ ,γ)-measurable where ℓ = R/(4√2) and γ is a positive constant. Moreover, is also 0 0 S (ℓ,γ)-measurable where ℓ = 2ℓ and the grid of ℓ-cells is a subgrid of the grid of cells of side 0 length ℓ . We assume the geometric-MANET over satisfies the density condition w.r.t. the 0 S ℓ -cells. 0 Theorem 11 Undertheaboveassumptions, the1-flooding timeisw.h.p. boundedbyΘ(D( )/ρ). S The above theorem implies an optimal bound on 1-flooding time over an L L square for × Q any sufficiently large L. Corollary 12 Let R 6 L be such that R > c L logn/n for a sufficiently large constant c 0 0 and let R/2 6 ρ 6 αR2/√logn, for sufficiently small constant α > 0. Then the 1-flooding p time over is w.h.p. Θ(L/ρ). Q 4.1 Proof of Theorem 11 We adopt Def.s 5, 6, and 7 given in the previous section. Moreover, we need the further Definition 13 Two cells are ρ-close if the (Euclidean) distance between their geometric cen- ters is at most ρ. As in the previous section, we provide the local state-evolution law of any cell in a regular configuration (the proofs of all the next lemmas are given in the Appendix). Lemma 14 Consider any cell c at time step t and assume conf(t) be regular. Then the following properties hold w.h.p. 1) If c is red-close then it becomes red in conf(t+1). 2) If c is ρ-close to a red-close cell, then c becomes red in conf(t+1). 3) If c is white but it is not ρ-close to any red-close cell then it becomes white or red in conf(t+1). 4) If c is red or black but it is not ρ-close to any red-close cell then it becomes red or black in conf(t+1). As an easy consequence of the above lemma, we get the following Lemma 15 For any t < n, if conf(t) is regular, then w.h.p. conf(t+1) is regular as well. In what follows, we assume that all configurations are regular (w.h.p.) and analyze the speed of the infection process. Differently from the previous section, we will show this “speed” is Θ(ρ). Notice that the cell diameters of w.r.t. the ℓ and ℓ respectively differs by a “small” 0 S constant factor only: for this reason both of them are denoted as D ( ). (cid:3) S Lemma 16 For any t < n, let w be any white cell in conf(t+1) and let Red-close(t) be the set of red-close cells in conf(t). It w.h.p. holds that d (w,Red-close(t+1)) 6 max d (w,Red-close(t)) Θ(ρ/R),0 (cid:3) (cid:3) { − } 7 Thestartingconfiguration conf(0)isregularandcontains oneredcell. So,Lemma16implies that every white cell in w.h.p will become red within S D ( )ℓ D( ) (cid:3) O S = O S time steps ρ ρ (cid:18) (cid:19) (cid:18) (cid:19) Moreover, thanks to Lemma 14, every red cell will become either red or black. Finally, when all cells are black or red, in the next time step there are no more white agent and the theorem follows. 5 Low Transmission-Rate or High-Mobility II Inthis section, westudy thecase whenthe move radius can bemuch larger than thetransmis- sionradius. Moreprecisely,themoveradiuscanbeanarbitrarypolynomialofthetransmission radius, i.e. ρ = O(poly(R)), we also assume R > c √logn, for a sufficiently large c , and 0 0 ρ> 5R. A slightly different version of the geometric random-walk model is here adopted, the cellular random walk: theregion ispartitioned insquaredsupercells ofedgelengthρ. Thenanagent S lying in any position of a supercell C selects her next position independently and uniformly at random over the neighborhood N(C). Moreover, an agent can be informed by another (red) agent only if they both belong to the same supercell. So, in the cellular random walk model, the influence of an agent lying in a supercell C, in the next time step, is always restricted to the subregion N(C). Observe that the cellular random walk model preserves all significant featuresofthestandardonewhile,ontheotherhand,itavoidsseveralgeometrictechnicalities. The latter would yield a much more elaborate analysis without increasing the relevance of the obtained results. Weconsiderasupportregion thatsatisfiestwomeasurableconditions. Itis(ℓ,γ)-measurable S where ℓ = R/√2 and γ is a positive constant. Moreover, is also (ρ,γ)-measurable where S the grid of supercells is a subgrid of the grid of cells of side length ℓ. In what follows, the cells of size length ρ are called supercells and those of size length ℓ are called cells, simply. We also assume that the geometric-MANET over satisfies the density condition w.r.t. the cells. S The density condition for the stationary phase of the cellular random-walk model for ρ over a region satisfying the two above measurability can be proved by similar arguments as in [7, 8]. Indeed, the measurability by supercells guarantees that the stationary distribution is almost uniform; this fact together with the measurability by cells implies the density condition. Theorem 17 Under the above assumptions and 5R 6 ρ 6 poly(R), the 1-flooding time is w.h.p. Θ(D( )/ρ). S The above theorem implies an optimal bound on 1-flooding time over an L L square . × Q Corollary 18 Let R = o(L) be such that R > c L logn/n for a sufficiently large constant 0 c and let 5R 6 ρ 6 poly(R). Then the 1-flooding time over , in the cellular random-walk 0 p Q model with move radius ρ, is Θ(L/ρ) w.h.p. 5.1 Proof of Theorem 17 Thehigheragentmobilityforcesustoanalyzetheinfectionprocessoverthesupercells(besides over the cells). During the information spreading, the state a supercell can assume is defined 8 by some bounds on the number of red and white agents inside it. Roughly speaking, the number of white agents must never be too small w.r.t. the number of red agents, moreover thelatter mustincrease exponentially w.r.t. R2. Sincethe infection process is rather complex, we need to consider a relative large number of possible supercell states. Our analysis will first show every supercell eventually evolves from the initial white state to the final black state according to a monotone process over a set of intermediate states. Then, we will show that the speed of this process is asymptotically optimal, i.e., proportional to the move radius. ForasupercellC andatimestept,let#t(C),#t (C),and#t(C)be,respectively, thenumber r w b of red, white, and black agents in C. We define ρ2 hˆ = log c logn (2) R2 0R2 (cid:24) (cid:18) (cid:19)(cid:25) Observe that the assumption ρ= O(poly(R)) implies hˆ = Θ(1). Definition 19 For any time t and for any supercell C, we define some possible states of C at time t. State h= 0 (White State): #t(C)= 0 and #t(C)= 0. r b State h= 1,...,hˆ 1 (Intermediate States): The values of #t(C) and #t (C) satisfy − r w a R2h 6 #t(C)6 b R2h and #t (C)> c ρ2 h r h w h where a ,b ,c are constants (they will be fixed later in the Appendix) that satisfy a < h h h h b , a > a > > a > 0, 0 < b 6 b 6 6 b , and c > c > > c > 0. h 1 2 ··· hˆ−1 1 2 ··· hˆ−1 1 2 ··· hˆ−1 State ˆh (Red State): #t(C)> 90ρ2 logn. r R2 State ˆh+1 (Black State): #t (C) = 0. w All the above states are mutually disjoint but the last three ones, i.e., hˆ 1, hˆ, hˆ +1. For − every supercell C and time step t, in order to indicate that C satisfies the condition of state h, we will write ht(C)= h. Definition 20 The configuration conf(t) is regular if for every supercell C (1) an h 0,1,...,hˆ,hˆ +1 exists s.t. ht(C) = h and (2) if ht(C) = hˆ +1, it holds that, C′ N(C)∈, {ht(C′)= hˆ ht(C}′)= hˆ +1. ∀ ∈ ∨ In the sequel, we exchange the order of the phases in a time step: the move phase now comes before the transmission one. Clearly, this does not change our asymptotical results. The next technical lemmas allow to control the 1-step evolution of the state of any supercell in terms of the number of red and white agents and how such agents spread over its cells (the proofs are given in the Appendix). Lemma 21 Let C be a supercell such that #t (N(C)) > λρ2, for some constant λ > 720/c2. w 0 Then, immediately after the move phase of time t +1 (and before the transmission phase), w.h.p., for every cell c in C, it holds that the number of white agents in c is at least (λ/36)R2. Lemma 22 Let C be a supercell such that #t(C) > λRk, for some constants λ > 1800/c2 r 0 and k > 2. Then, immediately after the move phase of time t+1, w.h.p. in every supercell C′ N(C), the cells in C′ hit by some red agent are at least min (λ/30)Rk,ρ2/(2R2) . ∈ { } 9