Robustness of Randomized Rumour Spreading

Authors Rami Daknama, Konstantinos Panagiotou, Simon Reisser



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.36.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Rami Daknama
  • Department of Mathematics, Ludwig-Maximilians-Universität München, Germany
Konstantinos Panagiotou
  • Department of Mathematics, Ludwig-Maximilians-Universität München, Germany
Simon Reisser
  • Department of Mathematics, Ludwig-Maximilians-Universität München, Germany

Cite AsGet BibTex

Rami Daknama, Konstantinos Panagiotou, and Simon Reisser. Robustness of Randomized Rumour Spreading. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.36

Abstract

In this work we consider three well-studied broadcast protocols: push, pull and push&pull. A key property of all these models, which is also an important reason for their popularity, is that they are presumed to be very robust, since they are simple, randomized, and, crucially, do not utilize explicitly the global structure of the underlying graph. While sporadic results exist, there has been no systematic theoretical treatment quantifying the robustness of these models. Here we investigate this question with respect to two orthogonal aspects: (adversarial) modifications of the underlying graph and message transmission failures. We explore in particular the following notion of local resilience: beginning with a graph, we investigate up to which fraction of the edges an adversary may delete at each vertex, so that the protocols need significantly more rounds to broadcast the information. Our main findings establish a separation among the three models. On one hand pull is robust with respect to all parameters that we consider. On the other hand, push may slow down significantly, even if the adversary is allowed to modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, push&pull is robust when no message transmission failures are considered, otherwise it may be slowed down. On the technical side, we develop two novel methods for the analysis of randomized rumour spreading protocols. First, we exploit the notion of self-bounding functions to facilitate significantly the round-based analysis: we show that for any graph the variance of the growth of informed vertices is bounded by its expectation, so that concentration results follow immediately. Second, in order to control adversarial modifications of the graph we make use of a powerful tool from extremal graph theory, namely Szemerédi’s Regularity Lemma.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Rumour Spreading
  • Local Resilience
  • Robustness
  • Self-bounding Functions
  • Szemerédi’s Regularity Lemma

Metrics

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

References

  1. Hüseyin Acan, Andrea Collevecchio, Abbas Mehrabian, and Nick Wormald. On the push&pull protocol for rumour spreading. In Extended Abstracts Summer 2015, pages 3-10. Springer, 2017. Google Scholar
  2. 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). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  3. Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Advanced Lectures on Machine Learning, pages 208-240. Springer, 2004. Google Scholar
  4. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE/ACM Transactions on Networking (TON), 14(SI):2508-2530, 2006. Google Scholar
  5. Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 961-970. ACM, 2012. Google Scholar
  6. Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi. Rumor Spreading and Conductance. Journal of the ACM (JACM), 65(4):17, 2018. Google Scholar
  7. Sebastian Daum, Fabian Kuhn, and Yannic Maus. Rumor Spreading with Bounded In-Degree. In Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19-21, 2016, Revised Selected Papers, pages 323-339, 2016. URL: https://doi.org/10.1007/978-3-319-48314-6_21.
  8. Domingos Dellamonica, Yoshiharu Kohayakawa, Martin Marciniszyn, and Angelika Steger. On the Resilience of Long Cycles in Random Graphs. Electr. J. Comb., 15(1), 2008. URL: http://www.combinatorics.org/Volume_15/Abstracts/v15i1r32.html.
  9. Alan Demers, Dan Greene, Carl Houser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. ACM SIGOPS Operating Systems Review, 22(1):8-32, 1988. Google Scholar
  10. Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. Social networks spread rumors in sublogarithmic time. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 21-30. ACM, 2011. Google Scholar
  11. Benjamin Doerr and Anatolii Kostrygin. Randomized Rumor Spreading Revisited. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 138:1-138:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.138.
  12. Benjamin Doerr and Marvin Künnemann. Tight analysis of randomized rumor spreading in complete graphs. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, pages 82-91. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  13. Robert Elsässer and Thomas Sauerwald. On the runtime and robustness of randomized broadcasting. Theoretical Computer Science, 410(36):3414-3427, 2009. Google Scholar
  14. Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. Randomized broadcast in networks. Random Structures & Algorithms, 1(4):447-460, 1990. Google Scholar
  15. Nikolaos Fountoulakis, Anna Huber, and Konstantinos Panagiotou. Reliable broadcasting in random networks and the effect of density. In 2010 Proceedings IEEE INFOCOM, pages 1-9. IEEE, 2010. Google Scholar
  16. Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 560-573. Springer, 2010. Google Scholar
  17. 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, pages 1642-1660. SIAM, 2012. Google Scholar
  18. Tobias Friedrich, Thomas Sauerwald, and Alexandre Stauffer. Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. Algorithmica, 67(1):65-88, September 2013. URL: https://doi.org/10.1007/s00453-012-9710-y.
  19. Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10(1):57-77, 1985. Google Scholar
  20. George Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany, pages 57-68, 2011. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.57.
  21. George Giakkoupis. Tight Bounds for Rumor Spreading with Vertex Expansion. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 801-815, 2014. URL: https://doi.org/10.1137/1.9781611973402.59.
  22. Bernhard Haeupler. Simple, fast and deterministic gossip and rumor spreading. Journal of the ACM (JACM), 62(6):47, 2015. Google Scholar
  23. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  24. Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. Randomized Rumor Spreading. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 565-574, 2000. URL: https://doi.org/10.1109/SFCS.2000.892324.
  25. Konstantinos Panagiotou, Xavier Pérez-Giménez, Thomas Sauerwald, and He Sun. Randomized Rumour Spreading: The Effect of the Network Topology. Combinatorics, Probability & Computing, 24(2):457-479, 2015. URL: https://doi.org/10.1017/S0963548314000194.
  26. Konstantinos Panagiotou and Leo Speidel. Asynchronous rumor spreading on random graphs. Algorithmica, 78(3):968-989, 2017. Google Scholar
  27. Vojtěch Rödl and Mathias Schacht. Regularity lemmas for graphs. In Fete of combinatorics and computer science, pages 287-325. Springer, 2010. Google Scholar
  28. Benny Sudakov and Van H. Vu. Local resilience of graphs. Random Struct. Algorithms, 33(4):409-433, 2008. URL: https://doi.org/10.1002/rsa.20235.
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