A Time-Randomness Tradeoff for Quasi-Random Rumour Spreading

We give a time-randomness tradeoff for the quasi-random rumour spreading protocol proposed by Doerr et al [Doerr, B., T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proc. of the 19th Annual ACM-SIAM Symp. on Disc. Alg., pages 773–781, 2008] on complete graphs. In this protocol, the goal is to spread a piece of information originating from one vertex throughout the network. Each vertex is assumed to have a (cyclic) list of its neighbors. Once a vertex is informed by one of its neighbors, it chooses a position in its list uniformly at random and goes on to inform its neighbors starting from that position and proceeding in order of the list. Doerr et al [Doerr, B., T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proc. of the 19th Annual ACM-SIAM Symp. on Disc. Alg., pages 773–781, 2008.] showed that after O(log n) rounds, the rumour will have been broadcasted to all nodes with probability 1−o(1).We study the broadcast time when the amount of randomness available at each node is reduced. For randomness parameter ℓ, we show that there exists lists such that (1−ε)(log2n+lnn−log2ℓ−lnℓ)+ℓ steps are needed to inform every vertex with probability at least .