Quasirandom rumour spreading on the complete graph is as fast as randomized rumour spreading

Abstract. 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 (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 and independently and informs it. In the quasirandom version of this method (cf. Doerr et al. 2008) each vertex has a cyclic list of its neighbours. Once a vertex has been informed, it chooses uniformly at random only one neighbour. In the following round, it informs this neighbour and at each subsequent round it picks the next neighbour from its list and informs it. We give 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) log2 n + lnn − 4 ln lnn ≤ S(n) ≤ log2 n + lnn + ω(n), with probability 1 − o(1). 1