Document Open Access Logo

Randomized Rumor Spreading Revisited

Authors Benjamin Doerr, Anatolii Kostrygin



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.138.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin Doerr
Anatolii Kostrygin

Cite AsGet BibTex

Benjamin Doerr and Anatolii Kostrygin. Randomized Rumor Spreading Revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.138

Abstract

We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a G(n,p) random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(-Omega(r)). We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Theta(n*log(log(n))) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Theta(n*log(n)). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the $\Theta(n*log(log(n))) message complexity.
Keywords
  • Epidemic algorithm
  • rumor spreading
  • dynamic graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Noam Berger, Christian Borgs, Jennifer T. Chayes, and Amin Saberi. On the spread of viruses on the internet. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 301-310. SIAM, 2005. URL: http://dx.doi.org/10.1145/1070432.1070475.
  2. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 961-970, 2012. URL: http://dx.doi.org/10.1145/2213977.2214064.
  3. Keren Censor-Hillel and Hadas Shachnai. Partial information spreading with application to distributed maximum coverage. In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 161-170, 2010. URL: http://dx.doi.org/10.1145/1835698.1835739.
  4. Keren Censor-Hillel and Hadas Shachnai. Fast information spreading in graphs with large weak conductance. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 440-448, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.35.
  5. Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Rumor spreading in social networks. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 375-386. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02930-1_31.
  6. Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Almost tight bounds for rumour spreading with conductance. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 399-408. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806745.
  7. Andrea E. F. Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Francesco Pasquale, and Riccardo Silvestri. Rumor spreading in random evolving graphs. Random Structures and Algorithms, 48:290-312, 2016. URL: http://dx.doi.org/10.1002/rsa.20586.
  8. Sebastian Daum, Fabian Kuhn, and Yannic Maus. Rumor spreading with bounded in-degree. CoRR, abs/1506.00828, 2015. Google Scholar
  9. Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, and Douglas B. Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 1-12. ACM, 1987. URL: http://dx.doi.org/10.1145/41840.41841.
  10. Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. Social networks spread rumors in sublogarithmic time. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 21-30. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993640.
  11. Benjamin Doerr, Anna Huber, and Ariel Levavi. Strong robustness of randomized rumor spreading protocols. Discrete Applied Mathematics, 161:778-793, 2013. URL: http://dx.doi.org/10.1016/j.dam.2012.10.014.
  12. Benjamin Doerr and Marvin Künnemann. Tight analysis of randomized rumor spreading in complete graphs. In Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 82-91. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973204.8.
  13. Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1:447-460, 1990. URL: http://dx.doi.org/10.1002/rsa.3240010406.
  14. Nikolaos Fountoulakis, Anna Huber, and Konstantinos Panagiotou. Reliable broadcasting in random networks and the effect of density. In Proceedings of the 29th International Conference on Computer Communications (INFOCOM), pages 2552-2560. IEEE, 2010. URL: http://dx.doi.org/10.1109/INFCOM.2010.5462084.
  15. Nikolaos Fountoulakis, Konstantinos Panagiotou, and Thomas Sauerwald. Ultra-fast rumor spreading in social networks. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1642-1660. SIAM, 2012. Google Scholar
  16. Alan M. Frieze and Geoffrey R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57-77, 1985. URL: http://dx.doi.org/10.1016/0166-218X(85)90059-9.
  17. Mohsen Ghaffari and Calvin Newport. How to discreetly spread a rumor in a crowd. CoRR, abs/1607.05697, 2016. Google Scholar
  18. George 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. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2011.57.
  19. George Giakkoupis. Tight bounds for rumor spreading with vertex expansion. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 801-815. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.59.
  20. Bernhard Haeupler. Simple, fast and deterministic gossip and rumor spreading. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 705-716, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.51.
  21. Konrad Iwanicki and Maarten van Steen. Gossip-based self-management of a recursive area hierarchy for large wireless sensornets. IEEE Transactions on Parallel and Distributed Systems, 21:562-576, 2010. URL: http://dx.doi.org/10.1109/TPDS.2009.89.
  22. Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. Randomized rumor spreading. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 565-574. IEEE, 2000. Google Scholar
  23. Marcos A. Kiwi and Christopher Thraves Caro. FIFO queues are bad for rumor spreading. IEEE Trans. Information Theory, 63:1159-1166, 2017. URL: http://dx.doi.org/10.1109/TIT.2016.2632153.
  24. Jon M. Kleinberg. The convergence of social and technological networks. Communications of the ACM, 51:66-72, 2008. URL: http://dx.doi.org/10.1145/1400214.1400232.
  25. Miguel Matos, Valerio Schiavoni, Pascal Felber, Rui Oliveira, and Etienne Riviere. BRISA: combining efficiency and reliability in epidemic data dissemination. In 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 983-994, 2012. URL: http://dx.doi.org/10.1109/IPDPS.2012.92.
  26. Damon Mosk-Aoyama and Devavrat Shah. Fast distributed algorithms for computing separable functions. IEEE Trans. Information Theory, 54:2997-3007, 2008. URL: http://dx.doi.org/10.1109/TIT.2008.924648.
  27. Konstantinos Panagiotou, Ali Pourmiri, and Thomas Sauerwald. Faster rumor spreading with multiple calls. The Electronic Journal of Combinatorics, 22:P1.23, 2015. Google Scholar
  28. Boris Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47:213-223, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail