George Giakkoupis
email: george.giakkoupis@inria.fr.

Tight Bounds for Rumor Spreading with Vertex Expansion

We establish a bound for the classic PUSH-PULL rumor spreading protocol on general graphs, in terms of the vertex expansion of the graph. We show that O(log 2 (n)/α) rounds suffice with high probability to spread a rumor from any single node to all n nodes, in any graph with vertex expansion at least α. This bound matches a known lower bound, and settles the natural question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.

Introduction

We study a classic randomized protocol for information dissemination in networks, known as (randomized) rumor spreading. The protocol proceeds in a sequence of synchronous rounds. 1 Initially, in round 0, an arbitrary node learns a piece of information, the rumor. This rumor is then spread iteratively to other nodes: In each round, every informed node (i.e., every node that learned the rumor in a previous round) chooses a random neighbor and sends the rumor to that neighbor. This is the PUSH version of the protocol. The PULL version is symmetric: In each round, every uninformed node contacts a random neighbor, and if this neighbor knows the rumor it sends it to the uninformed node. Finally, the PUSH-PULL algorithm is the combination of both: In each round, every node chooses a random neighbor to send the rumor to, if the node knows the rumor, or to request the rumor from, otherwise.

The above protocols were proposed almost thirty years ago, and have been the subject of extensive study, especially in the past decade. The most studied question concerns the number of rounds these protocols need to spread a rumor in various network topologies. It has been shown that O(log n) rounds suffice with high probability (w.h.p.) for several families for networks, from basic communication networks, such as complete graphs and hypercubes, to more complex structures, such as preferential attachment graphs modeling social networks (see the Related Work Section).

A main motivation for the study of rumor spreading is its application to algorithms for broadcasting in communication networks [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Feige | Randomized broadcast in networks[END_REF][START_REF] Karp | Randomized rumor spreading[END_REF]. Rumor spreading provides a scalable alternative to the flooding protocol (where each node sends the information to all its neighbors in a round), and a simpler and more robust alternative to deterministic solutions. The advantages of simplicity (each node makes a simple local decision in each round; no knowledge of the global topology is needed; no state is maintained), scalability (each node initiates just one connection per round), and robustness (the protocol tolerates random node/link failures without the use of error recovery mechanisms) make rumor spreading protocols particularly suited for today's distributed networks of massive-scale. Such networks, e.g., peer-to-peer, mobile ad-hoc, or sensor networks, are highly dynamic, suffer from frequent link and node failures, or nodes have limited computational, communication, and energy resources.

Another motivation for the study of rumor spreading protocols is that they provide intuition as to how information spreads in social networks [START_REF] Chierichetti | Rumor spreading in social networks[END_REF]. Understanding these simple rumor spreading protocols may lead to a better understanding of more realistic epidemic processes on social and other complex networks.

Our main focus in this paper is the connection between rumor spreading and graph expansion properties of networks. Many of the topologies for which rumor spreading is known to be fast have high expansion. Further, empirical studies indicate that social networks also have good expansion properties [START_REF] Eubank | Modelling disease outbreaks in realistic urban social networks[END_REF][START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF].

Several works have studied the relationship of rumor spreading with the conductance of the network graph [START_REF] Mosk | Fast distributed algorithms for computing separable functions[END_REF][START_REF] Chierichetti | Rumour spreading and graph conductance[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]. The conductance φ ∈ (0, 1] is a standard expansion measure defined roughly as the minimum ratio of the edges leaving a set of nodes over the total number of edges incident on these nodes (see Section 2). The main result of the above works is an upper bound of O(log(n)/φ) rounds for PUSH-PULL to inform all nodes w.h.p., for any n-node graph with conductance at least φ. This bound is tight, as there are graphs with diameter Ω(log(n)/φ) [START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF].

The above result has found applications to the design of various information dissemination protocols [START_REF] Censor | Fast information spreading in graphs with large weak conductance[END_REF][START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF][START_REF] Haeupler | Simple, fast and deterministic gossip and rumor spreading[END_REF]. These protocols rely on the fact that PUSH-PULL spreads information fast in subgraphs of high conductance, and they combine PUSH-PULL with more sophisticated rules on how each node chooses the neighbor to contact in each round. Those protocols achieve fast information spreading in a broader class of networks, and some even achieve for all graphs time bounds that are close (within poly-logarithmic factors) to the network diameter, which is the natural lower bound for information dissemination in networks.

More recently, another standard measure of expansion, the vertex expansion, has been studied in connection with rumor spreading. The vertex expansion α ∈ (0, 1] of a graph is, roughly, the minimum ratio of the neighbors that a set of nodes has (and are not in the set) over the size of the set. In general, vertex expansion is incomparable to conductance, as there are graphs with high vertex expansion but low conductance, and vice versa. (For an account of the differences between the two measures see [START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF].) The question of whether high vertex expansion implies fast rumor spreading (similar to high conductance) was highlighted as an interesting and challenging open problem in [START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF]. This problem was subsequently studied in [START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF][START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF], and the main result obtained was an upper bound for PUSH-PULL of O(log2.5 (n)/α) rounds w.h.p., for any graph with vertex expansion at least α. The precise bound is O(log n • log ∆ • log(2∆/δ)/α), where ∆ and δ are the maximum and minimum node degrees, respectively. Further, a lower bound of Ω(log n•log(∆)/α) was shown, assuming ∆/α ≤ n 1-for a constant > 0.

Our Contribution. Our main result is the following upper bound for PUSH-PULL in terms of vertex expansion, which matches the lower bound from [START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF].

Theorem 1.1. Let G = (V, E) be a graph with |V | = n nodes, maximum degree at most ∆, and vertex expansion at least α. For any such graph G and constant β > 0, with probability

1 -O(n -β ) PUSH-PULL informs all nodes of G in O log n • log(∆)/α rounds.
This result, together with the O(log(n)/φ) bound with conductance, resolve completely the natural question asked by Chierichetti, Lattanzi, and Panconesi [START_REF] Chierichetti | Rumor spreading in social networks[END_REF][START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF], on the relationship between rumor spreading and the two most standard measures of graph expansion.

A rough outline of the proof is as follows. Let S be the set of informed nodes after a given round, and let ∂S be the boundary of S, i.e., the set of nodes from V -S that have a neighbor in S. The proof defines a new simple measure of the expansion of S, called boundary expansion. If S has low boundary expansion, then we prove that a constant fraction of the boundary ∂S gets informed in an expected number of O(log ∆) rounds; this is the core argument of the proof. If, instead, S has high boundary expansion, then we have that an expected number of Ω(|∂S|) nodes from V -(S ∪ ∂S) are added to the boundary in a single round. It follows that a simple potential function Ψ(S) that counts 1 for each informed node and 1/2 for each node in the boundary, increases "on average" per round by at least Ω(|∂S|/ log ∆) = Ω(αΨ(S)/ log ∆); this is the right increase rate we need to show the O log n • log(∆)/α time bound.

Some of the arguments used in the proof may be of independent interest as tools for the analysis of rumor spreading. We demonstrated this by applying those arguments to show the following two smaller results.

1. Our first result serves as a "warm-up" for the main proof, as it uses a simpler version of the core argument of our analysis. We show that if a rumor is initially known to a subset of nodes that is a dominating set, then O(log n) rounds of PUSH-PULL suffice w.h.p. to inform the other nodes. (In fact we can use just PULL instead of PUSH-PULL.) 2 This result is somewhat relevant to problems in viral marketing [START_REF] Domingos | Mining the network value of customers[END_REF][START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]: It says that if we want to plant a rumor, or ad, in a (small) initial set of nodes in an arbitrary network, so that the remaining nodes get informed quickly by rumor spreading, then it suffices that the set we choose be a dominating set.

2. Our second result reuses the main argument from the proof of Result 1 above, and establishes that PUSH-PULL spreads a rumor in O(log n) rounds w.h.p. in any graph of diameter (at most) 2. This can be viewed as an extension to the classic result that rumor spreading takes O(log n) rounds in graphs of diameter 1, i.e., in complete graphs. We point out that unlike complete graphs, graphs of diameter 2 may have low expansion. Also the result does not hold for graphs of diameter 3. (The proof of the above result can be found in the appendix.)

Related Work. The first works on rumor spreading provided a precise analysis of PUSH on complete graphs [START_REF] Frieze | The shortest-path problem for graphs with random arc-lengths[END_REF][START_REF] Pittel | On spreading a rumor[END_REF]. Time bounds of O(log n) rounds were later proved for hypercubes and random graphs [START_REF] Feige | Randomized broadcast in networks[END_REF].

Other symmetric graphs similar to the hypercube in which rumor spreading takes O(log n + diam) rounds were studied in [START_REF] Elsässer | Broadcasting vs. mixing and information dissemination on Cayley graphs[END_REF]. A refined analysis for random graphs proving essentially the same time bound as for complete graphs was provided in [START_REF] Fountoulakis | Reliable broadcasting in random networks and the effect of density[END_REF], and extended to random regular graphs in [START_REF] Fountoulakis | Rumor spreading on random regular graphs and expanders[END_REF]. The authors of [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] studied rumor spreading on preferential attachment graphs, which are used as models for social networks, and showed that PUSH or PULL need polynomially many rounds, whereas PUSH-PULL needs only O(log 2 n) rounds. The last bound was subsequently improved to Θ(log n) [START_REF] Doerr | Social networks spread rumors in sublogarithmic time[END_REF]. Another class of random graphs used to model social networks was considered in [START_REF] Fountoulakis | Ultra-fast rumor spreading in social networks[END_REF], and it was shown that PUSH-PULL needs just Θ(log log n) rounds to inform all but an -fraction of nodes.

For general graphs, a bound of O(log(n)/Φ) was shown in [START_REF] Mosk | Fast distributed algorithms for computing separable functions[END_REF] for a version of PUSH-PULL with nonuniform probabilities for neighbor selection, where Φ is the conductance of the matrix of selection probabilities (which is different than the conductance φ of the graph). A comparable bound in terms of the mixing time of an appropriate random walk was shown in [START_REF] Boyd | Randomized gossip algorithms[END_REF]. For PUSH-PULL, a polynomial bound in log(n)/φ was shown in [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] via a connection to a spectral sparsification process. An improved, almost tight bound was shown in [START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF], and the tight O(log(n)/φ) bound was shown in [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF]. For PUSH or PULL this bound holds for regular graphs, but not for general graphs.

The bound for PUSH-PULL with conductance has been used in subsequent works [START_REF] Censor | Partial information spreading with application to distributed maximum coverage[END_REF][START_REF] Censor | Fast information spreading in graphs with large weak conductance[END_REF][START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF][START_REF] Haeupler | Simple, fast and deterministic gossip and rumor spreading[END_REF], mainly to argue that rumors spread fast in subgraphs of high conductance. A refinement of conductance, called weak conductance, which is greater or equal to φ was introduced in [START_REF] Censor | Partial information spreading with application to distributed maximum coverage[END_REF] and was related to the time for PUSH-PULL to inform a certain fraction of nodes. A gossip protocol for the problem in which every node has a rumor initially, and must receive the rumors of all other nodes was proposed in [START_REF] Censor | Fast information spreading in graphs with large weak conductance[END_REF]. The protocol alternates rounds of PUSH-PULL with rounds of deterministic communication, and guarantees fast information spreading in all graphs with high weak conductance. In [START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF][START_REF] Haeupler | Simple, fast and deterministic gossip and rumor spreading[END_REF] protocols for the same gossip problem were proposed that need only O(diam • polylog(n)) or O(diam + polylog(n)) rounds. One of these protocols is even deterministic [START_REF] Haeupler | Simple, fast and deterministic gossip and rumor spreading[END_REF]. Similar to the conductance-based bounds, we believe that the results with vertex expansion we present in this paper could potentially help in the design of new protocols for information dissemination.

Definitions and Notation

Throughout the paper we assume that graph G = (V, E) is connected, and |V | = n. For a node v ∈ V , we denote by N (v) the set of v's neighbors in G, and deg(v) = |N (u)| is the degree of v. By ∆ and δ we denote the maximum and minimum node degrees of G. For a set S ⊆ V , we denote by ∂S the boundary of S, that is, the set of neighbors of S that are not in S; formally, ∂S = {v ∈ V -S : N (v) ∩ S = ∅}. We will write S + to denote set S ∪ ∂S. A set S is a dominating set iff each node v ∈ V either belongs to S or has a neighbor in S, i.e., S + = V . The vertex expansion of a non-empty set S ⊆ V , and the vertex expansion of graph G are defined respectively as

α(S) = |∂S| |S| , α(G) = min 0<|S|≤ n 2 α(S).
The volume of a set S is vol(S) = v∈S deg (v). By E(S, V -S) we denote the set of edges with one endpoint from S and the other from V -S. The conductance of a non-empty set S ⊆ V , and the conductance of graph G are defined respectively as

φ(S) = |E(S, V -S)| vol(S) , φ(G) = min 0<vol(S)≤ vol(V ) 2 φ(S).
For any graph G we have that 0 < φ(G), α(G) ≤ 1, and

(δ/∆) • φ(G) ≤ α(G) ≤ ∆ • φ(G) [20].
3 Warm-up: Rumors Spread Fast from a Dominating Set

In this section we show the following result.

Theorem 3.1. Let S ⊆ V be a dominating set of G = (V, E), and suppose that all nodes u ∈ S know the rumor initially. Then PULL informs all remaining nodes in O(log n) rounds, with probability 1 -O(n -β ) for any constant β > 0.

We start with an overview of the proof. By a standard lemma on the symmetry between PUSH and PULL (Lemma 3.2), we have that in order to bound the time for PULL to spread a rumor from S to a given node u / ∈ S, it suffices to bound instead the time for PUSH to spread a rumor from u to some node in S. We bound the latter time as follows (Lemma 3.3). Let I u t be the set of informed nodes after t rounds of PUSH, when the rumor starts from u. We consider the earliest round τ for which the expected growth of I u t in the next round τ + 1 is smaller than by a constant factor > 0, i.e.,

E[|I u τ +1 -I u τ | | I u τ ] < •|I u τ |.
We argue that τ = O(log n) w.h.p. (Claim 3.4), which is intuitively clear, as up to round τ the number of informed nodes increases by a constant factor in expectation per round. Next we bound the harmonic mean of the degrees of nodes in I u τ ; precisely, we show that

v∈I u t 1 deg(v) = Ω(1) (Claim 3.5). If I u τ ∩ S = ∅ then each node from I u τ
has some neighbor in S, and from the above bound on the degrees it follows that in a round, the probability that some node from I u τ pushes the rumor to a neighbor in S is Ω(1). Thus, within O(log n) rounds after round τ , the rumor has reached some node in S w.h.p.

Next we give the detailed proof.

Lemma 3.2. Let T push (V 1 , V 2 ), for V 1 , V 2 ⊆
V , be the number of PUSH rounds until a rumor initially known to all u ∈ V 1 (and only them) spreads to at least one v ∈ V 2 ; define

T pull (V 1 , V 2 ) similarly. For any V 1 , V 2 ⊆ V , the random variables T push (V 1 , V 2 ) and T pull (V 2 , V 1 )
have the same distribution.

The proof of Lemma 3.2 is essentially the same as that of [START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF]Lemma 3], and is therefore omitted. Next we state our main lemma; its proof is given in Section 3.1. Lemma 3.3. Let S be a dominating set and u ∈ V -S. Using PUSH, a rumor originated at u spreads to at least one node v ∈ S in O(log n) rounds, with probability 1 -O(n -β ) for any constant β > 0. Theorem 3.1 follows now easily: From Lemma 3.3 we obtain that a rumor originated at a given u ∈ V -S spreads to at least one v ∈ S after O(log n) rounds of PUSH, with probability 1 -O(n -β-1 ). Lemma 3.2 then implies that a rumor known to all v ∈ S reaches u after O(log n) rounds of PULL, with the same probability, 1 -O(n -β-1 ). Applying now the union bound over all u ∈ V -S yields the theorem.

3.1 Proof of Lemma 3.3. Let I u t be the set of informed nodes after t rounds of PUSH, when the rumor starts from node u ∈ V -S. Let τ be the earliest round such that the expected increase of I u t in the next round is smaller than

• |I u t |, i.e., τ = min{t : E[|I u t+1 | | I u t ] < (1 + ) • |I u t |},
for some positive constant < 1.

Claim 3.4. With probability 1 -n -β , τ = O(log n). Proof. Let X t , for t ≥ 1, be a 0/1 random variable that is 1 iff |I u t | ≥ (1 + /2) • |I u t-1 | or t ≥ τ . Then for any k, (3.1) Pr(τ ≤ k) ≥ Pr k t=1 X t ≥ log 1+ /2 n , because: if τ > k, then |I u k | ≥ (1 + /2) k t=1 Xt and thus k t=1 X t ≤ log 1+ /2 (|I u k |) < log 1+ /2 n; and taking the contrapositive gives that k t=1 X t ≥ log 1+ /2 n implies τ ≤ k.
Next we show that for any t,

(3.2) Pr(X t = 1 | X 1 . . . X t-1 ) ≥ /2 1 -/2 .
Fix the outcome of the first t -1 rounds, and suppose that τ > t -1. (Otherwise, we have X t = 1 and the inequality above holds trivially.) We bound Pr(X t = 0) using Markov's Inequality:

Pr(X t = 0) ≤ Pr(|I u t | < (1 + /2) • |I u t-1 |) = Pr(2 |I u t-1 | -|I u t | > (1 -/2) • |I u t-1 |) ≤ 2 |I u t-1 | -E[|I u t |] (1 -/2) • |I u t-1 |
, by Markov's Ineq.

Further, since τ > t -1 we have from τ 's definition that

E[|I u t |] ≥ (1 + ) • |I u t-1 |. Hence, Pr(X t = 0) ≤ 2 |I u t-1 | -(1 + ) • |I u t-1 | (1 -/2) • |I u t-1 | = 1 - 1 -/2 ,
and thus Pr(

X t = 1) ≥ /2 1-/2 . From Eq. (3.2), it follows that k t=1 X t stochasti- cally dominates binomial random variable B k, /2
1-/2 . Thus, using Chernoff bounds we obtain Pr

k t=1 X t ≥ log 1+ /2 n ≥ Pr B k, /2 1-/2 ≥ log 1+ /2 n ≥ 1 -n -β for k ≥ c log n,
for a sufficiently large constant c. From this and Eq. (3.1), the claim follows.

The next claim bounds the harmonic mean of the degrees of nodes v ∈ I u τ .

Claim 3.5. If E[|I u t+1 | | I u t ] < (1 + ) • |I u t | then v∈I u t 1 deg(v) ≥ 1 - √ . 3
Proof. The proof is by contrapositive. Fix I u t and let k = |I u t |. For 1 ≤ i ≤ k, let u i be the i-th node in I u t , and let d i = deg(u i ). We will assume that

k i=1 1/d i < 1 - √ and prove that E[|I u t+1 |] ≥ (1 + )k.
We count the number of uninformed nodes that in round t + 1 receive exactly one copy of the rumor. This is clearly a lower bound on the number of nodes that get informed in round t+1.

Let d i = |N (u i )∩I u t | be the number of neighbors that u i has in I u t .
The probability that in round t + 1 node u i pushes the rumor to some uninformed node is then 1 -d i /d i . And if this happens, the probability that the recipient node does not receive the rumor from any other node in the round is at least

j =i (1 -1/d j ) ≥ 1 - j =i (1/d j ) ≥ 1 -(1 - √ ) = √ .
Thus the probability that u i sends the rumor to an uninformed node that does not receive another copy of the rumor is at least (1

-d i /d i ) √ .
Hence, the expected number of uninformed nodes that receive exactly one rumor copy in round t + 1 is at least

k i=1 (1 -d i /d i ) √ . And since k i=1 (1 -d i /d i ) = k - k i=1 (d i /d i ) ≥ k - k i=1 (k/d i ) ≥ k -k(1 - √ ) = k √ ,
we obtain a lower bound of k √ • √ = k on the expected number of uninformed nodes that receive exactly one copy of the rumor in round t + 1. Hence, the same lower bound holds for the total number on nodes informed in the round, and we conclude that

E[|I u t+1 |] ≥ (1 + )k.
Using Claim 3.5 it is easy to show an O(log n) bound w.h.p. on the number of additional rounds after round τ , until the rumor spreads to at least one node from S: Suppose that I u τ = U for some set U ⊆ V -S. (If U V -S then some node from S is already informed.) Each v ∈ U has at least one neighbor in the dominating set S, and thus the probability that none of these nodes pushes the rumor to a neighbor in S in a given round t > τ , is upper bounded by Another application of the same proof idea is described in Section A of the appendix.

Proof of the Main Result

In this section we show our main result, Theorem 1.1. We start with an overview of the proof. Let I t denote the set of informed nodes after the first t rounds. We study the growth of the quantity Ψ The first case is when the boundary expansion of I t is low (upper-bounded by a constant h < 1). This is the more challenging case, and is the core of our analysis. Our main lemma in this case is Lemma 4.3, which establishes that a constant fraction of the boundary ∂I t gets informed in an expected number of O(log ∆) rounds. The proof builds upon and extends the ideas used in the proof of Theorem 3.1. We note that in the setting of Theorem 3.1, the boundary expansion of the set S of informed nodes is zero.

t := |I t | + |∂I t |/2 = (|I t | + |I + t |)/2.
The second case is when the boundary expansion of I t is high (lower-bounded by a constant h > 0). Then from our definition of boundary expansion it follows that the expected number of nodes from ∂(I + t ) that have an informed neighbor after the next round is Ω(

|∂I t |), i.e., E[|I + t+1 -I + t | | I t ] = Ω(|∂I t |).
Our main lemma in this case is Lemma 4.10, which turns the above lower bound on the expected per round growth of I + t into an upper bound on the expected number of rounds until I + t grows by some quantity b • |∂I t |, which depends on the degrees of nodes in ∂I t . Finally we bound the expected time needed to double Ψ t (Lemma 4.12), by combining the results of the two cases above and using an inductive argument.

The rest of this section is structured as follows. We define the measure of boundary expansion in Section 4.1. In Section 4.2 we lower-bound the growth of I t when boundary expansion is low. In Section 4.3 we lower-bound the growth of I + t when boundary expansion is high. And in Section 4.4 we put the pieces together to complete the proof of Theorem 1.1.

Boundary Expansion.

Definition 4.1. Let S ⊂ V be a non-empty set. Let U be a random subset of ∂S such that each node u ∈ ∂S belongs to U with probability 1/ deg(u) independently of the other nodes. The boundary expansion h(S) of S is the ratio of the expected number of nodes v ∈ ∂(S + ) that have some neighbor in U , over the size of ∂S, i.e.,

h(S) = E [|{v ∈ ∂(S + ) : N (v) ∩ U = ∅}|] /|∂S|.
It is 0 ≤ h(S) < 1. The lower bound of 0 is matched iff S is a dominating set; and the upper bound holds because E [|{v ∈ ∂(S + ) : N (v) ∩ U = ∅}|] is upperbounded by the expected number of the edges between U and ∂(S + ), which is

u∈∂S |N (u) -S + |/deg(u) ≤ u∈∂S (deg(u) -1)/deg(u) < |∂S|.
Intuitively, h(S) is small if for many nodes u ∈ ∂S, we have that either just a small fraction of u's neighbors belong to ∂(S + ), or, if u has a lot of neighbors in ∂(S + ), then a large fraction of them are common neighbors to many nodes from ∂S.

If I t = S then h(S) • |∂S| is a lower bound on the expected number of new nodes that have some informed neighbor after round t + 1, i.e., (4.3)

E[|I + t+1 -I + t | | I t = S] ≥ h(S) • |∂S|,
as each node u ∈ ∂I t pulls the rumor from I t in round t + 1 with probability at least 1/ deg(u). In Section 4.3 we will need the following refined definition, which describes the boundary expansion of S contributed by a given subset T of ∂S. For T = ∂S the above definition is identical to Definition 4.1, i.e., h ∂S (S) = h(S).

The Case of Low Boundary Expansion.

In this section we prove the following result, which is the core lemma of our analysis. Lemma 4.3. Suppose that I t = S for some set S ⊂ V with boundary expansion h(S) ≤ h , where 0 ≤ h < 1 is an arbitrary constant. There is a constant = ( h ) > 0 such that the expected number of rounds until • |∂S| nodes from ∂S get informed is O(log ∆).

We start with an overview of the proof. Similar to the proof of Theorem 3.1, to bound the time for a given node u ∈ ∂S to get informed, we bound instead the time for a rumor originated at u to spread to some node from S. Establishing this bound, however, is more difficult now than in the setting of Theorem 3.1. Recall that in the proof of Theorem 3.1, to bound the time until a rumor from u ∈ ∂S reaches S, we first bound the time when the set I u t of informed nodes stops growing by a constant expected factor in each round, and then bound the harmonic mean of the degrees of nodes in I u t at that time; the bound on the degrees implies that if I u t ∩ S = ∅, then with large probability some node from I u t will send the rumor to a neighbor in S. This last statement depends critically on the assumption that S is a dominating set, and thus every node from I u t has a neighbor in S. This in not the case, however, in the current setting.

To tackle this problem we consider a "restricted" rumor spreading process, on an induced subgraph of G. We identify a set of nodes participating in rumor spreading (Definition 4.4), such that, intuitively, each participating node has at least a constant probability to contact or be contacted by another participating node in a round. Only nodes from S + or ∂(S + ) can be participating. Participating nodes from S + are active, i.e., they initiate a connection to a random neighbor in each round, while participating nodes from ∂(S + ) are passive, i.e., they accept connections from active neighbors but do not initiate connections to random neighbors. Using the assumption that S has low boundary expansion we show that at least a constant fraction of ∂S is participating (Lemma 4.5). For each participating node u ∈ ∂S then we show that an expected number of O(log ∆) rounds suffice for a rumor originated at u to spread to some node from S (Lemma 4.6). The proof of this last result follows a similar outline to that of Lemma 3.3, although it is a bit more involved.

Below, in Section 4.2.1 we formally define the set of participating nodes and show that a constant fraction of ∂S is participating. Then in Section 4.2.2 we bound the time for a rumor originated at a participating node from ∂S to reach S. Finally, we complete the proof of Lemma 4.3 in Section 4.2.3.

Participating Nodes.

Definition 4.4. The set P of participating nodes is a maximal subset of V such that for any u ∈ P and for

A := P ∩ S + , |N (u) ∩ P | deg(u) + v∈N (u)∩A 1 deg(v) ≥ p , if u ∈ A; (4.4) v∈N (u)∩A 1 deg(v) ≥ p , if u ∈ P -A, (4.5)
where 0 < p < (1h )/3 is a constant;4 set A is the set of active nodes, and P -A is the set of passive nodes.

It follows from this definition that all participating nodes belong to S + ∪ ∂(S + ); the ones in S + are active, and those in ∂(S + ) are passive. Intuitively, P is defined such that each participating node has at least a constant probability to contact or be contacted by another participating node in a round. The term |N (u) ∩ P |/ deg(u) in Eq. (4.4) is the probability that active node u chooses a participating neighbor in a round. In Eq. (4.5) we do not have this term because, as mentioned earlier, passive nodes do not initiate connections. The sum that is common in both equations adds the probabilities of the events that u is chosen by v, for all active neighbors v of u. If this sum is small (bounded by a constant), then it is of the same order as the probability that u is chosen by at least one of its active neighbors.

The set P can be obtained by a simple procedure that recursively removes from V all nodes that do not satisfy (4.4) or (4.5). (This proves also that P is unique.) Formally, we start with set P 0 = V . In the i-th step of the procedure we obtain set P i by removing from

P i-1 all nodes u ∈ A i-1 := P i-1 ∩ S + for which |N (u)∩P i-1 |/ deg(u)+ v∈N (u)∩Ai-1 1/ deg(v) < p , and all nodes u ∈ P i-1 -A i-1 for which v∈N (u)∩Ai-1 1/ deg(v) < p .
Clearly, the procedure finishes after at most n steps. Let P * := P i for the last step i. We argue now that P * = P . Because of the maximality of P , it suffices to show that P ⊆ P * : Suppose, for contradiction, that P P * , and consider the first step i for which P P i . Then, we have P ⊆ P i-1 and A ⊆ A i-1 , and some node u ∈ P is removed from

P i-1 in step i. If u ∈ A then it follows from (4.4) that |N (u) ∩ P i-1 |/ deg(u) + v∈N (u)∩Ai-1 1/ deg(v) ≥ p ,
which contradicts the assumption that u is removed in step i. Similarly, if u ∈ P -A, then it follows from (4.5) that v∈N (u)∩Ai-1 1/ deg(v) ≥ p , which again contradicts that u is removed.

We observe that if a subset of V is used as the starting set P 0 (instead of having P 0 = V ), then the set obtained by the procedure is a subset of P .

We will now show that at least a constant fraction of nodes u ∈ ∂S is participating.

Lemma 4.5. |∂S ∩ P | ≥ 1 - h (1-p )(1-2 p ) • |∂S|. 5
Proof. We use a potential function argument. We consider the recursive procedure given above to obtain P , and define a potential Φ i after each step i. This potential is a non-negative quantity. Further, for an appropriate choice of the initial set P 0 for the procedure, we achieve that the potential function is non-increasing. 5 From the assumption in Definition 4.4 that p < (1h )/3, it follows that 1 -

h (1-p )(1-2 p ) > 0.
For this P 0 we show that the potential Φ 0 before the first step satisfies Φ 0 ≤ h 1-p • |∂S|. We also show that for each node u ∈ A i-1 that is removed from P i-1 in step i, the potential drops by at least 1 -2 p , and the removal of a node u / ∈ A i-1 does not increase the potential. It follows that the total number of nodes u ∈ S + removed in all steps is bounded by Φ 0 /(1 -2 p ). Thus, the same bound holds for the nodes u ∈ ∂S removed, i.e., |∂S| -|∂S ∩ P | ≤ Φ 0 /(1 -2 p ). Rearranging and using that Φ 0 ≤ h 1-p • |∂S| yields the claim. Next we fill in the details omitted in the outline above. We start with the definition of the potential function. Intuitively, the potential Φ i after step i measures the probability "wasted" in connections between participating and non-participating nodes. It has two components. The first component, Φ i,1 , is the sum over all u ∈ A i of the probability that u chooses a neighbor v / ∈ P i ; the second component, Φ i,2 , is the sum over all u ∈ S + -A i of the probability that u would choose a neighbor v ∈ P i if u were active. We give two equivalent formulas for each of Φ i,1 , Φ i,2 , to be used later on.

Φ i,1 = u∈Ai v∈N (u)-Pi 1 deg(u) = u / ∈Pi v∈N (u)∩Ai 1 deg(v) ; Φ i,2 = u∈S + -Ai v∈N (u)∩Pi 1 deg(u) = u∈Pi v∈N (u)∩(S + -Ai) 1 deg(v) .
Then, Φ i = Φ i,1 + Φ i,2 .

The starting set P 0 we use consists of all nodes u ∈ S + plus those u ∈ ∂(S + ) for which (4.6)

v∈N (u)∩∂S 1 deg(v) ≥ 2 p .
The above condition is similar to (4.5), but the threshold is twice that in (4.5). We show now that

(4.7) Φ 0 ≤ h 1 -p • |∂S|.
Let B be the set of nodes from ∂(S + ) that do not satisfy (4.6), i.e.,

B = u ∈ ∂(S + ) : v∈N (u)∩∂S 1 deg(v) < 2 p .
We have P 0 = S + ∪ (∂(S + ) -B) and A 0 = S + . Substituting these values to the second formula for Φ i,1 and the first one for Φ i,2 yields

Φ 0 = Φ 0,1 + Φ 0,2 = u∈B v∈N (u)∩∂S 1 deg(v) + 0. (4.8)
Next we relate the double sum above with h . From the definition of h(S) (Definition 4.1), it follows

h(S) = 1 |∂S| v∈∂(S + )   1 - u∈N (v)∩∂S 1 - 1 deg(u)   .
Since the left side is at most h , and replacing ∂(S + ) by B ⊆ ∂(S + ) on the right side can only decrease the sum's value, it follows

h ≥ 1 |∂S| u∈B   1 - v∈N (u)∩∂S 1 - 1 deg(v)   .
Further, for any u ∈ B, the product on the right side is

v∈N (u)∩∂S 1 - 1 deg(v) ≤ e -v∈N (u)∩∂S 1 deg(v) ≤ 1 - v∈N (u)∩∂S 1 deg(v) + 1 2   v∈N (u)∩∂S 1 deg(v)   2 ≤ 1 -   v∈N (u)∩∂S 1 deg(v)   (1 -p ), as v∈N (u)∩∂S 1/ deg(v) < 2 p for u ∈ B. It follows h ≥ 1 -p |∂S| u∈B   v∈N (u)∩∂S 1 deg(v)   (4.8) = (1 -p )Φ 0 |∂S| ,
and rearranging yields Eq. (4.7). It remains to show that for each node u ∈ A i-1 that is removed in step i, the potential decreases by at least 1 -2 p , and for each node u ∈ P i-1 -A i-1 removed the potential does not increase. W.l.o.g. we assume that only one node u ∈ P i-1 is removed in step i. (If k > 1 nodes should be removed we just break step i into k sub-steps.)

First, suppose that a node u

∈ P i-1 -A i-1 is removed in step i. Then P i = P i-1 -{u} and A i = A i-1 .
From the second formulas for Φ i,1 and Φ i,2 we obtain

Φ i,1 -Φ i-1,1 = v∈N (u)∩Ai 1 deg(v) =: φ inc , Φ i,2 -Φ i-1,2 = - v∈N (u)∩(S + -Ai-1)

deg(v)

=: -φ dcr .

Since A i = A i-1 we have

φ inc + φ dcr = v∈N (u)∩S + 1 deg(v) ≥ 2 p ,
where the inequality holds because of Eq. (4.6), since u ∈ ∂(S + ). Further, since u is removed in step i, it satisfies the condition v∈N (u)∩Ai-1 1/ deg(v) < p , which yields φ inc < p . From the above two inequalities on φ inc and φ dcr we get φ inc < p < φ dcr , and thus, Φ i -Φ i-1 = φ inc -φ dcr < 0. Suppose now that a node u ∈ A i-1 is removed. Then P i = P i-1 -{u} and A i = A i-1 -{u}, and

Φ i,1 -Φ i-1,1 = - v∈N (u)-Pi-1 1 deg(u) φ1 + v∈N (u)∩Ai 1 deg(v) φ2 , Φ i,2 -Φ i-1,2 = v∈N (u)∩Pi 1 deg(u) φ3 - v∈N (u)∩(S + -Ai-1) 1 deg(v) .
In the expression for φ 2 we can replace A i by A i-1 , as u /

∈ N (u) and thus N (u)

∩ A i = N (u) ∩ A i-1 .
Similarly, in the expression for φ 3 we can replace P i by P i-1 . It follows that φ 1 + φ 3 = v∈N (u) 1/ deg(u) = 1, and also φ 2 + φ 3 < p as otherwise u would not be removed in step i. Thus,

Φ i -Φ i-1 = (Φ i,1 -Φ i-1,1 ) + (Φ i,2 -Φ i-1,2 ) ≤ -φ 1 + φ 2 + φ 3 ≤ -φ 1 + 2φ 2 + φ 3 = -(φ 1 + φ 3 ) + 2(φ 2 + φ 3 ) < -1 + 2 p .
This completes the proof of Lemma 4.5.

Spreading a Rumor from an Active Node.

We prove now the following lemma, which bounds the expected time until a rumor originated at some active node u ∈ ∂S reaches S. This result is similar to Lemma 3.3, but holds only for active nodes rather than all u ∈ ∂S, and assumes PUSH-PULL rather than just PUSH. The proof analyzes the spread of u's rumor on the subgraph induced by the set P of participating nodes. Each active node (i.e., from set A = P ∩S + ) chooses a random neighbor in each round, and contacts that neighbor if it is participating. Passive nodes (i.e, from set P -A = P ∩ ∂(S + )) do not choose neighbors; they communicate only with the active nodes that contact them in each round.

Let I u t be the set of informed nodes after t rounds. Similar to the proof of Lemma 3.3, we define Proof. Let X t , for t ≥ 1, be a 0/1 random variable that is 1 iff

τ = min{t : E[|I u t+1 | | I u t ] < (1 + ε) • |I u t | ∨ |I u t | ≥ ∆ 2 }, where 0 < ε < p /2
|I u t | ≥ (1 + ε/3) • |I u t-1 | or t ≥ τ . Further, let τ = min i : i t=1 X t ≥ 2 log 1+ε/3 ∆ .
We have

(4.9) E[τ ] ≤ E[τ ], because: for any k, if τ > k then |I u k | ≥ (1 +ε/3) k t=1 Xt
and |I u t | < ∆ 2 , and thus,

k t=1 X t ≤ log 1+ε/3 (|I u k |) < log 1+ε/3 (∆ 2 ) = 2 log 1+ε/3 ∆, which implies τ > k.
Hence, for any k we have that τ > k implies τ > k, and thus

E[τ ] ≤ E[τ ].
Next we show that for any t,

(4.10) Pr(X t = 1 | X 1 . . . X t-1 ) ≥ 1 -e -ε 2 /18 .
Fix the outcome of the first t -1 rounds, and suppose that τ > t -1. (Otherwise, X t = 1 and the inequality above holds trivially.) We have

Pr(X t = 0) ≤ Pr(|I u t | < (1 + ε/3) • |I u t-1 |).
We will bound now the probability on the right side.

Observe that

|I u t | = v∈V Y v
, where Y v is the indicator variable of the event that v ∈ I u t . The random variables Y v are not independent: if two participating nodes v, v / ∈ I u t-1 have a common neighbor w ∈ I u t-1 , then the events that w pushes the rumor to v or to v in round t are correlated. However, the variables Y v are negatively associated [START_REF] Devdatt | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF]; this follows from [START_REF] Devdatt | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF]Example 4.5]. 6 Negative association allows us to use standard Chernoff bounds to bound Pr(

|I u t | < (1 + ε/3) • |I u t-1 |): Since 6
The example cited refers to a general balls and bins model. In our case: bins are the nodes, and for each informed node v we place a ball to a random neighbor of v, while for each uninformed node v we place a ball to v iff a randomly chosen neighbor of v is informed. The example then shows that the number of balls in the bins are negatively associated.

we have τ > t -1, it follows from τ 's definition that

E[|I u t |] ≥ (1 + ε) • |I u t-1 |, and
Pr(|I u t | < (1 + ε/3) • |I u t-1 |) ≤ Pr |I u t | < (1 + ε/3) • E[|I u t |] 1 + ε ≤ Pr(|I u t | < (1 -ε/3) E[|I u t |]) ≤ e -(ε/3) 2 E[|I u t |]/2 ≤ e -ε 2 /18 .
Hence, Pr(X t = 1) = 1 -Pr(X t = 0) ≥ 1 -e -ε 2 /18 . From Eq. (4.10) it follows that τ is stochastically dominated by a negative-binomial random variable that counts the number of independent bernoulli trials until we have 2 log 1+ε/3 ∆ successes, and each trial has a success probability of 1 -e -ε 2 /18 . Therefore, E[τ ] ≤ (2 log 1+ε/3 ∆)/(1 -e -ε 2 /18 ) = O(log ∆). From this and Eq. (4.9), the claim follows.

The next result is an analogue of Claim 3.5, and bounds the harmonic mean of the degrees of active nodes in

I u τ Claim 4.8. If E[|I u t+1 | | I u t ] < (1+ε)•|I u t | or |I u t | ≥ ∆ 2 , then v∈I u t ∩S + 1 deg(v) ≥ ζ, where ζ = ( p -2ε)/3. Proof. First we show that if |I u t | ≥ ∆ 2 holds then v∈I u t ∩S + 1/ deg(v) ≥ ζ-
this is the easier case. Observe that each informed inactive node w ∈ I u t ∩ ∂(S + ) has at least one informed neighbor v in ∂S, namely, the one that pushed the rumor to w. Further, each v ∈ ∂S has at most deg(v) -1 ≤ ∆ -1 neighbors in ∂(S + ) (and at least one in S). It follows that if

|I u t | ≥ ∆ 2 , then at least ∆ of the nodes in I u t belong to S + , i.e., |I u t ∩S + | ≥ ∆, because otherwise, |I u t | = |I u t ∩ S + | + |I u t ∩ ∂(S + )| ≤ |I u t ∩ S + | + |I u t ∩ S + | • (∆ -1) = |I u t ∩ S + | • ∆ < ∆ 2 . And if we have |I u t ∩ S + | ≥ ∆, then v∈I u t ∩S + 1/ deg(v) ≥ |I u t ∩ S + |/∆ ≥ ∆/∆ = 1 > ζ. It remains to show that if E[|I u t+1 | | I u t ] < (1+ε)•|I u t | then v∈I u t ∩S + 1/ deg(v) ≥ ζ.
In the rest of the proof we assume that v∈I u t ∩S + 1/ deg(v) < ζ, and will prove that

E[|I u t+1 | | I u t ] ≥ (1 + ε) • |I u t |.
The proof builds upon the ideas used for Claim 3.5. Similar to Claim 3.5, we count the number of uninformed nodes to which exactly one copy of the rumor is pushed in round t + 1 (these nodes may also receive a second copy via pull). Further, we count the number of uninformed nodes that pull the rumor in that round. The sum of the above two numbers is then a lower bound on twice the total number of nodes informed in round t+1. We lower-bound the expectation of this sum using the definition of active and passive nodes.

Fix

I u t . For each informed active node v ∈ I u t ∩ S + , let β(v) = |N (v) ∩ (P -I u t )|/ deg(v)
be the fraction of v's neighbors that are participating and uninformed. Then the probability that v pushes the rumor to such a neighbor and no other node pushes the rumor to the same neighbor is lower-bounded by

β(v) • v ∈I u t ∩S + 1 -1 deg(v ) ≥ β(v) •   1 - v ∈I u t ∩S + 1 deg(v )   ≥ β(v) • (1 -ζ). Further, for each informed node v ∈ I u t , let γ(v) = v ∈N (v)∩(A-I u t ) 1/ deg(v )
be the expected number of uninformed active nodes that pull the rumor from v. It follows that the expected total number of nodes that get informed in round t + 1 is (4.11)

E |I u t+1 | -|I u t | ≥ 1 2 v∈I u t ∩S + β(v)•(1-ζ)+ 1 2 v∈I u t γ(v).
Next we bound the above sums of β(v) and γ(v) using Definition 4.4. For each informed active node v ∈ I u t ∩ S + , we have

|N (v) ∩ P | deg(v) = |N (v) ∩ I u t | deg(v) + β(v) ≤ |I u t | deg(v) + β(v),
and

v ∈N (v)∩A 1 deg(v ) = v ∈N (v)∩(A∩I u t ) 1 deg(v ) + γ(v) ≤ v ∈A∩I u t 1 deg(v ) + γ(v) < ζ + γ(v). Then (4.4) yields |I u t |/ deg(v) + β(v) + ζ + γ(v) ≥ p .
Summing over all v ∈ I u t ∩ S + and rearranging gives

v∈I u t ∩S + β(v) + γ(v) ≥ |I u t ∩ S + | • ( p -ζ) - v∈I u t ∩S + |I u t | deg(v) ≥ |I u t ∩ S + | • ( p -ζ) -|I u t | • ζ.
Next, for each informed passive node v ∈ I u t -S + , we obtain similarly using (4.5) that ζ + γ(v) ≥ p , and summing over all such v gives

v∈I u t -S + γ(v) ≥ |I u t -S + | • ( p -ζ).
Adding the last two inequalities above yields

v∈I u t ∩S + β(v) + v∈I u t γ(v) ≥ |I u t | • ( p -ζ) -|I u t | • ζ = |I u t | • ( p -2ζ
). From this and (4.11) it follows

E[|I u t+1 | -|I u t |] ≥ 1 2 (1 -ζ) • |I u t | • ( p -2ζ) ≥ ε • |I u t |,
where the last inequality is obtained using that ζ = ( p -2ε)/3. This completes the proof of Claim 4.8.

Using Claim 4.8 it is easy to show an O(1) bound on the expected number of additional rounds after round τ , until some node in S gets informed: Fix I u τ and suppose that I u τ ∩ S = ∅ (otherwise some node from S is already informed). Then I u τ ∩ S + = I u τ ∩ ∂S, and Claim 4.8 gives

v∈I u t ∩∂S 1/ deg(v) ≥ ζ. Since each node v ∈ I u
t ∩ ∂S has at least one neighbor from S, the probability that none of these nodes pushes the rumor to a neighbor from S in a given round t > τ , is at most

v∈I u t ∩∂S (1 -1/ deg(v)) ≤ e -v∈I u t ∩∂S 1/ deg(v) ≤ e -ζ .
It follows that the expected number of rounds until some of the nodes v ∈ I u τ ∩ ∂S pushes the rumor to a node in S is at most 1/(1 -e -ζ ) = O(1). Combining this with Claim 4.7 gives an upper bound of O(log ∆) on the expected number of rounds until some node from S gets informed, concluding the proof of Lemma 4.6.

4.2.3

Completing the Proof of Lemma 4.3. The next standard lemma is the analogue of Lemma 3.2 for PUSH-PULL. Versions of this result can be found, e.g., in [START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF][START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF][START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF]. Lemma 4.9. Let T (V 1 , V 2 ) be the number of PUSH-PULL rounds until a rumor initially known to all u ∈ V 1 (and only them) spreads to at least one v ∈ V 2 . Then

T (V 1 , V 2 ) and T (V 2 , V 1 ) have the same distribution.
From the lemma above and Lemma 4.6, it follows that the rumor spreads from S to a given u ∈ ∂S ∩ P in an expected number of at most = O(log ∆) rounds. Markov's Inequality then gives that in 2 rounds node u has been informed with probability at least 1/2, and from the linearity of expectation, in 2 rounds at least 1/2 of the nodes from ∂S ∩ P have been informed in expectation. Using Markov's again we obtain that in 2 rounds more than 3/4 of the nodes from ∂S ∩ P are still uninformed with probability at most (1/2)/(3/4) = 2/3. Thus, 1/4 of the nodes from ∂S ∩ P get informed within 2 rounds with probability at least 1/3, and this implies that 1/4 of the nodes from ∂S ∩ P get informed in an expected number of most 2 /(1/3) = 6 steps. From this and Lemma 4.5, which states that |∂S ∩ P | = Θ(|∂S|), we obtain Lemma 4.3.

4.3

The Case of High Boundary Expansion. In this section we show the following result. We start with an overview of the proof. Eq. (4.3) gives that the expected number of nodes from ∂(S + ) that have some informed neighbor after one round is at least h(S) • |∂S| ≥ h • |∂S| = Ω(|∂S|). To prove the lemma we need to bound also the variance of those nodes. Intuitively, the variance will be higher when the degrees of nodes in ∂S are larger, and in this case larger values for b are needed to satisfy the lemma.

The proof distinguishes three cases. The first case is when the larger contribution to the boundary expansion of S is from nodes u ∈ ∂S of degree deg(u) ≤ c•|∂S|, for some constant c. Formally, we have h T (S)

≥ h /3, for T = {u ∈ ∂S : deg(u) ≤ c • |∂S|} (see Definition 4.2).
Using the second moment method, we show that after one round of PULL we have with probability Ω(1) that Ω(|∂S|) nodes from ∂(S + ) have some informed neighbor. It follows that the expected number of rounds until Θ(|∂S|) nodes from ∂(S + ) have some informed neighbor is O(1), thus the lemma holds for b = Θ(1).

The next case is when the larger contribution to h(S) comes from nodes u ∈ ∂S of degree between c • |∂S| and |S|. We argue that for some degree k from that range, the number of nodes u ∈ ∂S with degree k ≤ deg(u) ≤ 2k and Θ(k) neighbors in ∂(S + ) is at least Ω(|∂S|/ log ∆). Then the probability of informing at least one such u in a round of PULL is p = Ω(|∂S|/(k log ∆)). It follows that the expected number of rounds until Θ(k) nodes from ∂(S + ) have some informed neighbor is 1/p = O((k/|∂S|) log ∆), thus the lemma holds for b = Θ(k/|∂S|).

The last case is when the largest contribution to h(S) is from nodes u ∈ ∂S of degree deg(u) ≥ d * , where d * = max{|S|, c|∂S|}. We argue that Ω(|∂S|) nodes u ∈ ∂S have Ω(d * ) neighbors in ∂(S + ). As the degree of those nodes u may be very large, we rely on push transmissions to inform them. Using that the degree of any node from S is bounded by |S + |, we argue that in one round of PUSH, at least one of the above nodes u is informed with probability p = Ω(|∂S|/|S + |). We give the detailed proof next.

-I + t | ≥ εk/2 ≥ 1 -e -ε|∂S| 4kl = Ω |∂S| kl . (c) If h T3 (S) ≥ ε then for k = max{|S|, c|∂S|}, Pr |I + t+1 -I + t | ≥ εk/2 ≥ 1 -e -εc|∂S| 4k = Ω |∂S| k .
Proof. (a) Before round t + 1, we fix for each node u ∈ T 1 a neighbor v u ∈ S. Let U T1 be the set of nodes u ∈ T 1 that get informed in round t + 1 by pulling the rumor from their neighbor u v . Further, let f T1 be the number of nodes from ∂(S + ) that have a neighbor in U T1 . Clearly, |I + t+1 -I + t | ≥ f T1 , thus to prove (a) it suffices to show that Pr (f T1 ≥ ε • |∂S|/2) ≥ 1/2. We show this next using Chebyshev's Inequality.

Each node u ∈ T 1 belongs to U T1 with probability 1/ deg(u) independently of the other nodes, similar to U T in Definition 4.2. It follows that h

T1 (S) = E[f T1 ]/|∂S|, thus E[f T1 ] = h T1 (S) • |∂S| ≥ ε • |∂S|.
For the variance of f T1 , we will prove below that (4.12)

Var[f T1 ] ≤ u∈T1 deg(u).
From this it follows

Var[f T1 ] ≤ |T 1 | • (c • |∂S|) ≤ c • |∂S| 2 = ε 2 • |∂S| 2 /8,
as c = ε 2 /8. Chebyshev's Inequality then yields the desired result:

Pr (f T1 ≤ ε • |∂S|/2) ≤ Pr |f T1 -E[f T1 ]| ≥ ε • |∂S|/2 ≤ Var[f T1 ] (ε • |∂S|/2) 2 ≤ 1/2.
It remains to prove Eq. (4.12). For each v ∈ ∂(S + ), let X v be a 0/1 random variable that is 1 iff v has a neighbor in U T1 . Then, f T1 = v∈∂(S + ) X v , and

Var[f T1 ] = (v1,v2)∈(∂(S + )) 2 Cov[X v1 , X v2 ]. The covariance term Cov[X v1 , X v2 ] equals Pr(X v1 = X v2 = 1) -Pr(X v1 = 1) • Pr(X v2 = 1).
We can express Pr(X v1 = X v2 = 1) as the sum of the following two terms: 1) the probability that v 1 and v 2 have a common neighbor in U T1 ; by the union bound, this is at most equal to u∈N (v1)∩N (v2)∩T1 1/ deg(u); and 2) the probability that each of v 1 and v 2 has a neighbor in U T1 but they have no common neighbors in U T1 ; this is at most equal to Pr(

X v1 = 1) • Pr(X v2 = 1). It follows Cov[X v1 , X v2 ] ≤ u∈N (v1)∩N (v2)∩T1 1/ deg(u), thus Var[f T1 ] ≤ (v1,v2)∈(∂(S + )) 2 u∈N (v1)∩N (v2)∩T1 1/ deg(u).
For each node u ∈ T 1 , the term 1/ deg(u) appears in the double sum above exactly |N (u) ∩ ∂(S + )| 2 times: once for each pair (v 1 , v 2 ) ∈ (N (u) ∩ ∂(S + ))

2 . Thus,

Var[f T1 ] ≤ u∈T1 (|N (u) ∩ ∂(S + )| 2 / deg(u)) ≤ u∈T1 (deg(u) 2 / deg(u)) = u∈T1 deg(u). (b) Let T 2 = {u ∈ T 2 : |N (u) ∩ ∂(S + )|/ deg(u) ≥ ε/2}
be the set of nodes u ∈ T 2 with the property that an (ε/2)-fraction of u's neighbors belong to ∂(S + ). We have

|T 2 | ≥ ε•|∂S|/2, because otherwise the assumption h T2 (S) ≥ ε is contradicted: h T2 (S) • |∂S| ≤ u∈T2 |N (u) ∩ ∂(S + )| deg(u) ≤ |T 2 | • 1 + (|T 2 | -|T 2 |) • (ε/2) < ε • |∂S|/2 + |∂S| • (ε/2) = ε • |∂S|.
-(1-1/(2k)) |T 2 |/l ≥ 1-e -|T 2 |/(2lk) ≥ 1-e -ε|∂S|/(4lk) . (c) Similar to (b), we let T 3 = {u ∈ T 3 : |N (u) ∩ ∂(S + )|/ deg(u) ≥ ε/2}, and it is |T 3 | ≥ ε • |∂S|/2. If a node u ∈ T 3 gets informed in round t + 1, then we have |I + t+1 -I + t | ≥ εk/2,
where k = max{|S|, c • |∂S|}. Thus, to prove the claim it suffices to lower-bound the probability of informing at least one node u ∈ T 3 in round t + 1. Unlike the proofs for (a) and (b) which rely on pull transmissions of the rumor, we use push transmissions here. For each u ∈ T 3 , we fix a neighbor v u ∈ S of u before round t + 1. The probability that the rumor is pushed from

v u to u is 1/ deg(v u ) ≥ 1/|S + |.
Further, if i > 1 nodes u ∈ T 3 have the same v u , the probability that none of them receives the rumor via a push from v u is 1-i/ deg(v u ) ≤ (1-1/ deg(v u )) i , i.e., it is smaller than if the nodes u had distinct neighbors v u . It follows that the probability at least one node u ∈ T 3 receives the rumor via a push from its neighbor v u is lower-bounded by

1 -(1 -1/|S + |) |T 3 | ≥ 1 -e -|T 3 |/|S + | ≥ 1 -e -ε|∂S|/2 2k/c ,
where for the last inequality we used that

|S + | = |S| + |∂S| ≤ k + k/c ≤ 2k/c, as c ≤ 1.
This completes the proof of Claim 4.11.

From Claim 4.11, Lemma 4.10 follows easily: We can assume that before each round i > t all informed nodes u / ∈ S become uninformed, as this can only decrease the number of nodes v ∈ ∂(S + ) with some informed neighbor after round i. With this assumption, the number of v ∈ ∂(S + ) with an informed neighbor after round i becomes independent of the outcome of the previous rounds t + 1, . . . , i -1. From Claim 4.11(a) then we obtain that if h T1 (S) ≥ h /3, the probability that at least ε•|∂S|/2 nodes v ∈ ∂(S + ) have an informed neighbor after a given round i > t is at least 1/2. If k + Ψ S 0 -Ψ S 0 ≤ 0, the above expectation is 0, thus it is still bounded by the quantity in the second line. This completes the proof of Eq. (4.13) and the proof of Lemma 4.12.

We will now use Lemma 4.12 to derive Theorem 1.1. We partition rumor spreading in phases of y = 2s log(∆)/α rounds each, and count the phases in which Ψ t doubles or |I t | has exceeded n/2. Let X i , for i ≥ 1, be a 0/1 random variable that is 1 iff T (i-1)y ≤ y. From Lemma 4.12, E[T (i-1)y | I (i-1)y ] ≤ y/2, and Markov's Ineq. gives Pr T (i-1)y ≤ y | I (i-1)y ≥ 1/2. It follows Pr(X i = 1 | X 1 . . . X i-1 ) ≥ 1/2, and from this, j≤i X j stochastically dominates binomial random variable B(i, 1/2). Then Chernoff bounds give for i * = 2(β + 3) log n, Pr j≤i * X j < log n ≤ e -2(i * /2-log n) 2 /i * < n -β-1 . This implies that i * y rounds suffice to inform more than n/2 nodes with probability at least 1 -n -β-1 : If |I i * y | ≤ n/2 then fewer than log n among the X 1 . . . X i * are 1, as in this case Ψ i * y ≥ 2 j≤i * Xj , and Ψ i * y < n. Hence, we have Pr(|I i * y | ≤ n/2) ≤ Pr( j≤i * X j < log n) < n -β-1 .

Once a set V 1 ⊆ V with |V 1 | > n/2 has been informed, any given node u / ∈ V 1 gets informed within i * y additional rounds with probability at least 1 -n -β-1 : From Lemma 4.9, the probability that u learns the rumor from V 1 within i * y rounds equals the probability that some node from V 1 learns a rumor originated at u within i * y rounds. And the latter probability is at least equal to the probability that more than n/2 nodes learn u's rumor within i * y rounds, because then at least one of these nodes will belong to V 1 as |V 1 | > n/2.

From the above and the union bound, it follows that all nodes get informed in at most 2i * y = O(log n • log(∆)/α) rounds with probability at least 1-n -β . This completes the proof of Theorem 1.1.

5 .

 5 This probability bound holds for each round t > τ independently of the outcome of previous rounds. It follows that := (β ln n)/(1-√ ) = O(log n) additional rounds after round τ suffice to spread the rumor to a node in S with probability 1 -(e -1+ √ ) = 1 -n -β . Combining this with Claim 3.4, which bounds τ by O(log n) with probability 1 -n -β , and applying the union bound gives that the rumor spreads from u to at least one v ∈ S in O(log n) rounds with probability 1 -2n -β . This completes the proof of Lemma 3.3.

Definition 4 . 2 .

 42 Let S ⊂ V and T ⊆ ∂S. Let U T be a random subset of T such that each node u ∈ T belongs to U T with probability 1/ deg(u) independently of the other nodes. The boundary expansion of S due to T is h T (S) = E [|{v ∈ ∂(S + ) : N (v) ∩ U T = ∅}|] /|∂S|.

Lemma 4 . 6 .

 46 Let u ∈ ∂S ∩ P . Using PUSH-PULL, a rumor originated at u spreads to at least one node v ∈ S in an expected number of O(log ∆) rounds.

Lemma 4 . 10 .

 410 Suppose that I t = S for some set S ⊂ V with boundary expansion h(S) ≥ h , where h > 0 is an arbitrary constant. There is a positive real number b = b(S) ≤ 1/α such that the expected number of rounds until b • |∂S| nodes from ∂(S + ) have some informed neighbor is O(b log ∆).

  It follows that the expected number of rounds until Θ(d * ) = Θ(|S + |) nodes from ∂(S + ) have some informed neighbor is 1/p = O(|S + |/|∂S|), thus the lemma holds for b = Θ(|S + |/|∂S|).

4. 3 . 1 T 1 =T 2 =T 3 =

 31123 Proof of Lemma 4.10. We partition ∂S into three sets, {u ∈ ∂S : deg(u) ≤ c • |∂S|}, {u ∈ ∂S : c • |∂S| < deg(u) ≤ |S|}}, {u ∈ ∂S : deg(u) > max{|S|, c • |∂S|}}, where c = ( h /3)

  It follows that for b = ε/2 the expected number of rounds until b•|∂S| nodes v ∈ ∂(S + ) have an informed neighbor is at most 1/(1/2) = O(b). Similarly, Claim 4.11(b) yields that if h T2 (S) ≥ h /3, then for some k ∈ {c • |∂S|, . . . , |S|} and for b = εk/(2|∂S|) < 1/α, the expected number of rounds until b•|∂S| nodes v ∈ ∂(S + ) have an informed neighbor is 1/Ω(|∂S|/kl) = O(bl). Finally, Claim 4.11(c) gives that if h T3 (S) ≥ h /3, then for k = max{|S|, c • |∂S|} and b = εk/(2|∂S|) < 1/α, the expected number of rounds until b•|∂S| nodes v ∈ ∂(S + ) have an informed neighbor is 1/Ω(|∂S|/k) = O(b). This completes the proof of Lemma 4.10.4.4 Completing the Proof of Theorem 1.

Claim 4 . 13 .

 413 For any non-empty set S ⊂ V , there is a positive real number b S ≤ 1/α such that forτ S = min{i : Ψ S i ≥ Ψ S 0 + b S • |∂S|}, we have E[τ S ] ≤ cb S log ∆, for some constant c > 0. Proof. If h(S) ≤ h < 1,then it follows from Lemma 4.3 that set I S i increases by Θ(|∂S|) nodes-and thus Ψ S i increases by at least that amount-in an expected number of O(log ∆) rounds; so the claim holds for b s = Θ(1) in this case. If h(S) ≥ h > 0, then it follows from Lemma 4.10 that (I S i ) + increases by b•|∂S| nodesthus Ψ S i increases by at least b • |∂S|/2-in an expected number of O(b log ∆) rounds, for some positive b ≤ 1/α; so the claim holds for b s = b/2 in this case. Define T (S, k) = min i : ΨS i ≥ Ψ S 0 + k ∨ |I S i | > n/2 .The quantity E[T t | I t = S] we must bound is then the same as E[T (S, Ψ S 0 )]. We will prove that if |S| ≤ n/2 and 0 < k ≤ Ψ S 0 , then(4.13) E[T (S, k)] ≤ 4 -where c is the constant of Claim 4.13. Lemma 4.12 then follows as a special case of the above inequality:Setting k = Ψ S 0 yields E[T (S, Ψ S 0 )] ≤ 5c log(∆)/(2α), and since E[T (S, Ψ S 0 )] = E[T t | I t = S] it follows that E[T t | I t = S] ≤ s log(∆)/α for s = 5c/2.It remains to show Eq. (4.13). The proof is by induction on k. We distinguish two cases. Case 1: k ≤ b S • |∂S|. This is the base case of the inductive proof. Since k ≤ b S • |∂S|, we have that T (S, k) ≤ T (S, b S • |∂S|) ≤ τ S , and from Claim 4.13, E[τ s ] ≤ cb S log ∆ ≤ c log(∆)/α. Thus E[T (S, k)] ≤ c log(∆)/α. Eq. (4.13) now follows, because 4 -3Ψ S 0 k+Ψ S 0 ≥ 1 as k ≥ 0.

Case 2 :

 2 k > b S • |∂S|. We divide T (S, k) into two terms, the rounds until the potential has increase by b S •|∂S|, and the remaining rounds until it has increased by k in total. Let S = I S τ S . ThenT (S, k) = T (S, b S • |∂S|) + T (S , k + Ψ S 0 -Ψ S 0 ).The first term on the right side is at most τ S , thus from Claim 4.13 it followsE[T (S, b S • |∂S|)] ≤ cb S log ∆.We can bound the expectation of the second term, T (S , k + Ψ S 0 -Ψ S 0 ), by applying the induction hypothesis, as S S and thus k + Ψ S 0 -Ψ S 0 < k. Thus by applying (4.13) with S and k + Ψ S 0 -Ψ S 0 in place of S and k, respectively, we obtain that if k + Ψ S 0 -Ψ S 0 > 0,E[T (S , k + Ψ S 0 -Ψ S 0 ) | S ] ≤ 4 -

  From the three equations above it follows E[T (S, k)] ≤ αb S + 4 -To prove (4.13) it suffices to show that αb S -3b S |∂S| k+Ψ S 0 ≤ 0, or equivalently, that α(k + Ψ S 0 ) ≤ 3|∂S|: Using the assumption of (4.13) that k ≤ Ψ S 0 , and the fact that |∂S|/|S| ≥ α as |S| ≤ n/2, we get α(k + Ψ S 0 ) ≤ 2αΨ S 0 = 2α(|S| + |∂S|/2) ≤ 2(|∂S| + α|∂S|/2) ≤ 3|∂S|.

  You can think of Ψ t as a potential function: each informed node has as a potential of 1, each uninformed node with an informed neighbor has potential 1/2, and the remaining uninformed nodes have potential zero; Ψ t is then the total potential after round t. We have 1 < Ψ t ≤ n. To prove the theorem, we show that the expected number of rounds needed to double Ψ t is bounded by O(log(∆)/α), as long as |I t | ≤ n/2. It follows that O(log n • log(∆)/α) rounds suffice w.h.p. to inform more than half of the nodes, and by a symmetry argument, O(log n • log(∆)/α) additional rounds suffice to inform the remaining nodes. For Ψ t to double in O(log(∆)/α) rounds, it suffices that it increases by Ω(|∂I t |/ log ∆) "on average" per round, as |∂I t | ≥ α • |I t | and thus |∂I t | = Ω(αΨ t ). Such an increase can be achieved either by informing Ω(|∂I t |/ log ∆) nodes from ∂I t , or by informing fewer nodes which however have a total number of Ω(|∂I t |/ log ∆) neighbors in ∂(I + t ). Along this intuition, we distinguish the following two cases, in terms of a simple expansion measure we define for I t , called boundary expansion (Definition 4.1).

  is a constant. The new condition |I u t | ≥ ∆ 2 is added because we want to show a bound of O(log ∆), instead of O(log n) as in Lemma 3.3. The square in ∆ is to ensure that if at least ∆ 2 nodes are informed then at least ∆ of them are active, as we elaborate later. The next result is an analogue of Claim 3.4, and bounds the expectation of τ .

	Claim 4.7. E[τ ] = O(log ∆).

  2 /8. From Definitions 4.1 and 4.2, it follows h T1 (S)+h T2 (S)+h T2 (S) ≥ h(S) ≥ h , and thus, h Ti (S) ≥ h /3 for at least one i ∈ {1, 2, 3}.The next result lower-bounds |I + t+1 -I + t |, i.e., the number of nodes from ∂(S + ) that have an informed neighbor after one round. If h T2 (S) ≥ ε then there is a k ∈ {c|∂S|, . . . , |S|} such that for l = log 2 min{|S|, ∆} max{c|∂S|, δ} ≤ log(2∆),

	Claim 4.11. Let ε = h /3.
	(a) If h T1 (S) ≥ ε then Pr |I + t+1 -I + t | ≥ ε|∂S|/2 ≥ 1 2 .
	(b) Pr |I + t+1

  Since nodes in T 2 have degrees in the range between max{c|∂S|, δ} and min{|S|, ∆}, it follows that for some k in this range, at least |T 2 |/l nodes u ∈ T 2 have degree

	k ≤ deg(u) ≤ 2k. If at least one of these nodes gets
	informed in round t + 1 then |I + t+1 -I + t | ≥ εk/2, and
	the probability that this happens is at least
	1

  1. We will now use Lemmas 4.3 and 4.10 to establish a lower bound on the growth of Ψ t = (|I t | + |I + t |)/2. We show that the expected number of rounds needed to double Ψ t or increase |I t | above n/2 (whichever occurs first) is bounded by O(log(∆)/α). Lemma 4.12. LetT t = min{i : Ψ t+i ≥ 2Ψ t ∨ |I t+i | > n/2}.Then E[T t | I t ] ≤ s log(∆)/α, for a fixed constant s > 0.Proof. The proof uses an inductive argument, and is based on the following corollary of Lemmas 4.3 and 4.10. Let I S i and Ψ S i denote respectively I t+i and Ψ t+i given that I t = S.

Note that the analysis of the more sophisticated information dissemination algorithm proposed in[START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF][START_REF] Haeupler | Simple, fast and deterministic gossip and rumor spreading[END_REF], yields time bounds of O(log

n) and O(log 2 n), respectively, for this setting.

Inequalityv∈I u t 1 deg(v) ≥ 1 -√ yields that the harmonic mean of deg(v), over all v ∈ I u t , is at most |I u t |/(1 -√ ).

We will see that P is unique, although this is not essential for the analysis.

Acknowledgements. I would like to thank Keren Censor-Hillel and Thomas Sauerwald for helpful discussions on the motivation for this work.

Funded, in part, by INRIA Associate Team RADCON and ERC Starting Grant GOSSPLE 204742.

APPENDIX A Rumors Spread Fast in Graphs of Diameter 2

In this section we give an example of another result that can be proved using the machinery developed for the proof of our main result. We show that PUSH-PULL completes in a logarithmic number of rounds in any graph of diameter (at most) 2. This result can be viewed as an extension to the classic result that rumor spreading takes logarithmic time in graphs of diameter 1, i.e., in complete graphs. We point out that unlike complete graphs, some graphs of diameter 2 have very low expansion, e.g., two cliques of the same size with one common vertex. The result does not extend to graphs of diameter 3, as for example, rumor spreading takes linear time in the dumbbell graph, which consist of two cliques of the same size and a single edge between one node from each clique.

Proof Sketch. We fix an arbitrary pair of nodes u, v ∈ V , and show that a rumor originated at u reaches v in O(log n) rounds w.h.p. We divide rumor spreading into three phases, each of length c log n for a sufficiently large constant c.

In the first phase we consider only push operations. We define τ as in the proof of Lemma 3.3, and from Claims 3.4 and 3.5 we obtain that w.h.p. in O(log n) rounds the rumor has spread to all nodes of some set V u ⊆ V for which u ∈Vu 1/ deg(u ) = Ω(1).

In the last (third) phase we consider just pull operations. From the symmetry between push and pull, and the argument used for the first phase, it follows that w.h.p. there is a set V v ⊆ V with v ∈Vv 1/ deg(v ) = Ω(1), such that if some node from V v knows the rumor at the beginning of the last phase, then v learns the rumor as well within the next O(log n) rounds of the phase. (The set V v depends only on the random choices of nodes in the rounds of the phase.) Suppose now that sets V u and V v as above exist (this is true w.h.p.), and fix all random choices in the first and third phases (and thus sets V u and V v ). We will argue that in the second phase the rumor spreads from V u to some node in V v w.h.p. This is trivially true if

From the assumption that the graph has diameter 2, it follows that for every node v ∈ V v , at least one of the next two conditions holds:

1. Node v has a neighbor in V u ; or 2. For every u ∈ V u there is a node w u v / ∈ V u ∪ V v that is a common neighbor of u and v .

If Condition 1 holds for all v ∈ V v , and thus each v ∈ V v has some informed neighbor at the beginning of the second phase, then from inequality v ∈Vv 1/ deg(v ) = Ω(1) it follows that some v ∈ V v will pull the rumor from an informed neighbor w.h.p. within O(log n) rounds. Suppose now that Condition 1 does not hold for some v ∈ V v , thus Condition 2 must hold. Then from inequality u ∈Vu 1/ deg(u ) = Ω(1) it follows that w.h.p. at least one of the nodes u ∈ V u will push the rumor to its neighbor w u v within O(log n) rounds. And thus v will have some informed neighbor after that. Hence, after O(log n) rounds in the second phase, w.h.p. all v ∈ V v have some informed neighbor. It follows then that some v ∈ V v will pull the rumor in an additional O(log n) rounds w.h.p., as we argued earlier.