George Giakkoupis
email: george.giakkoupis@inria.fr

Philipp Woelfel
email: woelfel@cpsc.ucalgary.ca

An Improved Bound for Random Binary Search Trees with Concurrent Insertions

Keywords: 1998 ACM Subject Classification E.1 Data Structures Random binary search tree, buffer, average depth, concurrent data structures

Recently, Aspnes and Ruppert (DISC 2016) defined the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: n randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size c. Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree.

The ability of the adversary to choose the next key to insert among c buffered keys, models a distributed system, where up to c processes try to insert keys concurrently. Aspnes and Ruppert showed that the expected average depth of nodes in the resulting tree is O(log n + c) for a comparison-based adversary, which can only take the relative order of arrived keys into account. We generalize and strengthen this result. In particular, we allow an adversary that knows the actual values of all keys that have arrived, and show that the resulting expected average node depth is D avg (n) + O(c), where D avg (n) = 2 ln n -Θ(1) is the expected average node depth of a random tree obtained in the standard unbuffered version of this experiment. Extending the bound by Aspnes and Ruppert to this stronger adversary model answers one of their open questions.

Introduction

Consider the following random procedure, in which distinct keys from a totally ordered universe are inserted into an (internal) binary search tree (BST). Multiple keys arrive in random order, and whenever a key arrives, it is first placed into a buffer of fixed size c. Upon each key arrival, an adversary may remove one of the keys from the buffer, and insert it into the BST. (The adversary may also decide not to insert a key, if the buffer is not full.) We are interested in performance affecting properties of the resulting BST, such as its height or average node depth. This random experiment has recently been studied by Aspnes and Ruppert [1], to understand how concurrency influences the performance of search trees in a distributed setting: In an asynchronous shared memory system, multiple processes may concurrently try to insert keys into a BST data structure.

The order in which concurrent insertions succeed can depend on unpredictable system factors. For example, cache effects or memory locality on NUMA architectures can heavily influence the speed with which synchronization primitives, and thus insertions take effect. Events such as context switches can delay the operations by some processes, while other processes that may have locked parts of the data structure may be able to execute several operations in rapid succession. Therefore, the order in which concurrent data structure operations succeed can be arbitrary, and is usually analyzed under worst-case assumptions. For randomized algorithms or random inputs, an adversary is used to model how this order is influenced by random events. In analogy to the worst-case analysis of sequential algorithms, it is natural to make pessimistic adversary assumptions, i.e., consider the worst conceivable influence that random events can have on the operation order.

A buffered search tree with buffer size c as described above, models such a distributed scenario, where up to c processes insert random keys concurrently. At any point, there are up to c insert operations pending (corresponding to the keys in the buffer), and the adversary decides which of those insert operations succeeds first.

Aspnes and Ruppert [1] analyzed the buffered search tree for a comparison based adversary, which can base its decisions only on the relative order of the keys that have arrived so far. They showed that for a random arrival sequence of n distinct keys, the resulting BST has an expected average node depth of O(c + log n), and that this bound is asymptotically tight. They also proved that there is a comparison based adversary that can achieve an expected height of Ω c • log(n/c) .

Note that the height of a BST corresponds to the worst-case search time, and the average node depth corresponds to the average-case search time for successful searches.

Contrary to the distributed case (buffered tree), in the sequential setting the expected height and the expected average node depth are known up to constant additive terms. For example, the expected average node depth of a BST obtained by inserting keys {1, . . . , n} in random order is [6]

D avg (n) = 2(1 + 1/n)H n -2, where ln(n + 1) < H n < (ln n) + 1.
It seems appropriate to also analyze height and average depth as precisely as possible for a distributed setting.

The adversary considered by Aspnes and Ruppert [1] does not fully reflect a worst-case scenario, as it can make decisions only based on the relative order of elements, but cannot distinguish their absolute values. It is not clear whether adversarial decisions based on, for example, the pairwise differences between consecutive keys in the ordered list of buffered elements, can lead to a significantly increased average node depth. Consequently, Aspnes and Ruppert suggested that "it might be interesting to see whether even stronger malicious adversaries could force the height or average depth of random trees to grow higher by using the actual values of he keys" [1]. They suggested an example for a buffer size of c = 3, where keys are drawn uniformly at random from the interval [0, 1]: If the first three keys chosen are 0.03, 0.45, and 0.54, then a good strategy for an adversary that can see absolute values would be to insert 0.03 as the root. On the other hand, if the initial three keys in the buffer were 0.46, 0.55, and 0.97, the adversary would be better off by inserting 0.97, first.

Results. We provide a negative answer to the question posed by Aspnes and Ruppert [1], whether an adversary can achieve a significantly increase in the average node depth by using knowledge about the values of keys in the buffer. At the same time, we refine Aspnes and Ruppert's upper bound of O(log n+c) on the expected average node depth, to D avg (n)+O(c). As a result, a buffer of size c = o(log n) does not negatively affect the constant factor in the expected average node depth.

38:3

We consider a strong adversary, which can at any time base its next insertion decision on the exact values of all keys that have arrived so far. In a distributed system, where the buffer corresponds to pending concurrent insert operations, this translates to the strongest reasonable adversary, namely one which can base its decisions on all past random events, but not future ones.

Consider an arrival sequence of n arbitrary distinct keys chosen from a totally ordered universe and permuted randomly. Let ∆(n, c) denote the expected average node depth obtained for a buffered BST given the strong adversary, if the buffer has size c. Note that c = 1 corresponds to the unbuffered case, as the adversary has to move a key from the buffer whenever the buffer is full. Hence, ∆(n, 1) = D avg (n) is the expected average node depth in the standard sequential case. We will prove the following result.

Theorem 1. ∆(n, c) = ∆(n, 1) + O(c), for any c ∈ {2, . . . , n}.

Note that the result of Aspnes and Ruppert [1] states that ∆ (n, c) = O(∆ (n, 1) + c), where ∆ is defined as ∆ but for the weaker comparison based adversary. Related Work. Binary search trees are among the most fundamental data structures, and their properties have been studied extensively. It has been known for a long time that the expected average depth of nodes for trees obtained by inserting a random permutation of n distinct elements is O(log n) [2,10]. Many additional details, such as higher moments, are known about the distribution of node depths [6]. Other parameters of random BSTs have also been determined precisely. For example, a sequence of works [9,3,8] determined the expected height as (4.311 . . .

) • log n -(1.953 . . . ) • log log n + O(1).
The buffered search tree scenario considered in this paper was introduced by Aspnes and Ruppert [1]. They describe it in terms of a card game, where a player takes c cards from a shuffled deck of n cards, then chooses one of the cards in her hand to insert into the BST, and replaces that card with a new one from the deck. This continues until the deck has been depleted, upon which the player inserts all remaining cards in her hand into the tree. The authors point out that a complementary approach is the smoothed analysis of the expected BST height [7].

Concurrent Data Structure Context. To understand the context of this work, it is helpful to know how efficient concurrent data structures, such as binary search trees, may be implemented. There are several techniques to avoid conflicts, when multiple processes access a search tree (or other data structure) concurrently. The simplest one is to use "coarse grained locking", where a mutual exclusion algorithm (lock) protects the entire data structure. This way, only one process can access the data structure at a time, while other processes have to wait.

But such lock-based solutions are inefficient, and not fault tolerant. The "Read-Copy-Update" technique is an example of a more efficient and fault tolerant solution: The address of the root of the tree is stored in a Compare-And-Swap (CAS) object C. This is a standard shared memory primitive that supports a C.CAS(old, new) operation, which atomically changes the value of C to new, provided its current value is old. To insert a node v, a process first creates a copy of the search path from the root to the node u of which v will become a child. Then the process executes a C. CAS(old, new) operation, where old is the address of the original root, and new is the address of the root on the search path copy. This CAS only succeeds, if no other insertion took effect (i.e., no other CAS succeeded) in the meantime. If it fails, the process repeats its insertion attempt. This method is lock-free, guaranteeing S TA C S 2 0 1 8

38:4

An Improved Bound for Random Binary Search Trees with Concurrent Insertions progress even if processes crash. If the tree only supports insertions and no other update operations (such as deletions), then more efficient implementations based on fine grained synchronization are possible (e.g., using one CAS object or lock for each child pointer).

There are several other common solutions, e.g., based on transactional memory. But most of these solutions have in common that the speed of an insertion attempt may depend on the length of the search path. Since "fast" attempts have a higher chance of being successful, it is reasonable to assume that the order of concurrent insertions depends on the values of the involved keys.

Analysis

Our analysis works for a slightly stronger adversary, which in addition to the keys in the buffer, also knows the set (but not the order) of all future keys to arrive. In other words, the adversary knows at any point the ranks of the keys that have arrived so far, with respect to the set of all keys in the complete arrival sequence. In that setting we can assume w.l.o.g. that the key arrival sequence is a random permutation over {1, . . . , n}. The first c -1 of the keys are stored in a buffer. For each following key k that arrives, first k is inserted to the buffer, and then one of the c keys in the buffer is removed and inserted into the tree.

(It is obvious that the adversary can gain no advantage by inserting a key from the buffer "early", i.e., when the buffer is not full and more keys are going to arrive.) After all keys have arrived, the c keys remaining in the buffer are inserted into the tree as well.

Proof Overview. We use the fact that the average node depth in any tree is equal to the average number of descendants of all nodes in the tree. Let k 1 , . . . , k n denote the keys in the order in which they arrive (so, k 1 , . . . , k n is a random permutation of {1, . . . , n}). We bound the expected number of descendants of each key k i in the final tree. For i < c we use the trivial bound of n on the number of descendants of k i . Next we focus on the case i ≥ c. We bound the expected number of descendants of k i in the final tree, given the current tree and the set of keys in the buffer just before k i arrives; at that time, the value of k i is not yet determined, so it is equally likely to be any of the remaining keys. We observe that the number of descendants of k i in the final tree is maximized if key k i is inserted to the tree as soon as it arrives, rather than stored in the buffer and inserted at a later time. So, it suffices to bound the expected number of descendants k i would have, if it were inserted immediately. This expected value depends only on the set of the i -1 keys that arrived before k i , and the subset of them that have been inserted into the tree; in particular, it does not depend on the order in which keys arrived or the order in which keys were inserted into the tree. From this bound on the conditional expectation on the number of descendants of k i , given the i -1 keys that arrived before k i and the i -c keys already in the tree, we obtain a bound on the corresponding unconditional expectation, by letting the first i -1 keys be random, and assuming that an arbitrary (worst-case) (i -c)-subset of them has been inserted into the tree. From this bound for each i ≥ c (and the trivial bound of n for i < c), and from the linearity of expectation, we obtain a bound on the expectation of the average number of descendants of all nodes.

Detailed Proof. We now present the detailed proof of Theorem 1. As already mentioned, k 1 , . . . , k n is a random permutation of {1, . . . , n} denoting the order in which keys arrive. We assume w.l.o.g. that no key is inserted into the tree, unless the buffer is full or all keys have arrived. I.e., the insertions evolve in rounds as follows: In round j ∈ {1, . . . , c -1}, key k j is added to the buffer. In round j ∈ {c, . . . , n}, first key k j is added to the buffer, and then some key j is removed from the buffer and inserted into the search tree. Finally, in each round j ∈ {n + 1, . . . , n + c -1}, one key j is removed from the buffer and inserted into the tree.

For i ∈ {0, . . . , n + c -1}, let X i be the set of keys that have arrived by the end of round i, and let Y i be the set of keys that the tree contains at the end of round i (X 0 = Y 0 = ∅). Then X i = {k 1 , . . . , k i } for i ∈ {0, . . . , n}, and X i = {1, . . . , n} for i > n. Moreover, Y i = ∅ for i ∈ {1, . . . , c -1}, and Y i = { c , . . . , i } for i ∈ {c, . . . , n + c -1}. At the end of round i, the set of keys in the buffer is X i \ Y i . This set contains i elements at the end of round i ∈ {0, . . . , c -1}, c -1 elements at the end of round i ∈ {c, . . . , n}, and n + c -i -1 elements at the end of round i ∈ {n + 1, . . . , n + c -1}. Hence,

|X i \ Y i | = min{i, c -1, n + c -i -1}.
(1)

Let x 1 i , . . . , x i i denote the elements of X i ordered by increasing key values. For convenience we also define x 0 i = 0 and

x i+1 i = n + 1. Further, let Y i = Y i ∪ {0
, n + 1}. We are interested in bounding the number of descendants of each key in the final tree. For i ∈ {0, . . . , n -1}, define the random variable

δ c i = min y ∈ Y i | y > k i+1 -max y ∈ Y i | y < k i+1 .
As we will show below in the proof of Claim 2, the number of descendants of k i+1 in the search tree with buffer size c is at most δ c i -2. Moreover, for c = 1, the number of descendants is exactly δ 1 i -2. Since the average node depth of a search tree equals the average number of descendants of each node, we can upper bound the expected average node depth as the expected average of all values δ c i -2. And for c = 1, these two quantities match.

Claim 2.

(a) ∆(n, 1) = 1 n • n-1 i=0 E[δ 1 i ] -2; and (b) ∆(n, c) ≤ 1 n • n-1 i=0 E[δ c i ] -2, for any c ≥ 2.
Proof. For i ∈ {0, . . . , n -1} let desc(i) denote the set of descendants of key k i in the final search tree, and let depth(j) denote the depth of node k j in the final tree. Then the average node depth of the final tree is

1 n • n j=1 depth(j) = 1 n • n j=1 {i ∈ {1, . . . , n} : k j ∈ desc(i) = 1 n • n j=1 |desc(j)|.
We will now show for any i ∈ {0, . . . , n -1} that |desc(i + 1)| ≤ δ c i -2, and moreover, for a buffer of size c = 1, |desc(i + 1)| = δ 1 i -2. The claim follows immediately from that. Key k i+1 arrives in the buffer in round i + 1. Suppose it is moved into the tree in round j + 1 ≥ i + 1. Then at that point the tree contains the elements in Y j . When that happens, the largest element in the tree that is smaller than k i+1 (if it exists) is a j = max{y ∈ Y j | y < k i+1 }, and the smallest element in the tree that is larger than

k i+1 (if it exists) is b j = min{y ∈ Y j | y > k i+1 }.
The search path to the position where k i+1 gets inserted goes through a j and b j . Hence, in the final tree, the search path to any descendant of k i+1 also goes through those two nodes. Moreover, any key that is larger than a j and smaller than b j will follow the search path to k i+1 and become a descendant of k i+1 . Define S TA C S 2 0 1 8

38:6

An Improved Bound for Random Binary Search Trees with Concurrent Insertions a j = 0 respectively b j = n + 1 if Y j contains no element smaller respectively larger than k i+1 . Then we obtain desc(i + 1) = {a j + 1, . . . , b j -1} \ {k i+1 }, and thus

|desc(i + 1)| = b j -a j -2.
Now observe that if the buffer has size c = 1, then j = i, because key k i gets inserted into the tree in the same round as it arrives. Since

a i = max y ∈ Y i | y < k i+1 and b i = min y ∈ Y i | y > k i+1 (recall that Y i = Y i ∪ {0, n + 1}) we obtain δ 1 i = b i -a i ,
and so |desc(i + 1)| = δ 1 i -2. For c > 1 we may have j > i, but in any case Y i ⊆ Y j . Hence, a i ≤ a j and b i ≥ b j , and so we obtain

δ c i = b i -a i ≥ b j -a j = |desc(i + 1)| -2.
Later, in Claim 4, we will bound the expectation of δ c i , given X i and Y i . To do so, we will use the following simple observation.

Claim 3. For any

i ∈ {c -1, . . . , n -1}, δ c i ≤ max j∈{0,...,i-c+1} (x j+c i -x j i ). Proof. Let y a i = max y ∈ Y i | y < k i+1 . Then y a+1 i = min y ∈ Y i | y > k i+1
, and

δ c i = y a+1 i -y a i . Since Y i ⊆ X i ∪ {0, n + 1},
i , none of x +1 i , . . . , x r-1 i is in Y i . Recall that X i \ Y i
is the set of elements in the buffer at the end of round i. Hence, all r --1 ≥ c elements x +1 i , . . . , x r-1 i are in the buffer at the end of round i. But at the end of a round, the buffer can contain at most c -1 elements, and we have a contradiction.

Therefore, r -≤ c. Then there exists an index j ∈ {0, . . . , } with j + c ∈ {r, . . . , i + 1}. In this case x j i ≤ x i = y a i and x j+c i ≥ x r i = y a+1 i , and thus

x j+c i -x j i ≥ y a+1 i -y a i = δ c i .
This proves the claim.

For a set S = {s 1 , . . . , s m } ⊆ {1, . . . , n}, where

s 1 < • • • < s m , let γ(S) = m i=0 (s i+1 -s i ) 2
, where s 0 = 0 and s m+1 = n + 1.

For any i ∈ {0, . . . , n -1} we will now bound the expected value of δ c i as a function of γ(Y i ), given the sets X i and Y i . That bound is tight for the case c = 1.

Claim 4. For any

i ∈ {c -1, . . . , n -1}, (a) E[δ c i | X i , Y i ] ≤ γ(Y i ) -n -1 n -i ; (b) E[δ 1 i | X i ] = γ(X i ) -n -1 n -i . Proof. Let z = i -c + 1 = |Y i |
, let the set of ordered elements in Y i be y 1 i , . . . , y z i , and let y 0 i = 0 and

y z+1 i = n + 1. Therefore, z j=0 (y j+1 i -y j i ) = y z+1 i -y 0 i = n + 1. ( 2
)
Let σ(i) be the unique index in {0, . . . , z} such that y

σ(i) i < k i+1 < y σ(i)+1 i . Then y σ(i) i = max y ∈ {y 0 i , . . . , y z+1 i } | y < k i+1 and y σ(i)+1 i = min y ∈ {y 0 i , . . . , y z+1 i } | y > k i+1 . Hence, δ c i = y σ(i)+1 i -y σ(i) i .
Recall that X i is the set of keys arrived by the end of round i. Hence, given X i , the element k i+1 , which arrives in round i + 1, is uniformly distributed over {1, . . . , n} \ X i (the tag ( * ) below indicates where this fact is being used). Therefore,

E[δ c i | X i , Y i ] = z j=0 Pr(σ(i) = j) | X i , Y i ) • (y j+1 i -y j i ) = z j=0 Pr k i+1 ∈ {y j i + 1, . . . , y j+1 i -1} X i , Y i • (y j+1 i -y j i ) ( * ) = z j=0 |{y j i + 1, . . . , y j+1 i -1} \ X i | |{1, . . . , n} \ X i | • (y j+1 i -y j i ) ≤ z j=0 y j+1 i -y j i -1 |{1, . . . , n} \ X i | • (y j+1 i -y j i ) (3) = z j=0 (y j+1 i -y j i ) 2 -y j+1 i + y j i n -i (2) = z j=0 (y j+1 i -y j i ) 2 n -1 - n + 1 n -i = γ(Y i ) -n -1 n -i . ( 4
)
This proves Part (a) of the claim.

For Part (b) note that if the buffer has size c = 1, then X i = Y i . Hence, {y j i + 1, . . . , y j+1 i -1} contains no element in X i , and so inequality (3) above holds as an equality. Now Part (b) follows from substituting x j i with y j i and X i with Y i in the above bound.

According to Claim 2, we have

∆(n, c) -∆(n, 1) ≤ 1 n n-1 i=0 (E[δ c i -δ 1 i ]).
In the following we will bound the expectation of the maximum of γ(Y i ) -γ(X i ) for all sets Y i ⊆ X i of size i -c + 1, for i ∈ {c -1, . . . , n -1}. This implies an upper bound on

E[γ(Y i ) -γ(X i )],
and thus by Claim 4 on

E[δ c i -δ 1 i ]. Lemma 5. For any i ∈ {c -1, . . . , n -1}, E[δ c i -δ 1 i ] = O n 2 c 2 + n 2 c log 2 i i 2 (n -i) .
First we show a high probability upper bound on the differences x j+d i -x j i , for all values of j ∈ {0, . . . , i} and d ∈ {1, . . . , i -j + 1} in Claim 6 below. This allows us to bound for a random set S ⊆ {1, . . . , n} of m elements, the expectation of γ(S \ C) -γ(S) for the "worst" subset C of S of a given size. This bound is stated in Lemma 7 below. Using this bound, we will then prove Lemma 5. The distribution of the difference s j+d -s j does not depend on j (see Claim 9 in the appendix), so we can assume j = 0. Thus, it suffices to show

Pr(s d > b) < e -3d • m -3 . ( 5
)
If b > n, then the claim is trivially true, so assume b ≤ n. Let R t , t ∈ {1, . . . , m}, be an indicator random variable, where R t = 1 if and only if the t-th element chosen for S has a value of at most b.

Further, let R = R 1 + • • • + R m .
Then Pr(R t = 1) = b/n, and so

E[R] = m t=1 E[R j ] = m • b n = 8(d + ln m).
Recall that s 0 , s 1 , . . . , s m+1 is an increasing sequence. Therefore, R is the smallest index in {1, . . . , m} such that s R+1 > b. Hence, s d > b is equivalent to R < d, so according to (5) it suffices to show that

Pr(R < d) < e -3d • m -3 . ( 6
)
The random variables R t are negatively associated [5, Section 3.1(c)], so we can use Chernoff Bounds [4, Theorem 3.1] to obtain

Pr(R < d) = Pr R < E[R] 8 -ln m ≤ Pr R < E[R](1 -7/8) < e -(7/8) 2 •E[R]/2
≤ e -(7/8) 2 •8(d+ln m)/2 < e -3(d+ln m) = e -3d • m -3 .

This proves (6), and thus the claim.

Lemma 7. Let S be a set of m ∈ {1, . . . , n} elements chosen at random from {1, . . . , n} without replacement. Then for any τ ∈ {1, . . . , m},

E   max C⊆S |C|=τ γ(S \ C) -γ(S)   = O n 2 τ 2 + n 2 τ log 2 m m 2 .
Proof. Let s 1 , . . . , s m be the elements of S in sorted order, and let s 0 = 0 and s m+1 = n + 1. Define the following event,

Event A: ∀d ∈ {1, . . . , m + 1}, i ∈ {0, . . . , m -d + 1} : s i+d -s i ≤ 8n(d + ln m) m .
Using the union bound and applying Claim 6, we obtain Each pair (s i , s i+1 ) over S \ C contributes (s i+1 -s i ) 2 to the sum γ(S \ C), and it contributes the same amount to the sum γ(S). On the other hand, each pair (s αj , s αj +dj ) over S \ C contributes (s αj +dj -s αj ) 2 to γ(S \ C), while the corresponding contribution to γ(S) is potentially much smaller (precisely it is dj t=1 (s αj +t -s αj +t-1 ) 2 ). Therefore, ignoring these latter contributions to γ(S), we can upper bound the difference γ(S \ C) -γ(S) as follows:

γ(S \ C) -γ(S) ≤ j=1 (s αj +dj -s αj ) 2 .
Now, if event A occurs, then s αj +dj -s αj ≤ 8n(d j + ln m)/m, and so in this case

γ(S \ C) -γ(S) ≤ j=1 8n(d j + ln m) m 2 ≤ j=1 128n 2 d j 2 + ln 2 m m 2 , ( 8
)
where the last inequality was obtained by using the fact that (a + b) 2 ≤ 2(a 2 + b 2 ). Now recall that

d j = |I j | + 1, so d 1 + • • • + d -= |I 1 ∪ • • • ∪ I | = |C| = τ ,
d 1 + • • • + d = τ + ≤ 2τ, and d 1 2 + • • • + d 2 ≤ (d 1 + • • • + d ) 2 = (τ + ) 2 ≤ 4τ 2 . (9)
Observe that if event A occurs, bound (8) is true for every set C ⊆ S of size τ . Thus, if A occurs, then combining (8) and ( 9), we obtain max

C⊆S |C|=τ γ(S \ C) -γ(S) ≤ 128n 2 4τ 2 + ln 2 m m 2 ≤ 128n 2 4τ 2 + τ ln 2 m m 2 . ( 10
)
If event A does not occur, then we can use the trivial bound max

C⊆S |C|=τ γ(S \ C) -γ(S) ≤ max C⊆S |C|=τ γ(S \ C) ≤ γ(∅) = (n + 1) 2 . ( 11
)
According to (7), event ¬A occurs with probability O(m -2 ). Hence, ( 10) and ( 11) imply

E[ max C⊆S |C|=τ γ(S \ C) -γ(S)] ≤ 128n 2 4τ 2 + τ ln 2 m m 2 + (n + 1) 2 • O(m -2 ) = O n 2 τ 2 + τ log 2 m m 2 .
We can now prove Lemma 5.

S TA C S

E[δ c i -δ 1 i | X i , Y i ] ≤ γ(Y i ) -γ(X i ) n -i .
Recall that X i is a set of i elements in {1, . . . , n} chosen uniformly at random without replacement. Moreover, Y i ⊆ X i is chosen by the adversary, where |X i \ Y i | = τ by (1). Hence, from Lemma 7 (substituting X i for S and i for m) we obtain

E[δ c i -δ 1 i ] ≤ 1 n -i • E   max C⊆Xi |C|=τ γ(X i \ C) -γ(X i )   = O 1 n -1 • n 2 τ 2 + n 2 τ log 2 i i 2 .
Since τ < c, the claim follows.

For large i, close to n, the bound in Lemma 5 is too weak. Instead we use the following result which holds for i ≥ n/2:

Lemma 8. Let c < n/2 and i ∈ { n/2 , . . . , n -1}. Then E[δ c i ] = O(c + log n). Proof. Define Event B : ∀j ∈ {0, . . . , i -c + 1} : x j+c i -x j i ≤ 16(c + ln n).
If B occurs, then by Claim 3, δ c i ≤ 16(c + ln n). On the other hand, if B does not occur, then we will use the trivial bound δ c i ≤ n -i < n. We will show below that

Pr(¬B) = O(n -2 ). (12)
Hence, we obtain

E[δ c i ] ≤ 16(c + ln n) + n • O(n -2 ) = O(c + ln n).
Next we prove (12). Recall that k 1 , . . . , k i are the first i elements that arrive, i.e., they are chosen uniformly at random without replacement from {1, . . . , n}. Moreover, x 1 i , . . . , x i i is the sorted order of those elements. Thus, by Claim 6, for any j ∈ {0, . . . , i -c + 1},

Pr x j+c i -x j i > 8n(c + ln i) i < e -3c • i -3 .
Using the assumption of this lemma, n/2 ≤ i < n, and a union bound on j, we obtain Pr ∃j ∈ {0, . . . , i -c + 1} :

x j+c i -x j i > 16(c + ln n) < e -3c •(n/2) -3 (i-c+2) = O(n -2 ).
This proves (12), and thus the lemma.

We now combine Lemmas 5 and 8 to prove our main result, i. According to Claim 2, we have

∆(n, c) -∆(n, 1) ≤ 1 n • n-1 i=0 E[δ c i -δ 1 i ]. (13)
It may be useful to recall the reason for inequality (13). As explained in the proof of Claim 2, δ 1 i is equal to the number of descendants of node k i+1 in the final tree in case the buffer size is 1, and δ c i is an upper bound for the same if the buffer has size c. Hence, the average of all values δ c i -δ 1 i upper bounds the difference in the average number of descendants of all nodes between the two final trees, which in turn is equal to the difference of the average node depth between the two final trees.

We bound the sum above separately for 0 ≤ i ≤ c -1, c ≤ i ≤ b, and b < i ≤ n -1.

From the trivial bounds δ c i ≤ n + 1 and δ 1 i ≥ 0, we get

0≤i≤c-1 E[δ c i -δ 1 i ] ≤ 0≤i≤c-1 E[δ c i ] ≤ c(n + 1). ( 14
)
By Lemma 8, we have E[δ c i ] = O(c + log n) for i ∈ { n/2 , . . . , n -1}, thus b<i≤n-1

E[δ c i -δ 1 i ] = O (n -b) • (c + log n) = O (cn) . ( 15
)
To bound the remaining sum of E[δ c i -δ 1 i ], for c -1 ≤ i ≤ b, first recall the following basic facts for any real z ≥ 0 and integers 1 ≤ a ≤ : Combining ( 13), ( 14), (15), and (17), we obtain ∆(n, c) -∆(n, 1) = O(c). This completes the proof of Theorem 1.

∞ i=a 1 i 2 ≤ 1 a + 1 a 2 ; i=a 1 i ≤ 1 a +ln( /

Claim 6 .

 6 Let S be a set of m ∈ {1, . . . , n} elements chosen at random from {1, . . . , n} without replacement. Let s 1 , . . . , s m be the elements of S in sorted order, and let s 0 = 0 and s m+1 = n + 1. Then for any d ∈ {1, . . . , m + 1} and j ∈ {0, . . . , m -d + 1}, Pr s j+d -s j > 8n(d + ln m) m < e -3d • m -3 . Let b = 8n(d + ln m)/m.

e

  Pr(¬A) = Pr ∃d ∈ {1, . . . , m + 1}, i ∈ {0, . . . , m -d + 1} :s i+d -s i > 8n-3d • m -3 = O(m -2 ). (7)Now consider an arbitrary set C = {s i1 , . . . , s iτ } ⊆ S. Let I = {i 1 , . . . , i τ }, and partition I into maximal subsets I 1 , . . . , I of consecutive indices. Further, for j ∈ {1, . . . , } let α j = min I j -1 and d j = |I j | + 1. Thus, C = j=1 {s αj +1 , s αj +2 , . . . , s αj +dj -1 }, and so for S = S ∪ {s 0 , s m+1 }, S \ C = {s 0 , s 1 , . . . , s α1 , s α1+d1 , s α1+d1+1 , . . . , s α2 , s α2+d2 , . . . , s α , s α +d , . . . , s m+1 }.

  and ≤ |C| = τ (because C contains sets of consecutive indices. Therefore,

  e., ∆(n, c) = ∆(n, 1) + O(c). Proof of Theorem 1. Clearly, ∆(n, c) < n for all c. Therefore, if c ≥ n/2, the theorem is trivially true. Hence, assume c < n/2, and let b = n -cn 2(c + log n) > n -cn 2c = n/2 > c.

  2 + n 2 c log 2 i i 2 (n -i) + n/2<i≤b n 2 c 2 + n 2 c log 2 i i 2 (n -i) nc) + O (c 2 + c log 2 n) • 1 + ln c + log n c (16) = O(nc) + O (c 2 + c log 2 n) • 1 + log n c = O(nc) + O c 2 + c log 2 n + c log n + log 3 n = O(nc). (17)

2 0 1 8 38:10 An Improved Bound for Random Binary Search Trees with Concurrent Insertions Proof of Lemma 5.

  Let τ = c -1, and recall i ∈ {c -1, . . . , n -1}. According to Claim 4,

Acknowledgment

The authors are grateful to Eric Ruppert for his comments on a draft of the proof presented here. Eric also pointed out that our earlier, much simpler proof attempt was indeed too simple to be true.

This research was undertaken, in part, thanks to funding from the ANR Project NDFusion (ANR-16-TERC-0007), the ANR Project PAMELA (ANR-

A Appendix

In the following we provide a basic claim to facilitate our analysis. We believe that this simple observation should be known, but we could not find a reference for it.

Claim 9. Let S be a set of m ∈ {1, . . . , n} elements chosen at random from {1, . . . , n} without replacement. Let s 1 , . . . , s m be the elements of S in sorted order, and let s 0 = 0, s m+1 = n + 1. Then for any d ∈ {1, . . . , m + 1} and j ∈ {0, . . . , m -d + 1}, the distribution of s j+d -s j is identical to the distribution of s d -s 0 .

Proof. Fix d ∈ {1, . . . , m + 1}. Choose a set S of m + 1 elements in {0, . . . , n} at random without replacement, and let s 0 , . . . , s m be the chosen elements in sorted order. Considering the elements as chosen from the mod(n + 1) ring {0, . . . , n}, it is obvious by symmetry that all random variables Z j = (s (j+d) mod (m+1) -s j ) mod (n + 1), j ∈ {0, . . . , m}, are identically distributed. In particular, each variable Z j , j ∈ {0, . . . , m} has the same distribution as Z 0 .

Then letting s i = s i -s 0 , we have that s 1 , . . . , s m have the same distribution as if they were chosen from {1, . . . , n} at random without replacement and then sorted. Moreover, for


Flavio Chierichetti

George Giakkoupis

Silvio Lattanzi

Alessandro Panconesi

Rumor Spreading and Conductance

published or not. The documents may come

Introduction

Rumor spreading, also known as randomized broadcast or randomized gossip, is a well-known distributed algorithm. Starting with one source node with a message, the algorithm proceeds in a sequence of synchronous rounds with the goal of broadcasting the message, i.e., delivering it to all nodes in the network. In each round, every node that knows the message selects a neighbor uniformly at random to which the message is forwarded. This is the so-called PUSH strategy. The PULL variant is symmetric. In each round, every node that does not yet have the message selects a neighbor uniformly at random and asks for the information, which is then transferred to the node provided that the queried neighbor possesses it. Finally, the PUSH-PULL strategy is a combination of both: in each round, every node selects a random neighbor to perform a PUSH if it has the message, or a PULL if it does not have it.

Simplicity and effectiveness are among the many virtues of rumor spreading, making it an ideal candidate for quick dissemination of information inside a network. The algorithm has been extensively studied, since these three strategies were introduced by Demers et al. [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]. Naturally, one of the most studied questions concerns the completion time, i.e., how many rounds it takes to disseminate the information to all nodes in the graph, assuming a worst-case source.

Typically this question has been approached on a case by case basis, by giving careful estimates for particular classes of graphs. For instance, when the network is the complete graph we know that PUSH informs every vertex within log 2 n + ln n + O(1) rounds almost surely [START_REF] Frieze | The shortest-path problem for graphs with random arc-lengths[END_REF][START_REF] Pittel | On spreading a rumor[END_REF]. Other classes of graphs for which rumor spreading has been analyzed include hypercubes, constant degree graphs, and a large variety of random graphs (see Section 2 for more details).

Our approach here is quite different. Rather than focusing on special classes of graphs, we want to identify a set of necessary and/or sufficient conditions for rumor spreading to be fast in any given network satisfying such conditions, where by "fast" we mean that the completion time is poly-logarithmic in the size of the network with high probability. In this work, we make a step in this direction by providing a general sufficient condition for rumor spreading to be fast: high conductance.

The first result of this paper is to show that if a network has n nodes and conductance φ then, with high probability, the completion time of PUSH-PULL is O (log n/φ) . This bound is optimal, for there are graphs of conductance φ and diameter Θ(log n/φ). The proof of this bound is based on a decoupling of the operations of PUSH and PULL. We show that, once the rumor reaches a vertex of maximum degree, every remaining vertex is informed within O(log n/φ) many rounds with high probability by means of PULL alone. There is a clear symmetry between PUSH and PULL that can be exploited to show that the probability of spreading the message from a vertex u to another vertex v within t rounds via PULL is the same as that of spreading the message in the opposite direction, from v to u, within the same t rounds, via PUSH. Therefore, the argument above also shows that, starting from any source, a maximum degree vertex will be informed within O(log n/φ) many rounds with high probability by using PUSH alone. Taken together, these two bounds for PUSH and PULL give the optimal O(log n/φ) bound for PUSH-PULL.

The second result of this paper is an alternative proof showing that the completion time of PUSH-PULL is bounded by a polynomial function in log n/φ. Unlike the previous approach, which is based on a decoupling of PUSH and PULL, this approach analyzes the PUSH-PULL process as a whole. It is based on what we consider to be an interesting and, at the outset, surprising connection between rumor spreading and the spectral sparsification theory. This connection is used to show that a small number of PUSH-PULL rounds (polynomial in log n/φ) expands the volume of the set of informed nodes by a factor of (1 + Θ(φ 2 )), with high probability. In turn, this implies that with high probability, starting from any source, after a number of rounds of PUSH-PULL that is poly-logarithmic in n and polynomial in φ -1 , every node is informed. The resulting bound on the completion time is sub-optimal, but we believe that the proof remains interesting. In a broad sense, it draws a connection between the theory of spectral sparsification and the speed with which diffusion processes make progress in a network. This could potentially lead to further insights beyond the present work and is worth exploring.

The above bounds do not hold for neither PUSH nor PULL in isolation. Perhaps the simplest counterexample is a star of n nodes. The star has maximum conductance, but PUSH takes at least n -1 rounds to complete, regardless of the source, while a standard Coupon Collector's argument shows that Θ(n log n) many rounds are needed with high probability. Moreover, a basic expectation argument shows that when a leaf is the source, PULL requires n many rounds, on average. See also [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] for examples of preferential attachment graphs with high conductance in which the two strategies are proven to be slow.

The final result of the paper is to show a simple sufficient condition for the optimal O(log n/φ) bound to be attained with high probability by PUSH and by PULL alone: for each edge in the graph, the degrees of its two endpoints differ by at most a constant factor.

One of the motivations for our work comes from social networks. Loosely stated, we are looking for a theorem of the form "Rumor spreading is fast in social networks." There is however no universally accepted definition of social network. One way to circumvent this difficulty is to look for properties that are enjoyed by social networks and see whether they imply that rumor spreading is fast. The empirical evidence available suggests that social networks have high conductance [START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF]. Furthermore, this is true for preferential attachment models of social networks such as the one proposed by Mihail et al. [START_REF] Mihail | On certain connectivity properties of the Internet topology[END_REF]. Thus, our results can be considered as a possible explanation of why epidemic processes resembling rumor spreading spread virally in social networks.

We should note that the PUSH-PULL process has some sociological justification. PUSH corresponds to communicating in an active fashion, e.g., texting a message with a mobile phone or sending an email to a specific recipient. PULL on the other hand corresponds to, e.g., reading a tweet or a post on the wall of a Facebook account. Thus, PUSH-PULL seems to be a reasonable first approximation to model the spread of viral information in the age of the Internet.

The work presented here has been the first to show a connection between rumor spreading and graph expansion properties that, intuitively, should ensure fast dissemination. 1 This line of research has generated considerable follow-up work on the relationship between expansion properties and rumor speeding which we now know runs very deep. Following our work, optimal bounds for rumor spreading in terms of vertex expansion have been obtained [START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF][START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF][START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF], and extensions of the bounds with conductance and vertex expansions have been proposed to dynamic graph settings [START_REF] Giakkoupis | Randomized rumor spreading in dynamic graphs[END_REF]. Other works have looked for general bounds for the completion time of rumor spreading without any dependence on conductance, showing that O(D + polylog(n)) rounds are sufficient, where D is the diameter of the graph (and hence a trivial lower bound on the completion time) [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]. Still, these results rely on conductance, in the sense that they show that every graph can be partitioned into regions each of which is of high conductance, and within which rumors spread fast for the reasons elucidated in this work.

The rest of the paper is organized as follows. Section 2 discusses the relevant literature. Section 3 introduces some common concepts and definitions to be used in the rest of the paper. Section 4 presents the optimal O(log n/φ) bound for PUSH-PULL. Section 5 presents a sufficient condition for this bound to hold when PUSH and PULL operate by themselves. Finally, Section 6 shows the connection between rumor spreading and graph sparsification.

Related Work

The literature on rumor spreading is huge and we confine ourselves to what appears to be more relevant to the present work.

Clearly, at least diameter-many rounds of rumor spreading are needed for the message to reach all nodes. On the other hand, Feige et al. [START_REF] Feige | Randomized broadcast in networks[END_REF] have shown that O(n log n) rounds are sufficient with high probability for any connected graph with n nodes. The problem has been studied on a number of graph classes, such as cliques, hypercubes, bounded-degree graphs, and various types of random graphs (see, for instance, [START_REF] Feige | Randomized broadcast in networks[END_REF][START_REF] Frieze | The shortest-path problem for graphs with random arc-lengths[END_REF][START_REF] Pittel | On spreading a rumor[END_REF]). More recently, there has been a lot of work on "quasi-regular" expanders, i.e., expander graphs for which the ratio between the maximum and minimum degree is constant. It has been shown in different settings [START_REF] Berenbrink | Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems[END_REF][START_REF] Doerr | Quasirandom rumor spreading[END_REF][START_REF] Doerr | Quasirandom rumor spreading: Expanders, push vs. pull, and robustness[END_REF][START_REF] Sauerwald | On mixing and edge expansion properties in randomized broadcasting[END_REF] that O(log n) rounds are sufficient for the message to spread throughout the graph. Our work can be viewed as an extension of these studies to graphs of arbitrary degree distribution. Observe that many real world graphs (e.g., Facebook, the Internet, etc.) have a very skewed degree distribution, i.e., the ratio between the maximum and minimum degrees is very high. In most graph models for social networks this ratio is polynomial in the order n of the graph.

Mihail et al. [START_REF] Mihail | On certain connectivity properties of the Internet topology[END_REF] have studied the edge expansion and conductance of graphs that are very similar to preferential attachment graphs, and showed that their edge expansion and conductance are constant. For "genuine" preferential-attachment graphs, Chierichetti et al. [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] showed that rumor spreading finishes in O(log 2 n) rounds. A subsequent paper by Doerr et al. [START_REF] Doerr | Social networks spread rumors in sublogarithmic time[END_REF] improved that, by showing a tight bound of O(log n) rounds and moreover, if one is interested in informing only n -o(n) nodes, then one has to wait for just O(log n/ log log n) many rounds.

Fountoulakis et al. [START_REF] Fountoulakis | Ultra-fast rumor spreading in social networks[END_REF] studied another class of graphs with power-law degree distribution, for which they showed that O(log log n) rounds suffice with high probability to inform n -o(n) nodes.

Boyd et al. [START_REF] Boyd | Gossip algorithms: Design, analysis and applications[END_REF], and Mosk-Aoyama and Shah [START_REF] Mosk-Aoyama | Fast distributed algorithms for computing separable functions[END_REF] have shown that high conductance implies that non-uniform (over neighbors) rumor spreading is fast. By non-uniform we mean that, for every ordered pair of neighbors i and j, node i will select j with probability p ij for the rumor spreading step (in general, p ij = p ji ). This result does not extend to the case of uniform probabilities studied in this paper. In our setting (but not in theirs), the existence of a non-uniform distribution that makes rumor spreading fast is a rather trivial matter. A graph of conductance φ has diameter bounded by O(log n/φ). Observe that in a synchronous network, it is possible to elect a leader in O(log n/φ) many rounds and set up a BFS tree originating from it. Assigning probability 1 to the edge between a node and its parent gives the desired non-uniform probability distribution.

Giakkoupis et al. [START_REF] Giakkoupis | Low randomness rumor spreading via hashing[END_REF] have shown an O(log n/φ) bound for a "low-randomness" variant of PUSH on regular graphs. In their algorithm, the random choices of nodes are not independent, but rely instead on a pseudorandom generator whose random seed is attached to the message.

Another standard measure of graph expansion that has been studied in connection with rumor spreading is vertex expansion [START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF][START_REF] Giakkoupis | Rumor spreading and vertex expansion[END_REF][START_REF] Sauerwald | Rumor spreading and vertex expansion on regular graphs[END_REF]. The main result of this line of work is a tight bound of O(log n•log ∆/α) on the number of rounds for PUSH-PULL to spread a message with high probability, for any graph with vertex expansion α and maximum degree ∆. This bound is incomparable to the O(log n/φ) bound, as the vertex expansion is incomparable to conductance for general graphs.

An interesting application of the O(log n/φ) bound has been in the design of a new class of information dissemination protocols [START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF][START_REF] Censor-Hillel | Fast information spreading in graphs with large weak 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 a round. These new protocols achieve fast information spreading for broad families of networks, and some of these protocols achieve for all graphs time bounds that are close (within polylogarithmic factors or polylogarithmic terms) to the network diameter.

For the message complexity of PUSH-PULL, we observe first that it has been determined precisely only for very special classes of graphs (namely, cliques [START_REF] Karp | Randomized rumor spreading[END_REF] and Erdös-Rényi random graphs [START_REF] Elsässer | On the communication complexity of randomized broadcasting in random-like graphs[END_REF]). Apart from that, given the generality of the graph class we consider, it is not possible to obtain a non-trivial upper bound on the number of messages -where the trivial upper bound is the number of rounds times n. Consider for instance the "lollipop graph." Fix ω(n -1 ) < φ < O(log -1 n), and suppose that we have a path of length φ -1 connected to a clique of size n -φ -1 = Θ(n). This graph has conductance O(φ). Let the source be an arbitrary node in the clique. After Θ(log n) rounds each node in the clique will have the information with high probability. Further it will take at least φ -1 steps for the information to be sent to each node in the path. So, at least n -φ -1 = Θ(n) messages are pushed (by the nodes in the clique) in each round, for at least φ -1 -Θ(log n) = Θ(φ -1 ) rounds. Thus, the total number of messages sent will be Ω(nφ -1 ). Observing that the number of rounds is Θ(φ -1 +log n) = Θ(φ -1 ), we obtain that the number of rounds times n is (asymptotically) less than or equal to the number of transmitted messages.

We also note that one cannot give fault-tolerance guarantees (that is, the ability of the protocol to resist to node and/or edge deletions) based only on conductance. A star has high conductance, but failure of the central node destroys connectivity.

Preliminaries

In this section we introduce some, mostly standard, notation and provide some basic technical lemmas to be used in the analysis. Let G = (V, E) be an undirected graph with

n = |V | vertices. For a vertex v ∈ V , Γ G (v) denotes the set of v's neighbors in G, and deg G (v) := |Γ G (v)| is the degree of v. By ∆ G we denote the maximum degree of G. For a set of vertices S ⊆ V , we let Γ G (S) := v∈S Γ G (v) -S.
We define the volume of set S ⊆ V to be the sum of the degrees of the vertices contained in S,

vol G (S) := v∈S deg G (v).
Observe that vol G (V ) = 2 • |E|. Given two disjoint sets of vertices A, B ⊆ V , we let cut G (A, B) be the set of edges with one endpoint in A and the other in B.

Definition 1 (Conductance [START_REF] Jerrum | Approximating the permanent[END_REF]). The conductance of a non-empty vertex set S in graph G is

φ G (S) := |cut G (S, V -S)| vol G (S) .
The conductance of G is the minimum φ G (S), over all sets S for which vol(S) ≤ vol G (V )/2,

φ G := min S⊆V, 0<vol(S)≤vol(V )/2 |cut G (S, V -S)| vol G (S) .
In all the notations above we will omit G whenever the graph is clear from the context. We say that an event occurs with high probability, abbreviated as w.h.p., if it happens with probability 1 -n -Ω (1) .

Let B(k, p) denote a binomial random variable with parameters k and p, i.e., B(k, p) is the number of successes among k independent trials each of which succeeds with probability p. We will use the next standard lemma, which can be found in [1, Lemma 3.1].

Lemma 2. Let Z 1 , . . . , Z k be random variables with values in some arbitrary domain, and let X 1 , . . . , X k be binary random variables such that

X i = X i (Z 1 , . . . , Z i ), for 1 ≤ i ≤ k. Let X := k i=1 X i . If Pr(X i = 1 | Z 1 , . . . , Z i-1 ) ≥ p, for all 1 ≤ i ≤ k, then for any t, Pr(X < t) ≤ Pr(B(k, p) < t).
The following lemma gives simple bounds on the number of coupons collected in the Coupon Collector's process, within a given number of trials. We denote that number by C(k, t), where k is the total number of coupons, and t is the number of trials. Lemma 3. Consider the standard Coupon Collector's process, where we are given an urn of k different coupons, and we draw coupons from the urn, equally likely with replacement. Let C(k, t) denote the number of distinct coupons drawn in t trials. Then for any t ≥ 0,

Pr C(k, t) < k ≤ ke -t/k , (1)
and for any λ < k,

Pr (C(k, t) ≤ λ) ≤ Pr (B(t, 1 -λ/k) ≤ λ) . (2)
Proof. The probability that a given coupon is not selected in t trials is

(1 -1/k) t ≤ e -t/k ,
and by a union bound, the probability at least one coupon is not selected, i.e., C(k, t) < k, is at most ke -t/k . This proves (1). Let X i , 1 ≤ i ≤ t, be a binary random variable which is 1 if a new coupon is selected in the ith trial or if the total number of distinct coupons selected in the previous i -1 trials is larger than λ; otherwise, X i = 0. Then

Pr (C(k, t) ≤ λ) = Pr t i=1 X i ≤ λ .
The probability that X i = 1 is at least 1 -λ k , independently of the outcome of the previous trials, because either more than λ distinct coupons have been selected in the first i -1 trials and then X i = 1, or at most λ coupons have been selected, and thus the probability a new coupon is selected in the ith trial is at least k-λ k . Therefore, we can apply Lemma 2 to obtain Pr t i=1

X i ≤ λ ≤ Pr (B(t, 1 -λ/k) ≤ λ) .
Combining the last two equations above gives [START_REF] Batson | Spectral sparsification of graphs: Theory and algorithms[END_REF].

Finally, we will use the following Chernoff bounds for binomial random variables, which can be found, e.g., in [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF][START_REF] Mitzenmacher | Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis[END_REF].

Lemma 4 (Chernoff bounds). (a) For t ≤ k/2, Pr (B(k, 1/2) ≤ t) ≤ e -2(k/2-t) 2 /k . (b) For 0 < ≤ 1, Pr (B(k, p) ≥ (1 + )np) ≤ e -2 np/3 .

Optimal Bound for Push-Pull

In this section, we prove a general upper bound of O(log n/φ) rounds for PUSH-PULL on any nnode graph with conductance φ. Further, we argue that this bound is best possible, if we have no additional information for the graph other than φ and n.

The formal statement of the upper bound is as follows.

Theorem 5. Let G = (V, E) be a connected n-node graph with conductance φ. Then O(log n/φ) rounds of PUSH-PULL suffice w.h.p. to spread to all nodes of G a message originated at an arbitrary source node.

The proof of Theorem 5 relies on the next key lemma, which states that a message spreads from a node of maximum degree to all other nodes in O(log n/φ) rounds w.h.p. This statement is true even if only PULL is used. Recall that ∆ denotes the maximum degree of G. Lemma 6. Using PULL, a message originated at a node of degree ∆ spreads to all other nodes in O(log n/φ) rounds with probability at least 1 -n -c , for any constant c > 0.

The proof of Lemma 6 is based on an analysis of the growth of the volume of the set of informed nodes, and is given in Section 4.1.

We will also use the following basic lemma, which underlines the symmetries in the PUSH and PULL strategies. Lemma 7. Let u t -→ push v denote the event that a message originated at vertex u reaches vertex v in at most t rounds when PUSH is used, and define u t -→ pull v similarly. For any u, v ∈ V , and

t ≥ 0, we have Pr(u t - → push v) = Pr(v t - → pull u).
Proof. W.l.o.g. we can assume that in each round, every node (informed or not) chooses a random neighbor. Of course only informed nodes actually establish a connection to the neighbor they choose in the PUSH strategy, and only uninformed nodes establish a connection in the PULL strategy. Let Ω t be the space of possible choices for all nodes over t rounds, i.e., each ω ∈ Ω t specifies for every node u ∈ V and round i ∈ {1 . . . t}, the neighbor that u chooses in round i. Observe that all ω ∈ Ω t have the same probability: Pr(ω) = u∈V (deg(u)) -t . Further, each ω ∈ Ω t completely determines the spread of a message in t rounds, given the source node and the rumor spreading strategy. Let Ω t (u, v, push) be the set of all ω ∈ Ω t for which a message originated at u reaches v within t rounds when PUSH is used, and define Ω t (u, v, pull) similarly. Since all ω ∈ Ω t have the same probability, it suffices to show that |Ω t (u, v, push)| = |Ω t (v, u, pull)| in order to prove Pr(u

t - → push v) = Pr(v t - → pull u).
For ω ∈ Ω t , let rev(ω) ∈ Ω t contain the same collection of choices as ω but in reverse round order, i.e., if node u chooses node v in round i in ω, then u chooses v in round t -i in rev(ω). We now argue that ω ∈ Ω t (u, v, push) iff rev(ω) ∈ Ω t (v, u, pull). A push path for ω ∈ Ω t is a list of nodes u 0 , . . . , u t such that for any two consecutive nodes u i-1 and u i , either (i) u i-1 = u i , or (ii) u i-1 chooses u i in round i. A pull path is defined similarly except that (ii) is replaced by: (ii ) u i chooses u i-1 in round i. For a given ω ∈ Ω t , PUSH (or PULL) informs node v within t rounds of a message originated at u iff there is a push path (resp. pull path) from u to v. Further, u 0 , u 1 , . . . , u t , with u 0 = u and u t = v, is a push path for ω iff u t , u t-1 , . . . , u 0 is a pull path for rev(ω). From the last two observations it follows that ω ∈ Ω t (u, v, push) iff rev(ω) ∈ Ω t (v, u, pull). From this and the fact that for distinct ω, ω ∈ Ω t we have rev(ω) = rev(ω ), we obtain

|Ω t (u, v, push)| = |Ω t (v, u, pull)|.
Theorem 5 follows easily from the two lemmas above: From Lemma 6 we have that a message originating from an arbitrary source node u needs O(log n/φ) rounds of PULL to spread to all nodes w.h.p., after it has reached a node v of degree ∆. Further, by combining Lemma 6 with Lemma 7, we obtain that O(log n/φ) rounds suffice w.h.p. for u's message to reach the max-degree node v using PUSH.

Proof of Theorem 5 (assuming Lemma 6 holds). Let u be an arbitrary node, and v be a node with deg(v) = ∆. By Lemma 6, there is some t = O(log n/φ) such that t rounds of PULL suffice with probability at least 1 -n -c to spread a message from v to all other nodes, and thus to node u. From this and Lemma 7, it follows that t rounds of PUSH suffice to spread a message from u to v with probability at least 1 -n -c ; thus the same is true when PUSH-PULL is used instead of just PUSH. Once v has learned u's message, Lemma 6 implies, as mentioned above, that all nodes will learn the message with probability at least 1 -n -c after at most t additional rounds of PULL (and thus of PUSH-PULL). A union bound then gives that with probability at least 1 -2n -c , v learns u's message within t rounds and then all remaining nodes learn the message within t additional rounds. Thus all nodes get informed after a total number of at most 2t = O(log n/φ) rounds w.h.p.

Below, we give the proof of Lemma 6, in Section 4.1, and we argue about the optimality of Theorem 5, in Section 4.2.

Analysis of Pull (Proof of Lemma 6)

In this section, we show that O(log n/φ) rounds of PULL suffice w.h.p. to spread a message to all nodes, if the source node has degree ∆.

The proof analyses the growth rate of the volume of informed vertices. Let I t be the set of informed nodes after the first t rounds, and let U t = V -I t be the set of uninformed nodes at that time. Roughly speaking, we argue that while vol(I t ) is at most some constant fraction of the total volume vol(V ), vol(I t ) increases by a factor of at least 1+Ω(φ) per round on average; and after that, vol(U t ) decreases by a factor of at most 1 -Ω(φ). It follows that O(log(vol(V ))/φ) = O(log n/φ) rounds suffice for vol(I t ) to increase to a constant fraction of vol(V ), and then O(log n/φ) additional rounds suffice for vol(U t ) to drop to zero.

To convey the main intuition let us compute the expected increase of vol(I t ) in round t + 1 (see Lemma 8(a) for the formal argument): Suppose that vol(I t ) ≤ vol(V )/2, and for each uninformed node v ∈ U t let deg (v) be the number of its informed neighbors. The contribution of v to the expected increase of vol(I t ) is then (deg (v)/ deg(v)) • deg(v) = deg (v), as v chooses some of its informed neighbors in round t + 1 (and pulls the message from it) with probability deg (v)/ deg(v). It follows

E[vol(I t+1 ) | I t ] -vol(I t ) = v∈Ut deg (v) = | cut(I t , U t )| ≥ φ • vol(I t ),
by the definition of conductance. Thus,

E[vol(I t+1 ) | I t ] ≥ (1 + φ) vol(I t ). Similarly, we obtain E[vol(U t+1 ) | U t ] ≤ (1 -φ) vol(U t )
, when vol(I t ) ≥ vol(V )/2. These simple expectation bounds, together with Markov's Inequality, suffice to obtain an O(log n/φ) bound w.h.p. on the number of rounds until all nodes get informed, from the time when a constant fraction of the total volume has been informed (Lemma 11). To bound the time to inform that constant fraction, however, more work is required. For that we bound also the variance of the increase of vol(I t ) (Lemma 8(b)), and use the second moment method to show that the volume doubles in O(1/φ) rounds with constant probability (Lemma 9). From this last result and Chernoff Bounds, we obtain the desired high-probability bound on the time to inform a constant fraction of the total volume (Lemma 10).

Next we give the detailed analysis.

Consider the volume L of nodes that get informed in a round by pulling the message through a given set D of edges between informed and uninformed nodes (D does not necessarily contain all edges between informed and uninformed nodes, and is fixed before the round starts). The next lemma states that the expectation of L is equal to the number of edges contained in D, and L's variance is bounded by the number of edges times the maximum degree of their endpoints in U t . Lemma 8. Fix an arbitrary subset D of cut(I t , U t ) before round t + 1, and let L be the volume of the set of nodes that get informed in round t + 1 by pulling the message through edges from D. Then Proof. For each node v ∈ N , let deg D (v) be the number of edges from set D that are incident to v. Clearly, v∈N deg D (v) = |D|. For each v ∈ N , let X v be a binary random variable that is 1 if v gets informed in round t + 1 by pulling the message through some edge from D, and is 0 otherwise. Then, Pr(

X v = 1) = deg D (v)/ deg(v). We have L = v∈N X v • deg(v) ,

and thus

E[L] = v∈N E[X v • deg(v)] = v∈N Pr(X v = 1) • deg(v) = v∈N (deg D (v)/ deg(v)) • deg(v) = v∈N deg D (v) = |D|.
Next we bound the variance of L. Since L = v∈N X v • deg(v) and the random variables X v are independent,

Var[L] = v∈N Var[X v • deg(v)] = v∈N Var[X v ] • (deg(v)) 2 .
Using also that Var

[X v ] = Pr(X v = 1) • Pr(X v = 0) ≤ Pr(X v = 1) = deg D (v)/ deg(v), we obtain Var[L] ≤ v∈N (deg D (v) • deg(v)) ≤ v∈N deg D (v) • max v∈N deg(v) = |D| • max v∈N deg(v).
In the following, we first bound the number of rounds to inform a constant fraction of the total volume, namely a 1/3 fraction, and then bound the number of rounds to inform the remaining nodes.

Informing a Constant Fraction of the Volume

We prove that O(ln n/φ) rounds of PULL suffice w.h.p. to inform a subset of nodes with volume at least vol(V )/3, when the message starts from a node of degree ∆.

Our key claim is that if ∆ ≤ vol(I t ) ≤ vol(V )/3, then O(1/φ) rounds suffice with constant probability to double the volume of informed nodes. The proof proceeds as follows. Before each round t + k > t, we fix an edge set D k ⊆ cut(I t+k-1 , U t+k-1 ) of size |D k | = φ • vol(I t ); this set can be arbitrary but must be fixed before round t + k starts. Then we compute the volume L k of the set of nodes that get informed in round t + k by pulling the message through edges from D k . Clearly, 1≤i≤k L i is a lower bound on vol(I t+k ) -vol(I t ), and thus to prove the claim it suffices to show that 1≤i≤k L i ≥ vol(I t ) holds with constant probability. To show that, we use Lemma 8 to compute the expectation of 1≤i≤k L i and to bound its variance, and then apply Chebyshev's Inequality.

Lemma 9 below proves a slightly more general statement, which does not assume that volume vol(I t ) is at least ∆, and gives a lower bound on the probability that the volume doubles within a given number k of steps, as a function of k and the ratio ∆/ vol(I t ).

Lemma 9. If vol(I t ) ≤ vol(V )/3 then for any k > 1/φ, Pr vol(I t+k ) ≥ 2 vol(I t ) | I t > 1 - kφ (kφ -1) 2 • ∆ vol(I t ) .
Proof. Throughout the proof we assume that I t is fixed and vol(I t ) ≤ vol(V )/3. Let τ = min k : vol(I t+k ) ≥ 2 vol(I t ) .

For each 1 ≤ k ≤ τ , we define random variable L k as follows. Let D k denote the set of the first M := φ • vol(I t ) edges in cut(I t+k-1 , U t+k-1 ), according to some fixed total order over E. 2 (We will see in (3) that | cut(I t+k-1 , U t+k-1 )| ≥ M .) Then L k is the volume of the set of nodes that get informed in round t + k by pulling the message through edges from D k . Further, for each k > τ , we let L k = M . We argue now that for any t with t ≤ t < t + τ ,

| cut(I t , U t )| ≥ M. (3)
If vol(I t ) ≤ vol(V )/2 then φ(I t ) ≥ φ. Also vol(I t ) ≥ vol(I t ). Then

| cut(I t , U t )| = φ(I t ) • vol(I t ) ≥ φ • vol(I t ).
If vol(I t ) > vol(V )/2 then vol(U t ) < vol(V )/2, and thus φ(U t ) ≥ φ. Also, vol(I t ) < 2 vol(I t ) and thus vol(U t ) > vol(V ) -2 vol(I t ) ≥ vol(I t ), as vol(I t ) ≤ vol(V )/3. Then

| cut(I t , U t )| = φ(U t ) • vol(U t ) ≥ φ • vol(I t ).
For each k ≥ 0, let Y k = 1≤i≤k L i . Then for k ≤ τ , Y k is a lower bound on the volume of nodes informed in rounds t + 1 up to t + k, i.e., Y k ≤ vol(I t+k ) -vol(I t ). It follows that if vol(I t+k ) < 2 vol(I t ), then k < τ and Y k ≤ vol(I t+k ) -vol(I t ) < vol(I t ). Therefore,

Pr(vol(I t+k ) < 2 vol(I t )) ≤ Pr(Y k < vol(I t )). (4)
Next we bound the probability on the right side, that Y k < vol(I t ). For that, we compute the expectation and variance of Y k , and then apply Chebyshev's Inequality. If 1 ≤ k ≤ τ , then from Lemma 8(a) it follows that

E[L k | I t+k-1 ] = |D k | = M.
This equation is also trivially true if k > τ , as L k = M in this case. It follows that for all k ≥ 1,

E[L k ] = E[E[L k | I t+k-1 ]] = M,
and by linearity of expectation,

E[Y k ] = kM. (5)
For the variance of Y k we have

Var[Y k ] = Var[Y k-1 + L k ] = Var[Y k-1 ] + Var[L k ] + 2 Cov[Y k-1 , L k ].
The covariance term is zero, as

E (Y k-1 -E[Y k-1 ]) • (L k -E[L k ]) I t . . . I t+k-1 = (Y k-1 -E[Y k-1 ]) • (E[L k | I t+k-1 ] -E[L k ]) = (Y k-1 -E[Y k-1 ]) • (M -M ) = 0, and thus Cov[Y k-1 , L k ] = E E (Y k-1 -E[Y k-1 ]) • (L k -E[L k ]) I t . . . I t+k-1 = 0. Substituting this to the formula for Var[Y k ] above yields Var[Y k ] = Var[Y k-1 ] + Var[L k ]. We now bound Var[L k ]. If 1 ≤ k ≤ τ , then from Lemma 8(b) it follows Var[L k | I t+k-1 ] ≤ |D k | • max v∈N k deg(v) ≤ M ∆, ( 6
)
where N k is the set of nodes v ∈ U t+k-1 incident to some edge in D k . The above inequality is also

trivially true if k > τ , as Var[L k | I t+k-1 ] = 0 in this case. It follows that Var[L k ] ≤ M ∆, for all k ≥ 1. Substituting this to the equation for Var[Y k ] above gives Var[Y k ] ≤ Var[Y k-1 ] + M ∆,

and applying this inequality repeatedly yields

Var[Y k ] ≤ kM ∆. (7)
We use now Chebyshev's Inequality to bound the probability that Y k < vol(I t ). We assume that k > 1/φ. Then from ( 5),

E[Y k ] = kM > M/φ ≥ vol(I t ). We have Pr (Y k < vol(I t )) = Pr (E[Y k ] -Y k > E[Y k ] -vol(I t )) < Var[Y k ] (E[Y k ] -vol(I t )) 2 .
Substituting the value of E[Y k ] from [START_REF] Censor-Hillel | Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance[END_REF] and the bound for Var[Y k ] from [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF], we obtain

Pr (Y k < vol(I t )) < kM ∆ (kM -vol(I t )) 2 = ∆ vol(I t ) • kM/ vol(I k ) (kM/ vol(I k ) -1) 2 ≤ ∆ vol(I t ) • kφ (kφ -1) 2 ,
where the last inequality holds because kM/ vol(I t ) ≥ kφ, and the function f (x) = x/(x -1) 2 is decreasing for x > 1. Combining the above bound on Pr (Y k < vol(I t )) with ( 4) completes the proof of Lemma 9.

Using Lemma 9 and Chernoff Bounds, we show next our main claim, that O(ln n/φ) rounds suffice w.h.p. to inform a subset of nodes with volume at least vol(V )/3. Lemma 10. If the source of the message has degree ∆, then Pr(vol

(I t ) ≥ vol(V )/3) ≥ 1 -n -c , for t = 2c ln n + 4 log n • 4/φ .
Proof. We divide rumor spreading into phases of k := 4/φ rounds each, and consider whether the volume of informed vertices doubles in these phases. For each i ≥ 1, let X i be a binary random variable that is 1 if vol I ik ≥ 2 vol I (i-1)k or vol I (i-1)k ≥ vol(V )/3, and is 0 otherwise. From Lemma 9 it follows

Pr X i = 1 | I (i-1)k > 1 - kφ (kφ -1) 2 • ∆ vol(I (i-1)k ) ≥ 1 - 4 (4 -1) 2 • ∆ ∆ = 5/9 > 1/2. ( 8
)
We bound the probability that vol(I t ) < vol(V )/3 in terms of the sum of X i : If vol(I ik ) < vol(V )/3, then fewer than log(vol(V )/(3∆)) among the random variables X 1 . . . X i are 1, because, otherwise, the volume of informed nodes would double at least log(vol(V )/(3∆)) times in the first ik rounds, and thus increase from ∆ to at least 2 log(vol(V )/(3∆)) ∆ = vol(V )/3. Therefore,

Pr vol (I ik ) < vol(V )/3 ≤ Pr j≤i X j < log(vol(V )/(3∆)) ≤ Pr j≤i X j < log n ,
as vol(V ) ≤ n∆. To bound the sum of the (non-independent) random variables X i , we use the fact we showed in [START_REF] Chierichetti | Rumor spreading in social networks[END_REF], that for all i ≥ 1, Pr(X i = 1 | I (i-1)k ) ≥ 1/2, and apply Lemma 2 to obtain Pr j≤i X j < log n ≤ Pr (B(i, 1/2) < log n) . Then Lemma 4(a) gives for i ≥ 2 log n,

Pr j≤i X j < log n ≤ e -2(i/2-log n) 2 /i ≤ e -(i/2-2 log n) .
Letting i ≥ 2c ln n + 4 log n, the above bound becomes at most e -c ln n = n -c . Therefore, we have that Pr (vol (I ik ) < vol(V )/3) ≤ n -c , for i = 2c ln n + 4 log n .

Informing the Remaining Nodes

We show that O(ln n/φ) rounds of PULL suffice w.h.p. to inform all the remaining nodes, after a set of nodes with volume at least vol(V )/3 has been informed. Proof. In the following we assume I t is fixed and vol(I t ) ≥ vol(V )/3. We first argue that for t ≥ t,

| cut(I t , U t )| ≥ φ • vol(U t )/2. If vol(U t ) ≤ vol(V )/2, then φ(U t ) ≥ φ and | cut(I t , U t )| = φ(U t ) • vol(U t ) ≥ φ • vol(U t ). If vol(U t ) > vol(V )/2, then φ(I t ) ≥ φ and | cut(I t , U t )| = φ(I t )•vol(I t ) ≥ φ•vol(I t ) ≥ φ•vol(U t )/2, as vol(I t ) ≥ vol(V )/3. Lemma 8(a), for D = cut(I t , U t ), gives E[vol(U t -U t +1 ) | I t ] = | cut(I t , U t )|.
Substituting the bound for | cut(I t , U t )| from above and rearranging yields

E[vol(U t +1 ) | I t ] ≤ (1 -φ/2) • vol(U t ).
Taking the expectation on both sides gives

E[vol(U t +1 )] ≤ (1 -φ/2) • E[vol(U t )],
and applying this inequality repeatedly yields, for t = t + k,

E[vol(U t )] ≤ (1 -φ/2) k • vol(U t ) ≤ e -kφ/2 • n 2 .
For k ≥ 2(c + 2) ln n/φ, we get E[vol(U t )] ≤ n -c , and then Markov's Inequality gives

Pr(U t = ∅) = Pr(vol(U t ) ≥ 1) ≤ E[vol(U t )]/1 ≤ n -c .
Lemma 6 follows now immediately from Lemmas 10 and 11, and a union bound.

Tightness of the Upper Bound

We observe that the upper bound of Theorem 5 is tight. Indeed, there exist graphs on n nodes, with conductance φ, that have diameter Ω(log n/φ). We now present one example of such a graph. Let φ > 1/n 1-, and take any graph on Θ(φn) nodes with constant degree and constant conductance (e.g., a random cubic graph on Θ(φn) nodes.) Then, replace each edge of the graph with a path of length Θ φ -1 . The resulting graph will have conductance Θ(φ), and will contain Θ(n) nodes. Moreover, the diameter of the new graph will be equal to the diameter of the original graph times Θ φ -1 -since the original graph had constant degree its diameter is at least logarithmic in its order, that is at least Ω (log(φn)). Therefore, the new graph will have diameter at least Ω (log(φn)/φ). Since φ > 1/n 1-, the lower bound reduces to Ω (log n/φ).

A Sufficient Condition for Push and Pull

The O(log n/φ) bound we have shown for PUSH-PULL in Theorem 5 does not hold if only one of the PUSH or PULL strategies is used. As already mentioned, for the n-vertex star, which has conductance φ = 1, at least n -1 rounds of PUSH are needed to inform all nodes, regardless of the source. If PULL is used instead, and the message originates at a leaf of the star, then n rounds are needed in expectation (n -1 expected rounds until the center of the star pulls the message from the source, and 1 additional round for all leaves to pull the message from the center). Observe, however, that if the message originates at the center, then all nodes get informed in just a single round of PULL. As shown in Lemma 6, for any graph G = (V, E) there is some node u ∈ V (namely, any max-degree node u) such that a message originated at u spreads to all nodes within O(log n/φ) rounds of PULL w.h.p. The same is not true for PUSH, as the example of the star shows.

The next theorem identifies a simple graph property which guarantees that the O(log n/φ) bound holds for PUSH and PULL, regardless of the source of the message. The property states that for any edge of the graph, the ratio of the degrees of its two endpoints is bounded by some constant.

Theorem 12. Let G = (V, E) be a connected n-node graph with conductance φ and the property that for any edge uv ∈ E, deg(u)/ deg(v) = Θ(1). Then O(log n/φ) rounds of PUSH or PULL suffice w.h.p. to spread to all nodes of G a message originated at an arbitrary source node.

Proof. The analysis for PULL is the same as that for Lemma 6, except for a few small modifications we point out now. In place of Lemma 9, we use the following statement.

Lemma 13. Suppose that for every edge uv ∈ E, we have deg

(u)/ deg(v) ∈ [1/α, α] for some α ≥ 1. If vol(I t ) ≤ vol(V )/3 then for any k > 1/φ, Pr vol(I t+k ) ≥ 2 vol(I t ) | I t > 1 - kφ (kφ -1) 2 • α.
The proof of Lemma 13 is identical to that of Lemma 9, except that, in (6), we do not bound max v∈N k deg(v) by ∆, but use instead that max

v∈N k deg(v) ≤ α • vol(I t ).
This inequality holds because each node v ∈ N k has degree bounded by α • max u∈I t+k-1 deg(u), and each node u ∈ I t+k-1 has degree at most vol(I t ): if u ∈ I t then deg(u) ≤ vol(I t ), and if u ∈ I t+k-1 -I t then deg(u) ≤ vol(I t+k-1 ) -vol(I t ) < vol(I t ), since vol(I t+k-1 ) < 2 vol(I t ).

Using Lemma 13, we show, as in Lemma 10, that O(log n/φ) rounds suffice w.h.p. to inform a 1/3 fraction of the total volume, but now we do not need the assumption that the source node has degree ∆. Precisely, we show that Pr(vol(I t ) ≥ vol(V )/3) ≥ 1-n -c for t = 2c ln n+4 log n • 4α/φ . From this and Lemma 11, the bound of Theorem 12 follows for PULL.

For PUSH, the O(log n/φ) bound is obtained by combining the above O(log n/φ) bound for PULL, with Lemma 7 on the symmetry between the two strategies.

Rumor Spreading and Graph Sparsification

In this section, we give an alternative proof that PUSH-PULL finishes in a number of rounds that is at most polynomial in log n/φ. The proof relies on an interesting connection between rumor spreading and the Spielman-Teng sparsification process [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF][START_REF] Spielman | Spectral sparsification of graphs[END_REF].

Theorem 14. Let G = (V, E) be a connected n-node graph with conductance φ. Then O(log 4 n/φ 6 ) rounds of PUSH-PULL suffice w.h.p. to spread to all nodes in G a message originated at an arbitrary source node.

The proof of Theorem 14 relates the volume expansion of the Spielman-Teng sparsification process, denoted st, to that of an edge sampling process, pp, which selects edges similarly to PUSH-PULL. Roughly, the volume expansion of an edge sampling process on G is the minimum, over all S ⊆ V , of the ratio vol G (S )/ vol G (S), where S is the set of vertices in V -S that are reachable from S via a sampled edge (Definition 15). Process st selects each edge uv independently with probability Υ/ min{deg(u), deg(v)}, where Υ = Θ(log 2 n/φ 4 ). Process pp on the other hand, chooses for each node u a number of Ψ = Θ(Υ • log n) edges incident to u at random with replacement, imitating the random choices of nodes in Ψ rounds of PUSH-PULL.

It has been shown that the subgraph sampled by st almost preserves certain spectral parameters of the original graph G. We use this result to show that the volume expansion of st is Ω(φ 2 ) (Lemma 21). We relate st and pp by showing that process pp stochastically dominates st, is the sense that there is a coupling of the two processes for which the edges selected by st are w.h.p. a subset of those selected by pp (Lemma 23); this is our key technical claim. Once we have established this dominance, we infer that the volume expansion of pp is at least that of st, i.e., Ω(φ 2 ). It follows that Ψ rounds of PUSH-PULL increase the volume of informed nodes by a factor of 1 + Ω(φ 2 ), and thus O(Ψ • log n/φ 2 ) = O(log 4 n/φ 6 ) rounds suffice to inform half of the total volume. A symmetric argument gives that O(log 4 n/φ 6 ) additional rounds suffice to inform the remaining graph.

Below, we first set some definitions and notation, in Section 6.1. Then we review Spielman-Teng sparsification and analyze its volume expansion in Section 6.2. Last, we relate that process to rumor spreading and prove Theorem 14 in Section 6.3.

Definitions

We start with some terminology on edge sampling processes.

Definition 15 (Edge Sampling & Volume Expansion). Let f be a (randomized) process selecting edges in graph G = (V, E). We denote by f (G) the spanning subgraph of G whose edge set consists of the edges selected by f . Process f may also associate a weight with each edge it selects, in which case f (G) is a weighted graph. The volume expansion of f on G, denoted β f,G , is the minimum over all non-empty sets S ⊂ V , of the ratio

3 vol G (Γ f (G) (S)) min{vol G (S), vol G (V -S)} .
Definition 15 above states that graph f (G) obtained by process f may have weights associated to its edges. Next we formalize various notions of weight we will use, and also extend the standard definition of conductance to take weights into account. The weighted conductance ϕ G of G is the minimum ϕ G (S) over all S for which w G (S) ≤ w G (V )/2.

In the notations above, we will omit subscript G whenever the graph is clear from the context.

Spectral Sparsification

Next we recall the Spielman-Teng spectral sparsification procedure.

Definition 18 (Spielman-Teng Sparsification). Given a graph G = (V, E), the Spielman-Teng sparsification process [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF][START_REF] Spielman | Spectral sparsification of graphs[END_REF], denoted st, is an edge sampling process which selects each edge uv ∈ E independently with probability

p uv := min 1, Υ min{deg(u), deg(v)} ,
where Υ > 0 is a parameter of the process. The process also assigns to each selected edge e a weight w e := p -1 e .

Note that since the weight of each edge in st(G) is inversely proportional to the edge selection probability, the expected weight of each vertex in st(G) is the same as the degree of that vertex in G.

It was shown in [START_REF] Spielman | Spectral sparsification of graphs[END_REF]Theorem 6.1] that if Υ = Ω(log 2 n/φ 4 G ), then with high probability, st(G) is an (1 + )-spectral approximation of graph G, i.e., it has the same Laplacian quadratic form as G within a factor of 1 + . This implies the following result, stating that st(G) approximately preserves cut weights, as well as the conductance of G -the latter within a quadratic exponent.

Lemma 19 (Properties of st). Let 0 < < 1/2 and c ≥ 1, and let G = (V, E) be an n-node graph with conductance φ. Suppose that we apply the st process on G with parameter

Υ ≥ 24c log(3n) φ 2 2
, and let G := st(G). Then with probability at least 1 -n -c , the following hold.

3 Recall that ΓG(S) = u∈S ΓG(u) -S.

Relating Sparsification to Rumor Spreading (Proof of Theorem 14)

We consider now the following edge sampling process, pp, which imitates the random choices of nodes in PUSH-PULL.

Definition 22 (Process pp). Let pp be an edge sampling processes which selects edges from a given graph G = (V, E) as follows. Let E u be the set of all edges e ∈ E incident to vertex u, and let Ψ > 0 be an integer parameter of the process. For each vertex u ∈ V , process pp draws Ψ edges from E u independently at random with replacement; let F u be the set of edges drawn for u. The total set of edges selected by pp is the union of all sets F u , u ∈ V .

Note that graph pp(G) is unweighted, unlike graph st(G).

The next lemma is our main technical claim, showing that w.h.p. the volume expansion of pp is at least equal to that of st, if Ψ = Ω(Υ • log n). The proof shows a coupling of pp and st under which st(G) is a subgraph of pp(G) w.h.p. For this coupling we consider a variant of st, denoted st 2 , which makes two (independent) attempts to select each edge uv: one attempt succeeds with probability Υ/ deg(u), and the other with probability Υ/ deg(v) 4 (thus, the total success probability is at least as high as for a single attempt with the probability p uv from Definition 18). We associate the first attempt with vertex u, and the second with v. This allows us to couple st 2 and pp by considering independently for each vertex u, the selections of the two processes: in st 2 we select each edge incident to u with probability Υ/ deg(u), while in pp we make Ψ = Ω(Υ • log n) independent choices selecting random edges incident to u with replacement; let L u and F u be the respective sets of selected edges. We are looking for a coupling that ensures L u ⊆ F u w.h.p. We observe that given |L u | = k, the set L u is just a random k-subset of the edges incident to u, and the same is true for Lemma 23 (Volume Expansion of pp). Let 0 < < 1/2 and c ≥ 1, and let G = (V, E) be an n-node graph with conductance φ. Suppose that we apply the pp process on G with parameter

Ψ ≥ 24c log(3n) φ 2 2 • (4c + 8) ln n. (14)
Then with probability at least 1 -2n -c , the volume expansion of pp on G is

β pp,G ≥ φ 2 G 4 (1 + ) 3 .
Proof. We show that there exists a coupling of processes pp and st, where pp has parameter Ψ satisfying ( 14) and st has parameter

Υ = 24c log(3n) φ 2 2 ,
such that with probability at least 1 -n -c , graph G := st(G) is a subgraph of Ĝ := pp(G). This implies that with probability at least 1 -n -c , for any set

S ⊆ V , vol G (Γ Ĝ(S)) ≥ vol G (Γ G(S)).
Combining that with Lemma 21, and using a union bound, proves Lemma 23. The rest of the proof demonstrates the coupling we promised above.

Coupling of pp and st: Let st be a process identical to st except that the probability of selecting edge uv is

p uv := min 1, Υ max{deg(u), deg(v)}
.

(Notice that we use max{deg(u), deg(v)} instead of min.) Consider now a process st 2 which executes independently st and st on G, and selects all edges picked by at least one of st and st . We will show a coupling of pp and st 2 for which st 2 (G) is a subgraph of pp(G) with probability 1 -n -c . This immediately implies a coupling of pp and st with the same property, since there is a trivial coupling of st 2 and st for which st(G) is a subgraph of st 2 (G) (with probability 1).

There is a convenient equivalent way to describe st 2 , along the lines of Definition 22 of pp: For each vertex u ∈ V , process st 2 chooses each edge e ∈ E u independently with probability min 1, Υ deg(u)

; let L u denote the set of edges chosen for u. Then the total set of edges selected by st 2 is the union of all L u , u ∈ V . This description is equivalent to the original definition of st 2 , because each edge uv ∈ E, where deg(u) ≤ deg(v), is added to L u with probability p uv and is independently added to L v with probability p uv . Observe that the random sets L u , u ∈ V , are mutually independent, similar to the sets F u in the definition of pp. For each u ∈ V , the cardinality of set L u follows the binomial distribution B deg(u), min 1, Υ deg(u)

. Moreover, for any 0 ≤ k ≤ deg(u), conditionally on |L u | = k, we have that L u is a uniformly random k-subset of E u . For pp on the other hand, we have that |F u | has the same distribution as C(deg(u), Ψ), in the statement of Lemma 3, i.e., the number of coupons collected in Ψ trials in the Coupon Collector's process with deg(u) coupons in total. Similar to L u , we have that F u is a uniformly random k-subset of E u , given |F u | = k.

We use the following coupling of the sets L u and F u . For each u ∈ V , we draw a sample u from distribution B deg(u), min 1, Υ deg(u)

and a sample f u from the distribution of C(deg(u), Ψ), and independently we choose a random permutation π u over the edges in E u . 5 Then we let L u be the set of the first u edges in permutation π u , and let F u be the set of the first f u edges in π u . From the discussion above, it follows that the marginal distributions of L u and F u are the correct ones.

To show that st 2 (G) is a subgraph of pp(G), i.e., u∈V L u ⊆ u∈V F u , it suffices to show that L u ⊆ F u for all u ∈ V . And this is equivalent, under the coupling above, to showing that u ≤ f u for all u ∈ V . We now show that u ≤ f u , for any u ∈ V , w.h.p.

For each vertex u ∈ V , we distinguish two cases depending on deg(u). We are now ready to prove our main result.

Proof of Theorem 14. In preparation to apply Lemma 24, we divide rumor spreading into phases of r rounds each, where r is as in [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF], i.e., r := 24c log(3n) φ 2 2

• (4c + 8) ln n.

Recall that I t denotes the set of informed nodes after the first t rounds and U t = V -I t . Let ρ := φ 2 4 (1 + ) 3 .

For each i ≥ 1, let X i be a binary random variable that is 1 if vol I (i-1)r -I ir ≥ ρ • min vol I (i-1)r , vol U (i-1)r ; otherwise, X i = 0. Lemma 24 implies that for each i ≥ 1, Pr(X i = 1) ≥ 1 -2n -c . Moreover, it is easy to see that I ir = V (i.e., not all nodes are informed after ir rounds) implies 1≤j≤i X j < 2 ln 1+ρ (vol(V )/2). By a union bound, the probability that X j = 1 for all j ≤ i is at least 1 -in -c . It follows that for i = 2 ln 1+ρ (vol(V )/2), we have I ir = V with probability at least 1 -ln 1+ρ (vol(V )/2) • n -c = 1 -Ω(n -c log n/ρ) = 1 -Ω(n -c+4 log n), where for the last equation we used that φ = Ω(1/n 2 ) for any connected n-node graph. It follows that, with the above probability, the number of rounds before all nodes get informed is at most r • 2 ln 1+ρ (vol(V )/2) = O(log 4 n/ρφ 4 ) = O(log 4 n/φ 6 ).

  (a) E[L] = |D|. (b) Var[L] ≤ |D| • max v∈N deg(v), where N is the set of nodes v ∈ U t incident to some edge in D.

Lemma 11 .

 11 If vol(I t ) ≥ vol(V )/3, then Pr(U t+k = ∅ | I t ) ≥ 1 -n -c , for k = 2(c + 2) ln n/φ .

Definition 16 (

 16 Weights). Let G = (V, E, w) be a weighted graph where each edge e ∈ E has weight w e . The weight of a set of edges E ⊆ E is w G (E ) := e∈E w e ; the weight of a vertex u ∈ V is w G (v) := v∈Γ(u) w uv ; and the weight of a set of vertices S ⊆ V is w G (S) := u∈S w G (u). Definition 17 (Weighted Conductance). Consider a weighted graph G = (V, E, w). The weighted conductance of a non-empty vertex set S in graph G is ϕ G (S) := w G (cut G (S, V -S)) w G (S) .

  F u , given |F u | = k. It follows that the desired coupling exists, if |L u | is stochastically dominated by |F u |. We have that |L u | is distributed like binomial random variable B(deg(u), Υ/ deg(u)), while |F u | is distributed like Coupon Collector's random variable C(deg(u), Ψ) (see Lemma 3). We then use Lemma 3 to show the desired stochastic dominance of B(deg(u), Υ/ deg(u)) by C(deg(u), Ψ).

• 2 G 4 ( 1 + ) 3 •

 2413 Case Υ/ deg(u) ≥ 1/4: We apply Equation (1) of Lemma 3, for k = deg(u) and t = Ψ, to get PrC(deg(u), Ψ) < deg(u) ≤ deg(u) • e -Ψ/ deg(u) ≤ n • e -Υ•(4c+8) ln n/ deg(u)≤ n • e -(4c+8) ln n/4 , by the case hypothesis = n -c-1 .It follows that Pr(f u < deg(u)) ≤ n -c-1 , and since u ≤ deg(u), we havePr(f u ≥ u ) ≥ 1 -n -c-1 .Proof. For each u ∈ V , let V u denote the set of neighbors that u selects during the r rounds of PUSH-PULL. The edge sets {uv : v ∈ V u }, u ∈ V , are distributed identically to the sets F u selected by pp, when pp is applied to G with parameter Ψ = r. It follows that, if S is the set of vertices u ∈ V -S that either select or are selected by at east one neighbor from S during PUSH-PULL, then vol G (S ) has the same distribution as vol G (Γ pp(G) (S)). By the definition of volume expansion,vol G (Γ pp(G) (S)) ≥ β pp,G • min{vol G (S), vol G (V -S)},and applying Lemma 23, gives that vol G (Γ pp(G) (S)) ≥ φ min{vol G (S), vol G (V -S)}, with probability at least 1 -n -c . The claim now follows, because all vertices u ∈ S get informed during PUSH-PULL, since they communicate with at least one informed neighbor from S.

This paper is the result of a series of intermediate steps[START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF][START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF][START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF]. Paper[START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF] was the first to show the connection between rumor spreading and conductance. By using a different approach,[START_REF] Chierichetti | Almost tight bounds for rumour spreading with conductance[END_REF] followed up with an almost tight solution to the problem. Finally,[START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF] improved the latter approach introducing new ideas, obtaining a tight solution.

In fact, it is not important how set D k ⊆ cut(I t+k-1 , U t+k-1 ) is chosen, as long as it is fixed before round t + k, and has size M .

Formally, the probabilities are min{1, Υ/ deg(u)} and min{1, Υ/ deg(v)}, respectively, but for simplicity we omit the "min" in this informal overview.

Samples u and fu do not need to be independent.

* Supported in part by the ERC Starting Grant DMAP 680153, by a Google Focused Research Award and by the SIR Grant RBSI14Q743.

† Supported in part by the ANR NDFusion grant. ‡ This author was kindly supported by faculty awards of Yahoo! Research, IBM and Google.

(a) For any S ⊆ V ,

(b) The weighted conductance ϕ G of G satisfies

Remark 20. As already mentioned, [START_REF] Spielman | Spectral sparsification of graphs[END_REF]Theorem 6.1] is more general than our Lemma 19, proving that G is an (1 + )-spectral approximation of G. This immediately implies the weaker notion of (1 + )-cut approximation stated in ( 9) [START_REF] Batson | Spectral sparsification of graphs: Theory and algorithms[END_REF]. To obtain [START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF] we use the fact that the (1 + )-spectral approximation implies that the eigenvalues of the Laplacians of G and G differ by at most a factor of (1 + ). Then we apply Cheeger's Inequality [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF][START_REF] Chung | Spectral Graph Theory[END_REF], stating that for any unweighted or weighted graph with (weighted) conductance φ the smallest non-zero eigenvalue λ of its normalized Laplacian satisfies φ 2 /2 ≤ λ ≤ 2φ.

Using Lemma 19, we show now that the volume expansion of st is Ω(φ 2 G ) w.h.p.

Lemma 21 (Volume Expansion of st). Under the same assumptions as in Lemma 19, with probability at least 1 -n -c , the volume expansion of st on G is

Proof. Lemma 19(a), applied for a singleton set S = {u}, implies that for any u ∈ V ,

From this, it follows that for any T ⊆ V , the volume of

We now proceed to derive [START_REF] Chung | Spectral Graph Theory[END_REF]. Applying [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF] for T = Γ G(S), we obtain

where the last inequality holds because cut G(S, V -S) is just a subset of the edges incident to vertices in Γ G(S). From the definition of weighted conductance, [START_REF] Chierichetti | Rumour spreading and graph conductance[END_REF].

Substituting that to [START_REF] Doerr | Social networks spread rumors in sublogarithmic time[END_REF] and using the definition of β st,G , we obtain [START_REF] Chung | Spectral Graph Theory[END_REF].

We apply Equation (2) of Lemma 3, for k = deg(u), t = Ψ and the above value of λ, to get

Using Lemma 4(a) to bound the probability in the last line above, gives

Next we bound the probability that u ≥ λ. We have λ ≥ 2Υ, because 2Υ ≤ deg(u)/2 by the case hypothesis, and 2Υ ≤ Ψ/4 for the chosen values of Υ and Ψ. Then,

Combining that with [START_REF] Doerr | Quasirandom rumor spreading: Expanders, push vs. pull, and robustness[END_REF], and applying a union bound, gives

Therefore, in both cases above it holds

Then, by a union bound, the probability that f u ≥ u for all u ∈ V , is at least 1 -n -c . This completes the proof of Lemma 23.

The next claim follows from Lemma 23, and the analogy between the random choices made by pp and PUSH-PULL.