On the Randomness Requirements of Rumor Spreading

22nd Annual ACM-SIAM Symposium on Discrete Algorithms

数学;计算机科学

George Giakkoupis ; Philipp Woelfely

Others  :  http://www.siam.org/proceedings/soda/2011/SODA11_036_giakkoupisg.pdf
PID  :  32521

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We investigate the randomness requirements of the clas- sical rumor spreading problem on fully connected graphs with n vertices. In the standard random protocol, where each node that knows the rumor sends it to a ran- domly chosen neighbor in every round, each node needs O((log n)2) random bits in order to spread the rumor in O(log n) rounds with high probability (w.h.p.). For the simple quasirandom rumor spreading protocol proposed by Doerr, Friedrich, and Sauerwald (2008), dlog ne ran- dom bits per node are sucient. A lower bound by Do- err and Fouz (2009) shows that this is asymptotically tight for a slightly more general class of protocols, the so-called gate-model. In this paper, we consider general rumor spreading protocols. We provide a simple push-protocol that requires only a total of O(n log log n) random bits (i.e., on average O(log logn) bits per node) in order to spread the rumor in O(log n) rounds w.h.p. We also investigate the theoretical minimal randomness requirements of ecient rumor spreading. We prove the existence of a (non-uniform) push-protocol for which a total of 2 log n + log log n + o(log log n) random bits suce to spread the rumor in logn + lnn + O(1) rounds with probability 1o(1). This is contrasted by a simple time- randomness tradeo for the class of all rumor spreading protocols, according to which any protocol that uses log nlog logn!(1) random bits requires !(log n)