New for: D3
For the complete graph on $n$ nodes, we show that after $(1+\epsilon)(\log_{1+p}n+\frac{1}{p}\ln n)$ rounds, the quasirandom protocol with transmission success probability $p$ has informed all vertices with probability $1-n^{-\frac{p\epsilon}{40}}$.
We also provide a corresponding lower bound for the classical model. This demonstrates that the quasirandom model is at least as robust as the fully random model despite the greatly reduced degree of independent randomness.
This is joint work with Benjamin Doerr and Ariel Levavi.