Randomized rumor spreading

By Richard M. Karp, C. Schindelhauer, Scott Shenker, Berthold Vöcking. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

800 citations recorded by the source corpus.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/bad78a526180dd4e2a4cd6485e5dd5cb010b12f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Gossip-based computation of aggregate information (2003, background): “consider tradeoffs between the number of rounds of gossip and the number of message duplicates that are sent [20].”
Maximizing throughput in wireless networks via gossiping (2006, background): “for more information on gossip algorithms see [4, 15] and references therein.”
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, positive): “Termination without using global coordination is a problem in its own right that has been extensively studied (see for instance [3]).”
All You Need is DAG (2021, background): “There are also efficient gossip protocols [9, 10, 25, 27] that provide reliable broadcast whp at a sub-quadratic communication cost in the number of processes, and asynchronous verifiable information dispersal protocols [15, 35] that use erasure codes to efficiently batch the broadcast values.”
Randomized gossip algorithms (2006, background): “For an extensive body of related work, see [11], [16], [17], [20], [23], [25], [26], [29], [34], [42], [44], [46].”
Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection (2020, neutral): “Therefore, we generate it following the new assumption of the second eigenvalue similar to [29], [30], [32] but different from that in [26].”
Mobeyes: smart mobs for urban monitoring with a vehicular sensor network (2006, background): “Opportunistic data dissemination1 exploits node mobility to broadcast the epidemic, or data, to a complete well defined population in sparse ad hoc networks [13], [30].”
Spatial gossip and resource location protocols (2001, background): “A well-known result states that with high probability, all nodes will receive a copy of a given message m within O (log N ) steps of its initial appearance [7, 10, 14].”
Algebraic gossip: a network coding approach to optimal multiple rumor mongering (2006, methodology): “This work was supported by AFOSR PY-1362, NSF under Grants CCR-0093349 and CCR0325496, DARPA under Contract N00014-05-1-0197, and ARO S0176938.”
Gossip Algorithms for Distributed Signal Processing (2010, background): “ssues related to their use for in-network processing in wireless sensor networks. Gossip algorithms have been widely studied in the computer science community for information dissemination and search [14]–[16]. More recently, they have been developed and studied for information processing in sensor ”
Hyperledger fabric: a distributed operating system for permissioned blockchains (2018, methodology): “It has been shown [15, 22] that using both methods in tandem is crucial to optimally utilize the available bandwidth and to ensure that all peers receive all messages with high probability.”
Converging Quickly to Independent Uniform Random Topologies (2011, background): “Therefore, ideally, any node exchanges information with peers that are selected following a uniform random sample of all nodes in the system [1], [5], [6], [7].”
Toward a theory of in-network computation in wireless sensor networks (2006, background): “This is order optimal, since it can be shown [15] that any gossip algorithm in any n node graph requires Ω(n) rounds to compute the average with probability of error less than ε, where 0 < ε < 0.”
SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies (2015, background): “Overall, the effect of this mechanism is to establish a well-connected random network, with low degree yet low diameter, suitable for rapid broadcast of information through diffusion [35], [56].”
RapidChain: Scaling Blockchain via Full Sharding (2018, background): “While the large overhead of such a broadcast for every participant is usually reduced from a linear number of messages (with respect to the number of participants) to nearly a constant using a peer-to-peer gossiping protocol [36], the relatively high latency of such a “gossip-to-all” invocation (e.”
Distributed computation in dynamic networks (2010, methodology): “Various information dissemination problems for the gossiping model have been considered [21, 23, 25]; gossiping aggregation protocols that can be used to approximate the size of the system are described in [24, 36].”
On Scaling Decentralized Blockchains - (A Position Paper) (2016, background): “Such overlay topologies are usually expander graphs, which have known low-latency broadcast protocols [28,32].”
Synopsis diffusion for robust aggregation in sensor networks (2004, background): “Note that there are many extremely robust gossip-based protocols [Jenkins et al. 2001; Karp et al. 2000; Vogels et al. 2003] that do not require reliable communication, but they are designed primarily for information dissemination and can not”