hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Probability, math.PR
Abstract:
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.
