{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T11:52:35Z","timestamp":1759665155090},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work we consider three well-studied broadcast protocols: <jats:italic>push<\/jats:italic>, <jats:italic>pull<\/jats:italic> and <jats:italic>push&amp;pull<\/jats:italic>. 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.<\/jats:p><jats:p>We explore in particular the following notion of <jats:italic>local resilience<\/jats:italic>: 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, <jats:italic>pull<\/jats:italic> is robust with respect to all parameters that we consider. On the other hand, <jats:italic>push<\/jats:italic> may slow down significantly, even if the adversary may modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, <jats:italic>push&amp;pull<\/jats:italic> is robust when no message transmission failures are considered, otherwise it may be slowed down.<\/jats:p><jats:p>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\u00e9di\u2019s Regularity Lemma.<\/jats:p>","DOI":"10.1017\/s0963548320000310","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T07:30:07Z","timestamp":1597217407000},"page":"37-78","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Robustness of randomized rumour spreading"],"prefix":"10.1017","volume":"30","author":[{"given":"Rami","family":"Daknama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Reisser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"S0963548320000310_ref2","unstructured":"[2] 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\u201326:9. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S0963548320000310_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"S0963548320000310_ref3","first-page":"208","author":"Boucheron","year":"2004"},{"key":"S0963548320000310_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/43921.43922"},{"key":"S0963548320000310_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000194"},{"key":"S0963548320000310_ref10","doi-asserted-by":"crossref","unstructured":"[10] 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 \u201911), pp. 21\u201330. ACM.","DOI":"10.1145\/1993636.1993640"},{"key":"S0963548320000310_ref16","first-page":"560","author":"Fountoulakis","year":"2010"},{"key":"S0963548320000310_ref30","first-page":"287","author":"R\u00f6dl","year":"2010"},{"key":"S0963548320000310_ref7","doi-asserted-by":"crossref","unstructured":"[7] 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\u2013339.","DOI":"10.1007\/978-3-319-48314-6_21"},{"key":"S0963548320000310_ref5","doi-asserted-by":"crossref","unstructured":"[5] 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 \u201912), pp. 961\u2013970. ACM.","DOI":"10.1145\/2213977.2214064"},{"key":"S0963548320000310_ref6","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3173043","article-title":"Rumor spreading and conductance","volume":"65","author":"Chierichetti","year":"2018","journal-title":"J. Assoc. Comput. Mach."},{"key":"S0963548320000310_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892324"},{"key":"S0963548320000310_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0188-x"},{"key":"S0963548320000310_ref19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","article-title":"The shortest-path problem for graphs with random arc-lengths","volume":"10","author":"Frieze","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"S0963548320000310_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.12.009"},{"key":"S0963548320000310_ref23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/2767126","article-title":"Simple, fast and deterministic gossip and rumor spreading","volume":"62","author":"Haeupler","year":"2015","journal-title":"J. Assoc. Comput. Mach."},{"key":"S0963548320000310_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.130"},{"key":"S0963548320000310_ref14","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1002\/rsa.3240010406","article-title":"Randomized broadcast in networks","volume":"1","author":"Feige","year":"1990","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000310_ref8","doi-asserted-by":"publisher","DOI":"10.37236\/756"},{"key":"S0963548320000310_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9710-y"},{"key":"S0963548320000310_ref24","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-53-02004-3"},{"key":"S0963548320000310_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.017"},{"key":"S0963548320000310_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.59"},{"key":"S0963548320000310_ref32","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1007\/BF02230720","article-title":"Unzerlegbare, nicht negative Matrizen","volume":"52","author":"Wielandt","year":"1950","journal-title":"Math. Z."},{"key":"S0963548320000310_ref12","doi-asserted-by":"crossref","unstructured":"[12] Doerr, B. and K\u00fcnnemann, 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\u201391. SIAM.","DOI":"10.1137\/1.9781611973204.8"},{"key":"S0963548320000310_ref1","doi-asserted-by":"crossref","unstructured":"[1] Acan, H. , Collevecchio, A. , Mehrabian, A. and Wormald, N. (2017) On the push&pull protocol for rumour spreading. In Extended Abstracts Summer 2015 ( D\u00edaz, J. et al., eds), pp. 3\u201310. Springer.","DOI":"10.1007\/978-3-319-51753-7_1"},{"key":"S0963548320000310_ref4","doi-asserted-by":"crossref","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","article-title":"Randomized gossip algorithms","volume":"52","author":"Boyd","year":"2006","journal-title":"IEEE\/ACM Trans. Inform. Theory"},{"key":"S0963548320000310_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"},{"key":"S0963548320000310_ref20","unstructured":"[20] 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\u201368. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"key":"S0963548320000310_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"S0963548320000310_ref11","unstructured":"[11] Doerr, B. and Kostrygin, A. (2017) Randomized rumor spreading revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 138:1\u2013138:14."},{"key":"S0963548320000310_ref25","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander graphs and their applications","volume":"43","author":"Hoory","year":"2006","journal-title":"Bull. Amer. Math. Soc."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:52:09Z","timestamp":1611229929000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000310\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000310"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000310","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"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.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}