The worst case behavior of randomized gossip protocols

DOI10.1016/J.TCS.2014.08.008MaRDI QIDQ477180zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(3)

• The worst case behavior of randomized gossip
• On linear-time data dissemination in dynamic rooted trees
• 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)