Rumor Spreading with No Dependence on Conductance

DOI10.1137/14099992XzbMath1359.68024MaRDI QIDQ2963582

Jonathan A. Kelner, Petar Maymounkov, Keren Censor-Hillel, Bernhard Haeupler

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 model; information spreading; sparse spanners; gossip model; conductance decomposition

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68M14: Distributed systems

68W15: Distributed algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• Forests, frames, and games: Algorithms for matroid sums and applications
• Sublinear fully distributed partition with applications
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Almost tight bounds for rumour spreading with conductance
• Asynchronous Rumor Spreading in Preferential Attachment Graphs
• Low distortion spanners
• On the locality of distributed sparse spanner construction
• Asymptotically Optimal Randomized Rumor Spreading
• Quasirandom Rumor Spreading on the Complete Graph Is as Fast as Randomized Rumor Spreading
• Spectral Sparsification of Graphs
• Additive spanners and (α, β)-spanners
• Fully dynamic randomized algorithms for graph spanners
• Randomized broadcast in networks
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Graph spanners
• Distributed Computing: A Locality-Sensitive Approach
• An Optimal Synchronizer for the Hypercube
• Spatial gossip and resource location protocols
• Computing separable functions via gossip
• Tight Bounds for Rumor Spreading with Vertex Expansion
• Asynchronous gossip
• Global computation in a poorly connected world
• Social networks spread rumors in sublogarithmic time
• Simple, Fast and Deterministic Gossip and Rumor Spreading
• Distributed algorithms for ultrasparse spanners and linear size skeletons