Global computation in a poorly connected world

DOI10.1145/2213977.2214064MaRDI QIDQ5415528zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, Petar Maymounkov

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2213977.2214064

zbMATH Keywords

broadcastexpander decompositiongossipinformation spreadingsparse spanners

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Almost tight bounds for rumour spreading with conductance
• Fast information spreading in graphs with large weak conductance
• Fast information spreading in graphs with large weak conductance
• Randomized rumor spreading in poorly connected small-world networks
• Tight bounds for rumor spreading in graphs of a given conductance
• Rumour spreading and graph conductance
• Rumor spreading with no dependence on conductance
• Breaking the \(\log n\) barrier on rumor spreading

Cited in

(19)

• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Breaking the \(\log n\) barrier on rumor spreading
• The sparsest additive spanner via multiple weighted BFS trees
• Simple and optimal randomized fault-tolerant rumor spreading
• Rumor spreading with no dependence on conductance
• Simple, fast and deterministic gossip and rumor spreading
• Robustness of randomized rumour spreading
• Limits for rumor spreading in stochastic populations
• A tight analysis of the parallel undecided-state dynamics with two colors
• scientific article; zbMATH DE number 7525473 (Why is no real title available?)
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Probabilistic Analysis of Rumor-Spreading Time
• Fast information spreading in graphs with large weak conductance
• Brief announcement: Gossiping with latencies
• Simple, fast and deterministic gossip and rumor spreading
• Order optimal information spreading using algebraic gossip
• Early adapting to trends: self-stabilizing information spread using passive communication
• Time- and communication-efficient overlay network construction via gossip

This page was built for publication: Global computation in a poorly connected world

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415528)