The worst case behavior of randomized gossip protocols

DOI10.1016/J.TCS.2014.08.008zbMATH Open1303.68030OpenAlexW2037067117MaRDI QIDQ477180FDOQ477180

Authors: Hervé Baumann, Pierre Fraigniaud, Hovhannes A. Harutyunyan, Rémi de Joannis de Verclos 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.08.008

Recommendations

• The worst case behavior of randomized gossip
• Simple, fast and deterministic gossip and rumor spreading
• A time-randomness tradeoff for quasi-random rumour spreading
• Simple, fast and deterministic gossip and rumor spreading
• Quasirandom Rumor Spreading: An Experimental Analysis

zbMATH Keywords

broadcastrumor spreadinggossiprandom phone-call model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Network protocols (68M12)

Cites Work

• A survey of gossiping and broadcasting in communication networks
• The shortest-path problem for graphs with random arc-lengths
• Title not available (Why is that?)
• On Spreading a Rumor
• Methods and problems of communication in usual networks
• Title not available (Why is that?)
• On the runtime and robustness of randomized broadcasting
• An optimal greedy heuristic to color interval graphs
• Rumour spreading and graph conductance
• Rumor spreading on random regular graphs and expanders
• Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
• On randomized broadcasting in star graphs
• Almost tight bounds for rumour spreading with conductance
• Tight bounds for rumor spreading in graphs of a given conductance
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partial information spreading with application to distributed maximum coverage
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Mixing and Edge Expansion Properties in Randomized Broadcasting
• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem
• Broadcasting in random graphs
• Messy broadcasting - decentralized broadcast schemes with limited knowledge

Cited In (3)

• On linear-time data dissemination in dynamic rooted trees
• The worst case behavior of randomized gossip
• Stochastic and deterministic fault detection for randomized gossip algorithms

This page was built for publication: The worst case behavior of randomized gossip protocols

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