Breaking the log n barrier on rumor spreading

Chen Avin, Robert Elsässer

$O(\log n)$ rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching low…