Pittel (1987) showed that for the fully randomized method on a complete graph the following holds: If S(n) denotes the number of rounds that are needed until all n vertices are informed, then for any slowly growing function h(n) one has
log_2 n + ln n - h(n) < S(n) < log_2 n + ln n + h(n)
with probability 1-o(1).
We showed that the quasirandom protocol evolves essentially in the same way as the randomized protocol. In particular, if Q(n) denotes the number of rounds that are needed until all n vertices of a complete graph are informed, for any slowly growing function h(n) one has
log_2 n + ln n - 4 ln ln n < Q(n) < log_2 n + ln n + h(n)
with probability 1-o(1).
This is joint work with Nikolaos Fountoulakis.