LIPIcs.APPROX-RANDOM.2017.26.pdf
- Filesize: 486 kB
- 9 pages
Document
The String of Diamonds Is Tight for Rumor Spreading
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-08-11
File
Document Identifiers
Cite As Get BibTex
Omer Angel, Abbas Mehrabian, and Yuval Peres. The String of Diamonds Is Tight for Rumor Spreading. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.26
Abstract
For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor 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 (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.
Subject Classification
Keywords
- randomized rumor spreading
- push&pull protocol
- asynchronous time model
- string of diamonds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hüseyin Acan, Andrea Collevecchio, Abbas Mehrabian, and Nick Wormald. On the push&pull protocol for rumor spreading. SIAM Journal on Discrete Mathematics, 31(2):647-668, 2017. Available in https://arxiv.org/abs/1411.0948 (conference version in PODC'15). URL: http://dx.doi.org/10.1137/15M1033113.
-
A. Auffinger, M. Damron, and J. Hanson. 50 years of first passage percolation. arXiv, 1511.03262 [math.PR], 2016.
- Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Trans. Inform. Theory, 52(6):2508-2530, 2006. URL: http://dx.doi.org/10.1109/TIT.2006.874516.
- Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC'87, pages 1-12, New York, NY, USA, 1987. ACM. URL: http://dx.doi.org/10.1145/41840.41841.
- B. Doerr, M. Fouz, and T. Friedrich. Experimental analysis of rumor spreading in social networks. In Design and analysis of algorithms, volume 7659 of Lecture Notes in Comput. Sci., pages 159-173. Springer, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34862-4_12.
- R. Durrett. Stochastic growth models: recent results and open problems. In Mathematical approaches to problems in resource management and epidemiology (Ithaca, NY, 1987), volume 81 of Lecture Notes in Biomath., pages 308-312. Springer, Berlin, 1989. URL: http://dx.doi.org/10.1007/978-3-642-46693-9_21.
- Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. Randomized broadcast in networks. Random Structures Algorithms, 1(4):447-460, 1990. URL: http://dx.doi.org/10.1002/rsa.3240010406.
- G. Giakkoupis, Y. Nazari, and P. Woelfel. How asynchrony affects rumor spreading time. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC'16, pages 185-194, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933057.2933117.
-
J. M. Hammersley and D. J. A. Welsh. First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory, pages 61-110. Springer Berlin Heidelberg, Berlin, Heidelberg, 1965.
- S. Janson. Tail bounds for sums of geometric and exponential variables. Available in URL: http://www2.math.uu.se/~svante/papers/sjN14.pdf.
- R. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 565-574, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892324.
-
D. Richardson. Random growth in a tessellation. Proc. Cambridge Philos. Soc., 74:515-528, 1973.