# «Abstract. We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as deﬁned by Barab´si and a √ ...»

Furthermore by E4, every i n1/5 is useful. The following properties of non-useful nodes were proved in [11].

Lemma 4. With probability 1 − o(1), the following event holds

• E6 := {degG (v) ≤ 5m log2 n for all non-useful v}.

** Lemma 5. Assume that E6 holds.**

With prob. 1 − n−1/5+o(1), we have

Lemma 6 (Bollob´s and Riordan [2]). Let v be a ﬁxed non-useful a node. Then for all k ∈ [m], the prob. that v,k is a useful node is at least log−3 n. This event is independent from all other random decisions v,k with (v, k ) = (v, k).

Note that in the original lemma, the authors only state a bound on the probability that v,1 is a useful node. However, the same proof yields the above version. Also, Lemma 6 remains valid if we condition on E6.

4.3 Informing the ﬁrst useful node Let G = Gm (W1,..., Wn ) be a typical social network. Assume that also E6 and E7 hold. In this section, all probabilities are taken over the product space of the random graph G and the random decisions of the rumor spreading process.

** Lemma 7. Let u be a ﬁxed node.**

The rumor initiated by u reaches a useful node in time O((log log n)2 ) with probability 1 − o(1), and in time O(log n) with probability 1 − o(n−2 ).

4.4 Informing node 1 Similar to the synchronized case, we use constant degree nodes to establish fast links between large degree nodes. More precisely, once a neighbor of a constant degree node is informed, the time until it has pulled the rumor from this neighbor and pushed it to one speciﬁc neighbor is (essentially) exponentially distributed. Thus, independent of their own degrees, two nodes that are connected via a third node of constant degree exchange information in time exponentially distributed.

Starting from one informed useful node, we study how fast the rumor spreads to the surrounding ‘neighborhoods’ of nodes. We consider neighborhoods alternating between small nodes and good nodes i of relatively large weight wi. The small nodes act as fast links between the levels of good nodes that ensure a large expansion. In particular, we make use of the fact that a good node i has a high degree and since every small neighbor of i independently pulls the rumor in time exponentially distributed, we can argue that a considerable fraction of the small neighbors of i will be informed very fast. The more neighbors of informed nodes there are, the faster the rumor will spread to suﬃciently many neighbors that form the next level of informed node. In contrast, in the synchronized case, it would always take at least one time step for a neighbor to pull the rumor.

We consider informed neighborhoods at suitably chosen time steps on the continuous time line. The smaller these steps are chosen, the smaller the achieved expansion factor is at each step. On the other hand, smaller time steps allow us to progress faster through the diﬀerent neighborhood levels. By carefully choosing each step size, we can balance out these opposing eﬀects in order to achieve the following runtime.

** Theorem 2. Let W1,.**

.., Wn be such that E1,..., E5 are satisﬁed. Let G be a random graph from Gm (W1,..., Wn ). Let v ∈ [n] be a useful node.

With probability 1 − o(n−1 ), using the asynchronous push-pull protocol, a √ rumor present at v reaches node 1 in O( log n) steps.

For our argument using fast links, we will need many nodes of constant degree. The following simple lemma proves that there is a linear number of nodes i ∈ 3 n, n that have a degree equal to m. We call such nodes small. If not explicitly stated, all probabilities in this section are taken over the random graph Gm (W1,..., Wn ), where W1,..., Wn are given numbers that satisfy properties E1,..., E5.

** Lemma 8. Let εm := 8 e−3m.**

With probability 1 − e−Ω(n), there are at least εm n small nodes in 2 n, n.

where, as before, s = 2a is the smallest power of 2 larger than log10 n and 2b is the largest power of 2 smaller than 2 n. Let u be a useful node.

Let t0 t0 t1 t1... denote discrete time steps to be speciﬁed later. We consider neighborhoods of u that are informed in these time intervals. In particular, we deﬁne sets Γk and Γk recursively as follows.

We set Γ0 = {u}. Given the set Γk, Γk consists of all small nodes i ≥ 3 n that contact a neighbor in Γk in time [tk, tk ] and have not been included in any Γ with ≤ k − 1. Similarly, Γk is deﬁned as the set of all good nodes that are contacted by a neighbor in Γk−1 in time [tk−1, tk ] and have not been included in any Γ with ≤ k − 1. Note that for all k ≥ 0, Γk only contains nodes i 2 n, while Γk only contains nodes i ≥ 2 n. This is true for Γ0 since u is useful and by E5, all useful nodes are smaller than n/2. We deﬁne the weight of a set Γk by

We denote by Nk = Γ0 ∪ Γ1 ∪ · · · ∪ Γk (note that the Γi are not included). Let C0 ⊆ 3 n, n be the set of small nodes and for k ≥ 1, let Ck = C0 \ {Γ0,..., Γk−1 } be the set of small nodes excluding nodes in Γ0, Γ1,..., Γk−1. By Lemma 8, we have C0 ≥ εm n with probability 1 − e−Ω(n).

The next lemma shows that we achieve an exponential expansion in terms of fk in each level as long as there is still a linear number of small nodes in Ck and similarly, as long as for each interval It := [2t + 1, 2t+1 ], where t ∈ [a, b), there are still 2t−2 good nodes that are not Nk.

** Lemma 9. Let c 0 be a suﬃciently large constant, k ≥ 0 be such √ that log4 (n)/ n ≥ fk ≥ log2 (n)/n and |Ck | ≥ εm n/2.**

Let ∆k = −1/2 c log2 (εm fk n/ log2 n). Set tk := tk + ∆k and tk+1 := tk + ∆k. Then given Ck and Γ0, Γ0, Γ1, Γ1,..., Γk, with prob. 1 − O(n−6/5 ), one of the following is satisﬁed. (i) |Nk+1 ∩ It | ≥ 2t−2, for some t ∈ [a, b), or (ii) fk+1 ≥ 2fk.

**5 Conclusion**

We have shown that for PA graphs the asynchronous push-pull proto col informs almost all nodes in O( log n) time. This shows, in an even ˜ stronger way than the previous Θ(log n) bounds for the synchronized protocol [11], that randomized rumor spreading is very eﬀective in network topologies resembling real-world networks.

From a broader perspective, our result also indicates that in naturally asynchronous settings, it might be a misleading oversimpliﬁcation to assume a synchronized protocol.

**Bibliography**

[1] A.-L. Barab´si and R. Albert. Emergence of scaling in random neta works. Science, 286:509–512, 1999.

[2] B. Bollob´s and O. Riordan. The diameter of a scale-free random a graph. Combinatorica, 24:5–34, 2004.

[3] B. Bollob´s and A. Thomason. On Richardson’s Model on the Hya percube. Cambridge University Press, 1997.

[4] B. Bollob´s, O. Riordan, J. Spencer, and G. Tusn´dy. The degree a a sequence of a scale-free random graph process. Random Structures & Algorithms, 18:279–290, 2001.

[5] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52:2508– 2530, 2006.

[6] F. Chierichetti, S. Lattanzi, and A. Panconesi. Almost tight bounds for rumour spreading with conductance. In 42nd ACM Symposium on Theory of Computing (STOC), pages 399–408, 2010.

[7] F. Chierichetti, S. Lattanzi, and A. Panconesi. Rumor spreading in social networks. Theoretical Computer Science, 412:2602–2610, 2011.

[8] F. R. K. Chung and L. Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1:91–113, 2003.

[9] A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. E. Sturgis, D. C. Swinehart, and D. B. Terry. Epidemic algorithms for replicated database maintenance. Operating Systems Review, 22:8–32, 1988.

[10] B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 366–377, 2009.

[11] B. Doerr, M. Fouz, and T. Friedrich. Social networks spread rumors in sublogarithmic time. In 43rd ACM Symposium on Theory of Computing (STOC), pages 21–30, 2011.

[12] S. Dommers, R. van der Hofstad, and G. Hooghiemstray. Diameters in preferential attachment models. Journal of Statistical Physics, 139:72–107, 2010.

[13] R. Els¨sser. On the communication complexity of randomized broada casting in random-like graphs. In 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 148–157, 2006.

[14] M. Evans, N. Hastings, and B. Peacock. Statistical Distributions.

John Wiley & Sons, Inc., 3rd edition, 2000.

[15] U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures & Algorithms, 1:447–460, 1990.

[16] J. A. Fill and R. Pemantle. Percolation, ﬁrst-passage percolation, and covering times for Richardson’s model on the n-cube. Annals of Applied Probability, 3:593–629, 1993.

[17] N. Fountoulakis and K. Panagiotou. Rumor spreading on random regular graphs and expanders. In 14th International Workshop on Randomization and Computation (RANDOM), pages 560–573, 2010.

[18] N. Fountoulakis, K. Panagiotou, and T. Sauerwald. Ultra-fast rumor spreading in social networks. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1642–1660, 2012.

[19] A. M. Frieze and G. R. Grimmett. The shortest-path problem for

**graphs with random arc-lengths. Discrete Applied Mathematics, 10:**

57–77, 1985.

[20] G. Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 57–68, 2011.