Rumor spreading and conductance

DOI10.1145/3173043MaRDI QIDQ4561504zbMATH OpenOpenAlexFDO

Authors Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, Alessandro Panconesi

Publication date 6 December 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01942162/file/jacm2018RSconductance.pdf

zbMATH Keywords

distributed algorithmsgossip algorithmsgraph conductancegraph sparsificationrandomized algorithmsrandomized broadcast

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Almost tight bounds for rumour spreading with conductance
• Rumour spreading and graph conductance
• Tight bounds for rumor spreading in graphs of a given conductance
• On the Push\&Pull protocol for rumour spreading (extended abstract)
• On the Push&Pull Protocol for Rumor Spreading

Cited in

(14)

• How to discreetly spread a rumor in a crowd
• Asymptotics for pull on the complete graph
• Rumor spreading with no dependence on conductance
• Tight bounds for rumor spreading in graphs of a given conductance
• Robustness of randomized rumour spreading
• The String of Diamonds Is Tight for Rumor Spreading
• scientific article; zbMATH DE number 7525473 (Why is no real title available?)
• Partial information spreading with application to distributed maximum coverage
• Brief announcement: Gossiping with latencies
• Rumour spreading and graph conductance
• How does rumor spreading affect people inside and outside an institution
• Spread of information and diseases via random walks in sparse graphs
• Early adapting to trends: self-stabilizing information spread using passive communication
• Rumors with changing credibility

This page was built for publication: Rumor spreading and conductance

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