Rumor spreading with no dependence on conductance

DOI10.1137/14099992XzbMATH Open1359.68024OpenAlexW2583780251MaRDI QIDQ2963582FDOQ2963582

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

Publication date 15 February 2017

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/14099992x

zbMATH Keywords

local modelinformation spreadingsparse spannersgossip modelconductance decomposition

Mathematics Subject Classification ID

Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Recommendations

• Global computation in a poorly connected world
• Simple, fast and deterministic gossip and rumor spreading
• Simple, fast and deterministic gossip and rumor spreading
• Almost tight bounds for rumour spreading with conductance
• Rumor spreading and conductance

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 5764860 (Why is no real title available?)
• scientific article; zbMATH DE number 6783407 (Why is no real title available?)
• scientific article; zbMATH DE number 6783408 (Why is no real title available?)
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Almost tight bounds for rumour spreading with conductance
• An Optimal Synchronizer for the Hypercube
• Asymptotically optimal randomized rumor spreading
• Asynchronous Rumor Spreading in Preferential Attachment Graphs
• Asynchronous gossip
• Computing separable functions via gossip
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Fast information spreading in graphs with large weak conductance
• Forests, frames, and games: Algorithms for matroid sums and applications
• Fully dynamic randomized algorithms for graph spanners
• Global computation in a poorly connected world
• Graph spanners
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Low distortion spanners
• Low randomness rumor spreading via hashing
• Lower bound of the Hadwiger number of graphs by their average degree
• On the locality of distributed sparse spanner construction
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading
• Randomized broadcast in networks
• Rumor spreading and vertex expansion
• Simple, fast and deterministic gossip and rumor spreading
• Social networks spread rumors in sublogarithmic time
• Spatial gossip and resource location protocols
• Spectral sparsification of graphs
• Sublinear fully distributed partition with applications
• Tight bounds for rumor spreading in graphs of a given conductance
• Tight bounds for rumor spreading with vertex expansion
• Ultra-fast rumor spreading in social networks

Cited in

(4)

• Simple, fast and deterministic gossip and rumor spreading
• Global computation in a poorly connected world
• Simple, fast and deterministic gossip and rumor spreading
• Brief announcement: Gossiping with latencies

This page was built for publication: Rumor spreading with no dependence on conductance

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