Project topics and materials
Get Complete Project Material File(s) Now! »
Asynchronous Rumor Spreading
Now we discuss the relations between spreading time for the synchronous and asynchronous rumor speading. The fundamental question is what are the minimum and maximum spreading times in arbitrary n-vertex graph G? The answer was given by Acan, Collevecchio, Mehrabian, and Wormald [ACMW14]. Considering the basic push-pull protocol, they obtained the tight bounds, up to the constant factor cited in this section as Theorems II.1|II.4. For the guaranteed and average spreading time we will follow the notation of Acan et al. Thus, gsta(G) and gsts(G) mean the guaranteed spreading time of graph G in asynchronous and synchronous modes, respectively. Correspondingly, wasta(G) and wasts(G) { the worst average spreading time of graph G in asynchronous and synchronous modes. Their rst result compares the guaranteed and the worst average spreading time in the asynchronous setting.
Tight Bounds via a Target-Failure Calculus
We rst describe how we obtain estimates for the rumor spreading time that are tight apart from additive constants. Our strategy is close to the one seen in [DK14] brie y discussed is previous section. It is easy to compute the expected number E(k) of newly informed nodes in a round starting with k informed nodes, e.g., for the classic push protocol, E(k) = k (k2=n). For each number k of informed nodes, we formulate a pessimistic round target E0(k) that is suciently below or above the expected number E(k) of newly informed nodes. Here \suciently away » means that the probability q(k) to fail the target is small, but not necessarily o(1) as in all previous analyses. When proving upper bounds on rumor spreading times, we see that the expected time to go from k to at least E0(k) informed nodes is at most 1 + q(k) 1q(k) , simply with the argument that in the case of a failure, we can try again (this needs some elementary monotonicity statements for the q(k) and E0(k)). The second, again elementary, key argument still in the language of the push protocol is that when we dene a sequence of round targets by k0 := 1, k1 := E0(k0), k2 := E0(k1); : : : with suitably dened E0(), then the ki grow almost like 2i. More precisely, there is a T = log2 n O(1) such that kT = (n). Hence together with the previous paragraph we obtain that the expected number of rounds to reach kT informed nodes is PT1 i=0 1 + q(ki) 1q(ki) = T + O( PT1 i=0 q(ki)). So it suces that the sum of the failure probabilities q(ki) is a constant (unlike in previous works, where it needed to be o(1)).
Uniform Treatment of Many Rumor Spreading Processes
As discussed earlier, the previous works regarding dierent rumor spreading processes on complete graphs all had to use dierent arguments. The reason is that the processes, even when looking similar, are intrinsically dierent when looking at detail. As an example, let us consider the rst few rounds of the push and the pull protocol. In the push protocol, we just have just seen that while there are at most o(pn) nodes informed, then a birthday paradox type argument gives that with high probability we have perfect doubling in each round. For the pull process, in which each uninformed node calls a random node and becomes informed when the latter was informed, we also easily compute that a round starting with k informed nodes creates an expected number of (n k) k n = k k2 n newly informed nodes. However, since these are binomially distributed, there is no hope for perfect doubling. In fact, for the rst few rounds, we even have a constant probability that no single node becomes informed. The only way to uniformly treat such dierent processes is by making the analysis which depends only on general parameters of the process as opposed to the precise denition. Our second main contribution is distilling a few simple conditions that (i) subsume essentially all symmetric and time-invariant rumor spreading processes on complete graphs and (ii) suce to prove rumor spreading times via the above described target-failure method. All this is made possible by the observation that the target-failure method needs much less in terms of failure probabilities than previous approaches. Consequently, instead of using Cherno and Azuma bounds for independent or negatively correlated random variables (which rely on the precise denition of the process), it suces to estimate the number of newly informed nodes via computing the expectation and using Chebyshev’s inequality as concentration result. Consequently, to apply our method we only need to (i) understand (with a certain precision) the probability pk that an uninformed node becomes informed in a round starting with k informed nodes (recall that we assumed symmetry, that is, this probability is the same for all uninformed nodes) and (ii) we need to have a mild upper bound on the covariance of the indicator random variables of the events that two nodes become informed. Note that for most of the known protocols these events rather tend to be negatively correlated. The probabilities pk usually are easy to compute from the protocol denition. Also, we do not know them precisely. For example, for the growth phase of the push protocol discussed above, it suces to know that there are constants a < 2 and a0 such that for all k < n=2 we have k n(1 ak n) pk k n(1 + a0 k n). This (together with the mild covariance condition to be detailed later) is enough to show that the rumor spreading process takes log2 n O(1) rounds to inform n=2 nodes or more. We prot from the fact that seemingly all reasonable rumor spreading processes in complete networks can be described via three regimes.
Table of contents :
Resume Substantiel
Contents
List of Figures
List of Table
I Introduction
1 What Is Rumor Spreading
2 Motivation
3 State of the Art
4 Our Contribution
5 Plan of the Work
II Overview of Gossip Protocols
1 Classic Results
1.1 Denition of Rumor Spreading
1.2 Independent Random Phone-Call Model
1.3 Asynchronous Rumor Spreading
1.4 Path, Square Lattice, Star, Necklace
1.5 Complete Graph. Overview of the Proofs
2 Precise Statements of Our Results
2.1 Tight Bounds via a Target-Failure Calculus
2.2 Uniform Treatment of Many Rumor Spreading Processes .
2.3 Precise Statement of the Technical Results
2.4 Applying the Above Technical Results
2.5 Limitations of the Phase Method
IIIMain Analysis Technique
1 Homogeneous Rumor Spreading Processes
2 Exponential Growth Regime
2.1 Upper Bound
2.2 Lower Bound
3 Exponential Shrinking Regime
3.1 Upper Bound
3.2 Lower Bound
4 Double Exponential Shrinking Regime
4.1 Upper Bound
4.2 Lower Bound
IV Applications of our Method
1 Classic Protocols
1.1 Push Protocol
1.2 Pull Protocol
1.3 Push-Pull Protocol
2 Robustness, Multiple Calls, and Dynamic Graphs
2.1 Transmission Failures
2.2 Multiple Calls
2.3 Dynamic Graphs
3 Limited Incoming Calls Capacity
3.1 Single Incoming Call Push-Pull Protocol
3.2 Single Incoming Call Pull-Only Protocol
3.3 Push-Pull Protocol with Transition Time
V Non-Homogeneous Rumor Spreading
1 Two-State Multi-Parametric Process
2 Multi-State Rumor Spreading. Independent Stop Process
2.1 One Push Call per Node
2.2 Pull Protocol with C 1 Push Calls:
2.3 Random Stop Decision
3 Multiparametric exponential growth
VI Summary
1 Outlook
2 Open Problems
A Probabilistic notions
B First Order Bounds
C Coupon Collector and Ball into Bins
Bibliography
