Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-17T00:18:30.184Z Has data issue: false hasContentIssue false
  • English
  • Français

Robustness of randomized rumour spreading

Part of: Graph theory Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  12 August 2020

Rami Daknama ,
Konstantinos Panagiotou  and
Simon Reisser
Rami Daknama
Affiliation:
Institute for Mathematics, Ludwig-Maximilians-Universität München, 80333Munich, Germany
Konstantinos Panagiotou*
Affiliation:
Institute for Mathematics, Ludwig-Maximilians-Universität München, 80333Munich, Germany
Simon Reisser
Affiliation:
Institute for Mathematics, Ludwig-Maximilians-Universität München, 80333Munich, Germany
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 may 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.

MSC classification

Primary: 05C85: Graph algorithms
Secondary: 68R10: Graph theory (including graph drawing)
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 1 , January 2021 , pp. 37 - 78
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

1

An extended abstract of this paper was published in the Proceedings of the European Symposium on Algorithms 2019 (ESA ’19).

References

Acan, H., Collevecchio, A., Mehrabian, A. and Wormald, N. (2017) On the push&pull protocol for rumour spreading. In Extended Abstracts Summer 2015 (Díaz, J. et al., eds), pp. 3–10. Springer.Google Scholar
Angel, O., Mehrabian, A. and Peres, Y. (2017) The string of diamonds is tight for rumor spreading. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2017), pp. 26:1–26:9. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.Google Scholar
Boucheron, S., Lugosi, G. and Bousquet, O. (2004) Concentration inequalities. In Advanced Lectures on Machine Learning, Vol. 3176 of Lecture Notes in Computer Science, pp. 208–240. Springer.Google Scholar
Boyd, S., Ghosh, A., Prabhakar, B. and Shah, D. (2006) Randomized gossip algorithms. IEEE/ACM Trans. Inform. Theory 52 2508–2530.Google Scholar
Censor-Hillel, K., Haeupler, B., Kelner, J. and Maymounkov, P. (2012) 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 (STOC ’12), pp. 961–970. ACM.Google Scholar
Chierichetti, F., Giakkoupis, G., Lattanzi, S. and Panconesi, A. (2018) Rumor spreading and conductance. J. Assoc. Comput. Mach. 65 17.Google Scholar
Daum, S., Kuhn, F. and Maus, Y. (2016) Rumor spreading with bounded in-degree. In Structural Information and Communication Complexity: 23rd International Colloquium (SIROCCO 2016), pp. 323–339.Google Scholar
Dellamonica, D., Kohayakawa, Y., Marciniszyn, M. and Steger, A. (2008) On the resilience of long cycles in random graphs. Electron. J. Combin. 15 #R321.CrossRefGoogle Scholar
Demers, A., Greene, D., Houser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D. and Terry, D. (1988) Epidemic algorithms for replicated database maintenance. ACM SIGOPS Operating Systems Review 22 8–32.CrossRefGoogle Scholar
Doerr, B., Fouz, M. and Friedrich, T. (2011) Social networks spread rumors in sublogarithmic time. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC ’11), pp. 21–30. ACM.Google Scholar
Doerr, B. and Kostrygin, A. (2017) Randomized rumor spreading revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 138:1–138:14.Google Scholar
Doerr, B. and Künnemann, M. (2014) Tight analysis of randomized rumor spreading in complete graphs. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2014), pp. 82–91. SIAM.Google Scholar
Elsässer, R. and Sauerwald, T. (2009) On the runtime and robustness of randomized broadcasting. Theoret. Comput. Sci. 410 3414–3427.CrossRefGoogle Scholar
Feige, U., Peleg, D., Raghavan, P. and Upfal, E. (1990) Randomized broadcast in networks. Random Struct. Algorithms 1 447–460.Google Scholar
Fountoulakis, N., Huber, A. and Panagiotou, K. (2010) Reliable broadcasting in random networks and the effect of density. In 2010 Proceedings IEEE INFOCOM, pp. 1–9. IEEE.CrossRefGoogle Scholar
Fountoulakis, N. and Panagiotou, K. (2010) Rumor spreading on random regular graphs and expanders. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (RANDOM 2010), Vol. 6302 of Lecture Notes in Computer Science, pp. 560–573. Springer.Google Scholar
Fountoulakis, N., Panagiotou, K. and Sauerwald, T. (2012) Ultra-fast rumor spreading in social networks. In Proceedings of the Twenty-Third Annual ACM–SIAM Symposium on Discrete Algorithms (SODA ’12), pp. 1642–1660. SIAM.CrossRefGoogle Scholar
Friedrich, T., Sauerwald, T. and Stauffer, A. (2013) Diameter and broadcast time of random geometric graphs in arbitrary dimensions. Algorithmica 67 65–88.CrossRefGoogle Scholar
Frieze, A. M. and Grimmett, G. R. (1985) The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10 57–77.Google Scholar
Giakkoupis, G. (2011) Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pp. 57–68. Schloss Dagstuhl–Leibniz-Zentrum für InformatikGoogle Scholar
Giakkoupis, G. (2014) Tight bounds for rumor spreading with vertex expansion. In Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithm (SODA 2014), pp. 801–815.CrossRefGoogle Scholar
Greenberg, S. and Mohri, M. (2014) Tight lower bound on the probability of a binomial exceeding its expectation. Statist. Probab. Lett. 86 91–98.CrossRefGoogle Scholar
Haeupler, B. (2015) Simple, fast and deterministic gossip and rumor spreading. J. Assoc. Comput. Mach. 62 47.Google Scholar
Hoffman, A. J. and Wielandt, H. W. (1953) The variation of the spectrum of a normal matrix. Duke Math. J. 20 37–39.CrossRefGoogle Scholar
Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. 43 439–561.Google Scholar
Janson, S. (2018) Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135 1–6.CrossRefGoogle Scholar
Karp, R. M., Schindelhauer, C., Shenker, S. and Vöcking, B. (2000) Randomized rumor spreading. In 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 565–574.CrossRefGoogle Scholar
Panagiotou, K., Pérez-Giménez, X., Sauerwald, T. and Sun, H. (2015) Randomized rumour spreading: the effect of the network topology. Combin. Probab. Comput. 24 457–479.CrossRefGoogle Scholar
Panagiotou, K. and Speidel, L. (2017) Asynchronous rumor spreading on random graphs. Algorithmica 78 968–989.CrossRefGoogle Scholar
Rödl, V. and Schacht, M. (2010) Regularity lemmas for graphs. In Fete of Combinatorics and Computer Science, Vol. 20 of Bolyai Society Mathematical Studies, pp. 287–325. Springer.Google Scholar
Sudakov, B. and Vu, V. H. (2008) Local resilience of graphs. Random Struct. Algorithms 33 409–433.CrossRefGoogle Scholar
Wielandt, H. (1950) Unzerlegbare, nicht negative Matrizen. Math. Z. 52 642–648.Google Scholar