Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting

In this paper, we provide a detailed comparison between a fully randomized protocol for rumour spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich and Sauerwald [Doerr, B., T. Friedrich and T. Sauerwald, Quasirandom broadcasting, In Proceedings of the 19th Annual ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 773–781, 2008]. In the former, initially there is one vertex which holds a piece of information and during each round every one of the informed vertices chooses one of its neighbours uniformly at random, independently of every other vertex, and informs it. In the quasirandom version of this method (see Doerr et al. [Doerr, B., T. Friedrich and T. Sauerwald, Quasirandom broadcasting, In Proceedings of the 19th Annual ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 773–781, 2008]) each vertex is equipped with a cyclic ordering of its neighbours. Once a vertex is informed, it chooses uniformly at random only the first neighbour it will inform and at each subsequent round it informs the successor in its cyclic ordering. The randomized protocol was analyzed by Frieze and Grimmett [Frieze, A.M., and G.R. Grimmett, The shortest-path problem for graphs with random arc-lengths, Discrete Appl. Math. 10 (1985), 57–77] and their analysis was refined by Pittel [Pittel, B., On spreading a rumor, SIAM J. Appl. Math. 47 (1987), 213–223], who gave a precise description of its evolution. In the present work, we present a precise analysis of the evolution of the quasirandom protocol on the complete graph with n vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if S ( n ) denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function ω ( n ) with probability 1 − o ( 1 ) we have log 2 n + ln n − 4 ln ln n ⩽ S ( n ) ⩽ log 2 n + ln n + ω ( n ) .