Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

Gossip vs. Markov Chains, and Randomness-efficient Rumor Spreading


Guo,  Zeyu
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Sun,  He
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Guo, Z., & Sun, H. (2015). Gossip vs. Markov Chains, and Randomness-efficient Rumor Spreading. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 411-430). Philadelphia, PA: SIAM. doi:10.1137/1.9781611973730.29.

Cite as:
We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network. We present the first protocol for any expander graph $G$ with $n$ nodes such that, the protocol informs every node in $O(\log n)$ rounds with high probability, and uses $\tilde{O}(\log n)$ random bits in total. The runtime of our protocol is tight, and the randomness requirement of $\tilde{O}(\log n)$ random bits almost matches the lower bound of $\Omega(\log n)$ random bits for dense graphs. We further show that, for many graph families, polylogarithmic number of random bits in total suffice to spread the rumor in $O(\mathrm{poly}\log n)$ rounds. These results together give us an almost complete understanding of the randomness requirement of this fundamental gossip process. Our analysis relies on unexpectedly tight connections among gossip processes, Markov chains, and branching programs. First, we establish a connection between rumor spreading processes and Markov chains, which is used to approximate the rumor spreading time by the mixing time of Markov chains. Second, we show a reduction from rumor spreading processes to branching programs, and this reduction provides a general framework to derandomize gossip processes. In addition to designing rumor spreading protocols, these novel techniques may have applications in studying parallel and multiple random walks, and randomness complexity of distributed algorithms.