MPI-INF Logo
Campus Event Calendar

Event Entry

New for: D3

What and Who

Robustness of Randomized Rumor Spreading Protocols

Anna Huber
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 10 November 2009
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

Randomized rumor spreading is a classical protocol to disseminate information in 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?


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.

Contact

Anna Huber
--email hidden
passcode not visible
logged in users only

Anna Huber, 11/05/2009 13:21 -- Created document.