Robustness of randomized rumour spreading
From MaRDI portal
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 has to be allowed to 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. It turns out that 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`edi's Regularity Lemma.
Recommendations
Cites work
- Advanced Lectures on Machine Learning
- Diameter and broadcast time of random geometric graphs in arbitrary dimensions
- Expander graphs and their applications
- Global computation in a poorly connected world
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- Local resilience of graphs
- On the Push\&Pull protocol for rumour spreading (extended abstract)
- On the resilience of long cycles in random graphs
- On the runtime and robustness of randomized broadcasting
- Randomized broadcast in networks
- Randomized rumor spreading revisited
- Randomized rumour spreading: the effect of the network topology
- Regularity lemmas for graphs
- Rumor spreading and conductance
- Rumor spreading on random regular graphs and expanders
- Simple, fast and deterministic gossip and rumor spreading
- Social networks spread rumors in sublogarithmic time
- The shortest-path problem for graphs with random arc-lengths
- The String of Diamonds Is Tight for Rumor Spreading
- Tight analysis of randomized rumor spreading in complete graphs
- Tight bounds for rumor spreading in graphs of a given conductance
- Tight bounds for rumor spreading with vertex expansion
- Tight lower bound on the probability of a binomial exceeding its expectation
- Ultra-fast rumor spreading in social networks
- Unzerlegbare, nicht negative Matrizen
Cited in
(8)- Rumor spreading models with random denials
- Bounds on expected propagation time of probabilistic zero forcing
- Asymptotics for pull on the complete graph
- Asymptotically optimal randomized rumor spreading
- scientific article; zbMATH DE number 7525473 (Why is no real title available?)
- Quasirandom Rumor Spreading: An Experimental Analysis
- scientific article; zbMATH DE number 6783407 (Why is no real title available?)
- Rumors with changing credibility
This page was built for publication: Robustness of randomized rumour spreading
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993120)
