Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D3
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Robustness of Randomized Rumor Spreading Protocols
Speaker:Anna Huber
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D4, RG1, MMCI, D3, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 10 November 2009
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Anna Huber
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Anna Huber, 11/05/2009 01:21 PM -- Created document.