Direction-reversing quasi-random rumor spreading with restarts

• We study rumor spreading in complete graphs.
• We present a new algorithm with asymptotically optimal running time.
• It is a quasi-random algorithm with direction-reversion and random restarts.

Doerr and Fouz [Asymptotically optimal randomized rumor spreading, in: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011, pp. 502–513] presented a new quasi-random PUSH algorithm for the rumor spreading problem on complete graphs. Their protocol is the first randomized PUSH protocol with an asymptotically optimal running time. This is achieved by equipping all nodes with the same lists, and by allowing them to do a random restart after encountering an already informed node.Here in this work, we show that the same running time can be achieved if every second random restart is replaced by a reversion of the direction in which the nodes follow their lists. Put differently, our direction-reversing quasi-random rumor spreading protocol with random restarts achieves the same running time as the hybrid model by employing only (roughly) half the number of random choices.