Strong Robustness of Randomized Rumor Spreading Protocols

Download Now Date Added: Mar 2010
Format: PDF

Randomized rumor spreading is a classical protocol to disseminate information across a network. At SODA 2008, a quasirandom version of this protocol was proposed and competitive bounds for its run-time were proven. This prompts the question: to what extent does the quasirandom protocol inherit the second principal advantage of randomized rumor spreading, namely robustness against transmission failures? In this paper, the authors present result precise up to (1 ? o (1) factors. They limit ourselves to the network in which every two vertices are connected by a direct link. Run-times accurate to their leading constants are unknown for all other non-trivial networks.