Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T08:24:30.528Z Has data issue: false hasContentIssue false
  • English
  • Français

The string of diamonds is nearly tight for rumour spreading

Part of: Graph theory Combinatorial probability Theory of computing Algorithms - Computer Science

Published online by Cambridge University Press:  04 November 2019

Omer Angel ,
Abbas Mehrabian  and
Yuval Peres
Omer Angel
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver, BC, V6T 1Z2, Canada
Abbas Mehrabian*
Affiliation:
Department of Computer Science, University of British Columbia, Vancouver, BC, V6T 1Z4, Canada
Yuval Peres
Affiliation:
Microsoft Research, Redmond, WA98052, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstarct

For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O({n^{1/3}}{\log ^{2/3}}n)$. This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. We also show that if, for a pair α, β of real numbers, there exist infinitely many graphs for which the two spread times are nα and nβ in expectation, then $0 \le \alpha \le 1$ and $\alpha \le \beta \le {1 \over 3} + {2 \over 3} \alpha $; and we show each such pair α, β is achievable.

MSC classification

Primary: 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Secondary: 05C81: Random walks on graphs 60C05: Combinatorial probability 68W15: Distributed algorithms
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 190 - 199
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

A preliminary version of this paper appeared in Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM’2017). This full version includes a new result, namely Theorem 2.5.

§

Supported by NSERC.

Supported by an NSERC Postdoctoral Fellowship and a Simons–Berkeley Research Fellowship. Part of this work was done while this author was at the Simons Institute for the Theory of Computing at UC Berkeley. Currently at McGill University.

References

Acan, H., Collevecchio, A., Mehrabian, A. and Wormald, N. (2017) On the push&pull protocol for rumor spreading. SIAM J. Discrete Math. 31 647–668.CrossRefGoogle Scholar
Auffinger, A., Damron, M. and Hanson, J. (2017) 50 Years of First-Passage Percolation, Vol. 68 of University LectureSeries, American Mathematical Society.Google Scholar
Boyd, S., Ghosh, A., Prabhakar, B. and Shah, D. (2006) Randomized gossip algorithms. IEEE Trans. Inform. Theory 52 2508–2530.CrossRefGoogle Scholar
Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D. and Terry, D. (1987) Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC ’87), ACM, pp. 1–12.CrossRefGoogle Scholar
Doerr, B., Fouz, M. and Friedrich, T. (2012) Experimental analysis of rumor spreading in social networks. In Design and Analysis of Algorithms, Vol. 7659 of Lecture Notes in Computer Science, Springer, pp. 159–173.CrossRefGoogle Scholar
Durrett, R. (1989) Stochastic growth models: Recent results and open problems. In Mathematical Approaches to Problems in Resource Management and Epidemiology (Ithaca, NY, 1987), Vol. 81 of Lecture Notes in Biomathematics, Springer, pp. 308–312.CrossRefGoogle Scholar
Feige, U., Peleg, D., Raghavan, P. and Upfal, E. (1990) Randomized broadcast in networks. Random Struct. Alg. 1 447–460.CrossRefGoogle Scholar
Giakkoupis, G., Nazari, Y. and Woelfel, P. (2016) How asynchrony affects rumor spreading time. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC ’16), ACM, pp. 185–194.CrossRefGoogle Scholar
Hammersley, J. M. and Welsh, D. J. A. (1965) First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory, Springer, pp. 61–110.Google Scholar
Karp, R., Schindelhauer, C., Shenker, S. and Vöcking, B. (2000) Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE, pp. 565–574.CrossRefGoogle Scholar
Richardson, D. (1973) Random growth in a tessellation. Proc. Cambridge Philos. Soc. 74 515–528.CrossRefGoogle Scholar