George Giakkoupis

Thomas Sauerwald

Alexandre Stauffer

Randomized Rumor Spreading in Dynamic Graphs

We consider the well-studied rumor spreading model in which nodes contact a random neighbor in each round in order to push or pull the rumor. Unlike most previous works which focus on static topologies, we look at a dynamic graph model where an adversary is allowed to rewire the connections between vertices before each round, giving rise to a sequence of graphs, G1, G2, . . . Our first result is a bound on the rumor spreading time in terms of the conductance of those graphs. We show that if the degree of each node does not change much during the protocol (that is, by at most a constant factor), then the spread completes within t rounds for some t such that the sum of conductances of the graphs G1 up to Gt is O(log n). This result holds even against an adaptive adversary whose decisions in a round may depend on the set of informed vertices before the round, and implies the known tight bound with conductance for static graphs. Next we show that for the alternative expansion measure of vertex expansion, the situation is different. An adaptive adversary can delay the spread of rumor significantly even if graphs are regular and have high expansion, unlike in the static graph case where high expansion is known to guarantee fast rumor spreading. However, if the adversary is oblivious, i.e., the graph sequence is decided before the protocol begins, then we show that a bound close to the one for the static case holds for any sequence of regular graphs.

Introduction

Randomized rumor spreading is a popular epidemic protocol for disseminating information in large distributed networks. The protocol proceeds in a sequence of synchronous rounds. Initially, in round 0, an arbitrary node has a piece of information, the rumor. This rumor is then spread iteratively to the other nodes: In each round, every informed node (i.e., every node that learned the rumor in a previous round) chooses a random neighbor to which it sends the rumor. This is the so-called PUSH protocol. The PULL protocol is symmetric: In each round, every uninformed node chooses a random neighbor, and if this neighbor knows the rumor it transmits it to the uninformed node. Finally, the PUSH-PULL protocol is the combination of both strategies: In each round, every node chooses a random neighbor to send the rumor to, if the node is informed, or to request the rumor from, otherwise.

Several aspects of rumor spreading have been analyzed, including its running time (i.e., the number of rounds until all nodes get informed), the corresponding number of messages, and the amount of randomness needed. The running time is arguably the most fundamental and well-studied of those aspects. In particular, it has been shown that just a logarithmic number of rounds suffice to spread a rumor with high probability (w.h.p.) on several topologies, from basic communication networks, such as complete graphs, hypercubes and random graphs [START_REF] Pittel | On spreading a rumor[END_REF][START_REF] Feige | Randomized broadcast in networks[END_REF][START_REF] Karp | Randomized rumor spreading[END_REF], to more complex structures, such as preferential attachment graphs or power-law random graphs modeling social networks [START_REF] Doerr | Social networks spread rumors in sublogarithmic time[END_REF][START_REF] Fountoulakis | Ultra-fast rumor spreading in social networks[END_REF]. Recently, a number of studies have extended this line of work by establishing bounds on the running time of rumor spreading in terms of expansion parameters of the underlying graph, namely conductance [START_REF] Mosk-Aoyama | Fast distributed algorithms for computing separable functions[END_REF][START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF][START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF][START_REF] Censor-Hillel | Fast information spreading in graphs with large weak conductance[END_REF] and vertex expansion [START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF][START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF][START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF]. This connection between rumor spreading and graph theory is also relevant for understanding social and other real networks, as studies have indicated that such networks have good expansion properties [START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF][START_REF] Chierichetti | Rumor spreading in social networks[END_REF].

A limitation of the above results is that they require the graph to be fixed throughout the execution of the rumor spreading protocol, whereas many of the prevalent topologies, such as peer-to-peer or wireless networks, are inherently dynamic. In particular, the structure of these networks may change more quickly than a rumor spreads.

In this paper we analyze the running time of randomized rumor spreading in a dynamic setting, given by a sequence of graphs G 1 , G 2 , . . . with the same vertex set of size n, but possibly distinct edge sets. In this setting, at each round t, a vertex contacts a random neighbor in graph G t in order to push or pull the rumor. We assume that the edge set for each round is determined by an adversary. The adversary can be either adaptive, i.e., it decides the edge set for each round at the beginning of the round, knowing the set of informed vertices at the time, or oblivious, i.e., it fixes the complete sequence of graphs before rumor spreading starts, knowing just the source of the rumor.

Our first result is an upper bound on the running time of PUSH-PULL in terms of the conductances of graphs G 1 , G 2 , . . . Suppose that during the execution of the protocol, we have for each node that the ratio of its maximum over minimum degree is bounded by some ρ ≥ 1. We show that rumor spreading then completes within t rounds for some t such that the sum of conductances of the graphs G 1 up to G t is O(ρ log n). Moreover, this bound holds even if the adversary is adaptive.

Theorem 1. Let G 1 , G 2 , .
. . be a sequence of graphs determined by an adaptive adversary such that for each vertex u, its degree on each graph G t is at least δ u > 0 and at most ∆ u . The degree bounds δ u , ∆ u may be different for each u, and are fixed (in advance) by the adversary. Let ρ = max u (∆ u /δ u ). Also for each t ≥ 1, let φ t be the conductance of graph G t .

For any constant β > 0, there exists a constant b > 0 so that the following bound holds for PUSH-PULL. Let τ be the first round for which τ t=1 φ t ≥ bρ log n; τ = ∞ if not such round exists. Then with probability 1 -n -β , either τ = ∞ or all nodes have been informed by the end of round τ .

If all graphs G 1 , G 2 , . . . are the same and have conductance φ, then ρ = 1 and the bound of Theorem 1 implies the optimal bound for static graphs established in [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF], stating that O(log(n)/φ) rounds suffice w.h.p. to spread a rumor on any graph with conductance φ.

The dependence of the bound in Theorem 1 on ρ is not an artifact of our analysis. For example, even an oblivious adversary can construct a sequence of graphs in which every graph has constant conductance (but the degrees of nodes change widely and thus ρ is large) so that PUSH-PULL needs a linear number of rounds to inform all nodes (see Proposition 1, in Sect. 5).

We point out that Theorem 1 is shown for a more general setting, where multiple edges and self-loops are allowed. Moreover, it holds even if we define φ t to be the conductance in G t of the set of informed vertices before round t. This can be much larger than the conductance of G t , which is the minimum conductance of any set of vertices in G t .

For static graphs, conductance and vertex expansion yield very similar types of bounds on the running time of rumor spreading. For dynamic graphs, however, the situation is different. In particular, we reveal a separation between the adaptive and oblivious adversary models for the case of vertex expansion, which is not observed for conductance: An adaptive adversary can construct a sequence of regular graphs with constant vertex expansion so that PUSH-PULL takes a polynomial number of rounds (see Proposition 2)-by Theorem 1, this is not possible if conductance is considered in place of vertex expansion. For an oblivious adversary, on the other hand, we show that a bound similar to the one in Theorem 1 holds with vertex expansion, for any sequence of regular graphs.

Theorem 2. Let G 1 , G 2 , . . . be a sequence of d-regular graphs determined by an oblivious adversary. For each t ≥ 1, let α t be the vertex expansion of G t . Then, for any constant β > 0, there exists a constant c > 0 so that, if there exists a round t with t s=1 α s ≥ c•log 4 n log 2 d, then PUSH-PULL informs all nodes within t rounds with probability at least 1 -n -β .

If all graphs G 1 , G 2 , . . . are the same and have vertex expansion α, then the bound of Theorem 2 matches within a polylogarithmic factor the optimal bound for static graphs from [START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF], which states that O(log(n) log(d)/α) rounds suffice w.h.p. to spread a rumor on any graph (even non-regular) with vertex expansion α and maximum degree d. Whether Theorem 2 extends also to non-regular graph sequences is an interesting open problem.

Our proofs are non-trivial extensions of previous analyses for static graphs, in particular from [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF] and [START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF]. The dynamic setting, and also the adaptivity of the adversary for the case of conductance, add new challenges to the problem. The proof of Theorem 1 is based on a new martingale argument which exposes the outcome of each round gradually, one vertex at a time. The proof of Theorem 2 has to overcome the problem that the standard symmetry argument relating push and pull no longer holds, and this breaks key arguments used in existing proofs of bounds with vertex expansion. Moreover, tighter proofs from [START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF][START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF] employ potential functions based on the boundary of the informed nodes, which may largely fluctuate in the dynamic setting.

Related Work. There have been several studies on information spreading processes in dynamic graphs. Perhaps the closest one to our work is a recent work by Clementi et al. [START_REF] Clementi | Rumor spreading in random evolving graphs[END_REF] about PUSH in a random edge-Markovian model, yielding a dynamic variant of the Erdős-Rényi random graph. Motivated by the increasing importance of wireless networks, works [START_REF] Kesten | The spread of a rumor or infection in a moving population[END_REF][START_REF] Pettarin | Tight bounds on information dissemination in sparse mobile networks[END_REF][START_REF] Lam | Information dissemination via random walks in d-dimensional space[END_REF][START_REF] Peres | Mobile geometric graphs: Detection, coverage and percolation[END_REF] analyzed the dynamics of information dissemination among moving objects in d-dimensional grids. There are also several analyses on the flooding process-a variant of rumor spreading where every neighbor of an informed node becomes informed in a round [START_REF] Clementi | Information spreading in dynamic graphs[END_REF][START_REF] Clementi | Information spreading in stationary markovian evolving graphs[END_REF][START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF]. We note that in all these works, the graph dynamics are governed by a random process, whereas in our model the dynamics are controlled by an adversary.

Avin et al. [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF] analyzed the cover time of random walks on dynamic graphs specified by an oblivious adversary. They constructed graphs in which a simple random walk has an exponential cover time, but also proved that a lazy random walk has a polynomial cover time for any sequence of connected graphs.

Kuhn et al. [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] introduced the so-called k-token dissemination problem in a synchronous setting with a dynamically changing network. They considered a worst-case scenario, where the communication links are chosen by an adversary, and nodes do not know who their neighbors are for the current round before they send their messages. In contrast to our model, the connectivity (expansion) assumptions are weaker and correspondingly the time complexity bounds are much larger, i.e., at least polynomial in n [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Haeupler | Faster information dissemination in dynamic networks via network coding[END_REF][START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF][START_REF] Haeupler | Lower bounds on information dissemination in dynamic networks[END_REF][START_REF] Sarma | Fast distributed computation in dynamic networks via random walks[END_REF]. Georgiou et al. [START_REF] Georgiou | Asynchronous gossip[END_REF] considered the complexity of asynchronous gossip in a fault-prone distributed setting. While their model is quite different from ours, they also exhibited a separation between an adaptive and oblivious adversary.

Model

We consider the standard PUSH, PULL, and PUSH-PULL rumor spreading protocols. We will denote by I t the set of informed vertices after the first t rounds of the protocol, and by U t the set V \ I t of uninformed vertices. In particular, I 0 is the singleton set containing just the source, which is an arbitrarily chosen node.

The dynamic graph model we consider is an infinite sequence of graphs G 1 , G 2 , . . . on the same set of n vertices, but possibly with different edge sets. In each round t of rumor spreading, if a vertex must choose a neighbor to push the rumor to or pull the rumor from, then it chooses a random one among its neighbors in graph G t (if it has neighbors in G t ).

For each t ≥ 1, G t = (V, E t ), where V = {1, 2, . . . , n}, and the edge set E t is determined by an adversary. We distinguish between two adversarial models, adaptive and oblivious. An adaptive adversary decides the edge set E t knowing the outcome of all rounds before round t; precisely, E t is a function of I 0 , . . . , I t-1 . An oblivious adversary, on the other hand, has to specify the entire graph sequence in advance; precisely, E t is just a function of I 0 . An adversary can be either deterministic or randomized, where in the latter case the sequence of E t is also a function of a random bit string.

We recall now the definitions of two standard graph expansion parameters we use. For a graph G = (V, E), the conductance of a non-empty vertex set S ⊂ V and the conductance of graph G are defined respectively as

φ(S) = |E(S, V \ S)| min{vol(S), vol(V \ S)} and φ(G) = min S⊂V, S =∅ φ(S),
where E(S, V \ S) is the set of edges with one endpoint in each of the sets S and V \ S; and vol(S) = u∈S deg(u) is the volume of S, with deg(u) denoting the degree of u. The vertex expansion of S and G are respectively

α(S) = |∂S| min{|S|, |V \ S|} and α(G) = min S⊂V, S =∅ α(S),
where ∂S := N (S) \ S is the set of vertices outside S that are adjacent to some vertex in S. For any graph G, both φ(G) and α(G) are between 0 and 1, with high values indicating that the graph is well connected. If G is disconnected then

φ(G) = α(G) = 0.
In the following, when we write vol(I t ), ∂I t , φ(I t ), etc. (and similarly for U t ), we will assume that these quantities refer to graph G t+1 (and not to G t ), unless mentioned otherwise. This is convenient since I t is the set of informed vertices at the beginning of round t + 1.

Theorem 1 holds even if the graph sequence consists of multigraphs, with parallel edges and self-loops (as long as the degree of each vertex is at most polynomially large in n). To compute the conductance of a multigraph, parallel edges are counted with respect to their multiplicity and every self-loop counts as a single edge. Further, when a vertex must pick a random neighbor, this is done proportional to the multiplicity of a (parallel) edge or self-loop. If a self-loop is chosen then no communication takes place.

Proof of the Bound with Conductance (Theorem 1)

We observe that it suffices to consider just deterministic adversaries, since in case of a randomized adversary, we can just expose all its randomness (i.e., its random bit string) before the protocol starts, and then proceed deterministically.

Not all vertices are guaranteed to get informed eventually, as the adversary may permanently disconnect the network. However, it is not difficult to show that one can always modify a (deterministic) adversary, in such a way that this does not happen and it suffices to consider the modified adversary in the analysis. Thus, we will assume that the expected number of rounds until all nodes are informed is finite, i.e., E[min{t :

I t = V }] < ∞. (1)
For each round t ≥ 1, let Φ t = φ 1 +• • •+φ t be the sum of the conductances of the graphs in the first t rounds. We must show that for τ = inf{t : Φ t ≥ bρ log n}, we have w.h.p. that all nodes have been informed within τ rounds.

For each set S ⊆ V of vertices, we define the min-volume of S as vol * (S) = i∈S δ i . Thus vol * (S) is a lower bound for the volume of S on any of the graphs G t . Our proof is based on an analysis of the growth of vol * (I t ).

We will show the following lemma stating (a) if the min-volume of informed vertices is smaller than a constant fraction of the total min-volume, then the sum of conductances φ t until the min-volume doubles is bounded in expectation by O(ρ); and (b) if the min-volume of informed vertices is larger, then the sum of φ t until the min-volume of uninformed vertices halves is bounded by O(ρ).

Lemma 1. There is a fixed constant c > 0 such that for any round t ≥ 1,

(a) If vol * (I t ) ≤ vol * (V )/3 and τ t = min{k : vol * (I k ) ≥ 2 vol * (I t )}, then E[Φ τt - Φ t | I t ] ≤ cρ. (b) If vol * (I t ) > vol * (V )/3 and τ t = min{k : vol * (U k ) ≤ vol * (U t )/2}, then E[Φ τt -Φ t | I t ] ≤ cρ.
From this result, the bound of Theorem 1 follows easily: From Lemma 1(a) and Markov's Inequality it follows that when vol * (I t ) ≤ vol * (V )/3, we have

Pr[Φ τt -Φ t ≤ 2cρ | I t ] ≥ 1/2, i.e.
, with probability at least 1/2, vol * (I t ) doubles after Φ t has increased by at most 2cρ. It follows then by Chernoff bounds that 1/3 of the total min-volume gets informed with probability at least 1-n -β /2, for any fixed β, after a number t 1 of rounds such that

Φ t1 = 2cρ • O(log(vol * (V )/3)) = O(ρ log n), as log(vol * (V )) = O(log n). A similar argument using Lemma 1(b)
shows that if 1/3 of the total min-volume has been informed by some round t, then an additional t 2 rounds, such that Φ t+t2 -Φ t = O(ρ log n), suffice to inform the remaining vertices with probability at least 1 -n -β /2. From these two results and the union bound, Theorem 1 follows.

Proof of Lemma 1

Recall that during the spread, the degree of each vertex i ∈ V is lower bounded by δ i > 0 and upper bounded by ∆ i , and ∆ i /δ i ≤ ρ. Let δ = max i δ i .

The proof distinguishes three cases, depending on the min-volume of informed vertices initially: (i) vol * (I t ) < δ, (ii) δ ≤ vol * (I t ) ≤ vol * (V )/3, and (iii) vol * (I t ) > vol * (V )/3. For cases (ii) and (iii) it suffices that we consider only pull operations, while for case (i) we must consider both push and pull. Due to space limitations we only give the proof for case (ii). In this case,

τ t = min{k ≥ t : vol * (I k ) ≥ 2 vol * (I t )}. Claim 1. If δ ≤ vol * (I t ) ≤ vol * (V )/3 then E[Φ τt -Φ t | I t ] < 2ρ + 1.
Proof. We use a martingale argument that relates the min-volume of vertices informed by pull transmissions to the number of edges between informed and uninformed vertices. In this argument, the outcome of each round is exposed gradually, one vertex at a time. 4Assume I t is fixed. We divide each round k > t into |∂I k-1 | steps (∂I k-1 is the set of uniformed vertices at the beginning of round k that have some informed neighbor). Each of those |∂I k-1 | steps reveals the push and pull transmissions of the rumor in round k to a single vertex i ∈ ∂I k-1 . The order in which vertices i ∈ ∂I k-1 are considered can be arbitrary. We look at the sequence of all those steps, from round t + 1 until round τ t . For each step s = 1, 2, . . . , let i s be the vertex considered in step s, let k s be the round in which step s takes place, d s be the degree of i s during round k s (i.e., i s 's degree in G ks ), and γ s be the number of informed neighbors of i s in G ks at the beginning of round k s .

Below we first show that the sum of all γ s until the step when the min-volume of informed vertices has doubled is bounded in expectation by ρ(vol * t ) + δ). Then we bound the corresponding increase in Φ t in terms of the sum of γ s , and combine the two results to obtain the claim.

Let X s be the indicator variable that is 1 if i s pulls the rumor in step s, and X s = 0 otherwise. Further, let Z s be the indicator variable that is 1 if i s gets informed in step s, and 0 otherwise. Note that Z s ≥ X s , since i s may get informed by a push transmission. Note also that the sequence Z 1 , . . . , Z s-1 completely determines the evolution of the set of informed vertices in the first s -1 steps, and thus determines i s , k s , d s , and γ s . In order for i s to pull the rumor in step s, it must choose one of its γ s informed neighbors, among its d s neighbors in total. It follows that

E[X s | Z 1 . . . Z s-1 ] = γ s /d s . (2)
For each s ≥ 0, we define

Y s = 1≤j≤s (X j d j -γ j ) . The sequence Y 0 , Y 1 , . . . is a martingale with respect to Z 1 , Z 2 , . . . , because E[Y s | Z 1 . . . Z s-1 ] = Y s-1 + E[X s | Z 1 . . . Z s-1 ] • d s -γ s (2) = Y s-1 .
Let T be the number of steps after round t until the min-volume of informed vertices doubles, i.e., T = min{s : 1≤j≤s Z j δ ij ≥ vol * (I t )}. (Observe, k T = τ t .) Since T is a stopping time for Z 1 , Z 2 , . . . , and we have that E[T ] < ∞ 5 and the differences Y s -Y s-1 are bounded, it follows from the Optional Stopping Theorem that

E[Y T ] = E[Y 0 ] = 0.
Substituting the definition of Y T and rearranging gives

E 1≤j≤T γ j = E 1≤j≤T X j d j . (3)
We have 1≤j≤T X j d j ≤ ρ 1≤j≤T Z j δ ij , because X j ≤ Z j and

d j ≤ ∆ ij ≤ ρδ ij ; and from T 's definition, 1≤j≤T Z j δ ij < vol * (I t ) + δ. It follows E 1≤j≤T γ j < ρ(vol * (I t ) + δ). ( 4
)
we have the guarantee that the min-volume at that time is by at most δ -1 < vol * (It) larger than 2 vol * (It). (This is used in the line right above Eq.( 4), in order to obtain (4).) On the other hand, the min-volume right after the round during which the min-volume doubles may be much larger than 2 vol * (It). 5 This is immediate from Eq.( 1).

Next we bound Φ τt -Φ t in terms of 1≤j≤T γ j , and apply the above inequality to bound E[Φ τt -Φ t ]. For each round k with t < k ≤ τ t , the conductance φ k of G k is bounded by the conductance of I k-1 in G k , and thus

φ k ≤ s:ks=k γ s min{vol(I k-1 ), vol(U k-1 )} ≤ s:ks=k γ s vol * (I t ) ,
where the second inequality holds because vol(I k-1 ) ≥ vol * (I k-1 ) ≥ vol * (I t ) and

vol(U k-1 ) ≥ vol * (U k-1 ) ≥ vol * (U τt-1 ) = vol * (V ) -vol * (I τt-1 ) > vol * (V ) -2 vol * (I t ) ≥ vol * (I t ),
as vol * (I t ) ≤ vol * (V )/3. From the above bound on φ k applied for t < k < τ t , we obtain

Φ τt -Φ t = (φ t+1 + • • • + φ τt-1 ) + φ τt ≤ s:ks<τt γ s vol * (I t ) + 1.
From T 's definition, k T = τ t , and thus the sum above is s:ks<τt γ s < s≤T γ s .

Thus,

E[Φ τt -Φ t ] < E s≤T γ s vol * (I t ) + 1 (4)
< ρ(vol

* (I t ) + δ) vol * (I t ) + 1 ≤ 2ρ + 1, (5)
as δ ≤ vol * (I t ). This completes the proof of Claim 1.

The proof for the case of vol * (I t ) > vol * (V )/3 is similar, but considers the set of uninformed vertices instead of the set of informed ones.

Claim 2. If vol * (I t ) > vol * (V )/3 then E[Φ τt -Φ t | I t ] < 2ρ + 1.
The analysis in the proof of Claim 1 does not carry over to the case of vol * (I t ) < δ: The final inequality in [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] does not hold, as the ratio δ/ vol * (I t ) may be very large. In fact any analysis that relies only on pull transmissions is bound to fail, for otherwise Theorem 1 would hold even if only PULL were used, which is easily seen to be wrong because of the star graph counter-example. To show the next claim, we extend the approach of Claim 1 by taking into account also push transmissions.

Claim 3. If vol * (I t ) < min{δ, vol * (V )/3} then E[Φ τt -Φ t | I t ] < 3ρ + 1.

Proof of the Bound with Vertex Expansion (Theorem 2)

Theorem 2 can be deduced easily from the following result, in which we assume a uniform lower bound on the vertex expansion. (If d = O(log 3 n) then Theorem 2 follows directly from Theorem 1 since α ≤ d • Φ.) Theorem 3. Let t be any integer, and G 1 , G 2 , . . . , G t be a sequence of d-regular graphs with d = Ω(log 3 n) determined by an oblivious adversary, so that for each 1 ≤ s ≤ t, G s has vertex expansion at least α > 0. Then, for any constant β > 0, there exists a constant c > 0 such that, if t satisfies t • α ≥ c • log 3 n log 2 d, then PUSH-PULL informs all nodes within t rounds with probability at least 1 -n -β .

Proof of Theorem 3

The analysis of Theorem 3 is divided into three phases, according to the number of informed nodes. Before we analyze the different phases, we provide some tools we will use in the analysis. The proofs of all statements in this section are omitted due to space limitations.

The next lemma establishes a (nearly) exponential growth of the number of informed nodes until that number reaches d/ log n. Lemma 2. Let u ∈ V be arbitrary with I 0 = {u} and let κ := log 3 (d/(2 log n))+ 440. Then the following statements hold.

1. Pr I κ ≥ d 6 log n ≥ 1/2. 2. Pr I κ ≤ 3 220 • 10 6 • d ≥ 1 -n -4
, and more generally, for any round

1 ≤ s ≤ κ, Pr I s ≤ 2 • 10 6 • log n • 3 s ≥ 1 -n -4 .
The first statement of Lemma 2 motivates the following definition.

I t = {u} ≥ 1/4.
A similar notion of a friend was defined in [29, Definition 3.1] for a static graph; our definition depends on the sequence of graphs G t+1 , G t+2 , . . . , G t+κ , and so in particular, on the choice of t. Applying the first statement of Lemma 2, we have that for every subset U ⊆ V , every node u ∈ V , and every round t, node u is a friend of either U or V \ U in round t.

Next we consider the situation where I t is of any size, and half of the nodes in ∂I t are friends of I t . We shall prove that an almost constant fraction of nodes in I t gets informed after κ rounds. It should be noted that this is relatively straightforward in the case of static graphs, as it follows from a standard symmetry argument relating PUSH and PULL (cf. [START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF]Lemma 3.1]). Here, however, the analysis is considerably more involved, as we are dealing with dynamic graphs.

Lemma 3 (Key Lemma). Consider a round t with a fixed set of informed nodes I t , where 1 ≤ |I t | ≤ n/2. Let S ⊆ V \ I t be a set of vertices which are friends of I t in round t + 1. Then, there is a constant 0 < C < 1 so that, with probability at least 1/16, at least C • |S| log 2 n log d nodes get informed after κ additional rounds, for κ defined as in Lemma 2.

Next we analyze the growth of informed nodes in 3 phases:

|I t | ∈ [1, d 6 log n ], |I t | ∈ [ d 6 log n , d α ], and |I t | ∈ [ d α , n 2
]. In the following, κ is defined as in Lemma 2.

Lemma 4 (Phase 1). Assume that |I 0 | = 1. Then after t 1 := κ rounds, we have |I t1 | ≥ d 6 log n with probability at least 1/2.

The above result for the first phase follows immediately from Lemma 2.

Lemma 5 (Phase 2). Let t 1 be the first round for which |I t1 | ≥ d 6 log n . Then, for any constant β > 0, there exists a constant c > 0 so that, for t 2 := t 1 + c log 3 n log d α

• κ, we have |I t2 | ≥ d α with probability at least 1 -n -β . The analysis of the second phase is more involved. We only consider every (κ+1)-th round and distinguish between two cases. If half of the nodes in ∂I t are friends of I t , then Lemma 3 implies that a large fraction of these nodes becomes informed after κ+1 rounds. If half of the nodes in ∂I t are friends of V \I t , then, if such a node in ∂I t pulls the rumor in round t + 1, then after κ additional rounds d/(12 log n) nodes get informed in V \ I t . Expressing the progress of both cases via a submartingale and applying the Optional Stopping Theorem completes the proof of Lemma 5.

Lemma 6 (Phase 3). Let t 2 be the first round for which |I t2 | ≥ d α . Then, for any constant β > 0, there exists a constant c > 0 so that for t

3 := t 2 +c log 3 n log d α • κ, we have |I t3 | ≥ n
2 with probability at least 1 -n -β . The analysis of the third phase is somewhat similar to the analysis of the second phase. However, the case where half of the nodes in ∂I t are friends of V \ I t requires a more careful analysis, since we have to analyze the propagation of the rumor within V \ I t from several nodes in ∂I t in parallel.

From Lemmas 4-6 it follows that, with probability at least 1 -n -β , Phase 1 is completed after O(κ log n) = O(log n log d) rounds, and Phases 2 and 3 are completed after O( log 3 n log 2 d α ) rounds, thus proving the bound of Theorem 3.

Counter-Examples

High conductance is not sufficient to guarantee fast rumor spreading in our dynamic graph model. Even an oblivious adversary can construct a sequence of high-conductance graphs (in which the degrees of nodes change widely), so that PUSH-PULL needs a linear number of rounds to inform all nodes. Proposition 1. An oblivious adversary can construct a sequence of graphs G 1 , G 2 , . . ., each of which has conductance 1, so that PUSH-PULL needs n -1 rounds to complete.

Proof. Instead of analyzing the PUSH-PULL protocol we analyze a different process in which at each round all neighbors of the set of informed nodes become informed (i.e., I t+1 = I t ∪ ∂I t ). The strategy of the adversary is as follows. In every round t, G t is a star graph with n vertices. The source of the rumor is a vertex of degree 1, and in each round except for the last one, the informed nodes are vertices of degree 1. At first it may seem that the adversary has to be adaptive to employ this strategy. But, given that the source of the rumor is known, then I 0 is a deterministic set. Given G 1 and I 0 , then I 1 is again a deterministic set, and so on. Therefore, the construction above for the sequence G 1 , G 2 , . . . can be done in an oblivious manner. With this, our process satisfies |I t | = t + 1, for every 0 ≤ t ≤ n -1. Since the runtime of this process is at most the runtime of the PUSH-PULL protocol, the claim of the proposition follows.

An adaptive adversary can significantly delay the spread of the rumor, even if all graphs in the sequence are regular and have high vertex expansion. Thus Theorem 2 does not hold when the adversary is adaptive rather than oblivious. Proposition 2. An adaptive adversary can construct a sequence of regular isomorphic graphs G 1 , G 2 , . . ., each of which has constant vertex expansion, so that PUSH-PULL needs Ω( √ n) rounds with probability at least 1/2.

Proof In each round t ≥ 1, the adversary permutes the vertices in a way so that there is at most one clique that is not fully informed or fully uninformed (i.e., whose number of informed nodes is in the interval [

  Definition 1 (Friend). Let U ⊆ V be any subset. Then a node u is a friend of U in round t if, for κ as in Lemma 2, Pr |I t+κ ∩ U | ≥ d

	12 log n

  . Let G be the Cartesian product of a clique of size with every vertex in each clique connected to 3 vertices in other cliques. By [29, Lemma 4.2], G has constant vertex expansion. Every graph in the sequence G 1 , G 2 , . . . will be isomorphic to G.

	√ n vertices and is regular, with n with a 3-regular n + 2. Observe that G can be seen as a n. This graph has √ n • √ all vertices having degree expander graph of size √ √ n -1 + 3 = √ collection of √ n cliques of size √ n,

  1, √ n -1]). All other cliques contain either √ n informed nodes or none. Consider now a clique in which all √ n nodes are informed. The expected number of push transmissions that reach a node outside the clique is bounded by√ n • 3 √ n+2 ≤ 3.Similarly, the expected number of pull transmissions coming from outside is bounded by 3• √ n• 1 √ n+2 ≤ 3.Hence every clique which is completely informed contributes at most 6 to the expected number of newly informed node.For the single clique which is not fully informed nor fully uninformed, its contribution in expectation is at most 3 √ n newly informed nodes within the same clique and at most 6 newly informed nodes outside the clique. Hence,E [|I t+1 |] ≤ |I t | + (|I t |/

	√	n) • 6 + 3 •	√	n + 6 ≤ |I t | + 7 •	√	n,
	as long as |I t | ≤ n/2. Therefore, E |I t+ √	n/14-1 | ≤ 1+(	√	n/14-1)•7	√	n < n/2.
	Hence by Markov's inequality, Pr |I t+ √	n/14-1 | ≥ 2E |I t+ √	n/14-1 | ≤ 1/2.

The reason we expose one vertex at a time (rather than all at once), is that by stopping this process right after the min-volume of informed vertices has doubled,