On Quasirandom Rumor Spreading

Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald proposed a quasirandom analogue of the randomized rumor spreading model. Here, each vertex has a cyclic permutation of its neighbors. When first passing the rumor, it chooses a neighbor uniformly at random. All subsequent gossipping is done to the successors of this vertex in the cyclic permutation. For complete graphs, hypercubes and a broader range of random graphs it was then shown that, independent of the choice of the cyclic permutations, this protocol also needs $O(\log n)$ rounds only to inform all other nodes. We show that for complete graphs we do not even lose a constant factor, that is, independent of the cyclic permutations, the protocol informs all nodes in $(1 + o(1)) (\log_2(n) + \ln(n))$ rounds.

Joint work with Benjamin Doerr.