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 ) . dy 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 − ε ) ( log 2 n + ln n − log 2 ℓ − ln ℓ ) + ℓ steps are needed to inform every vertex with probability at least 1 − O ( e − n ε 2 ln n ) .