Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Doerr, Benjamin
Huber, Anna
Levavi, Ariel

dblp
dblp
dblp



Editor(s):

Dong, Yingfei
Du, Ding-Zhu
Ibarra, Oscar

dblp
dblp
dblp

Not MPII Editor(s):

Dong, Yingfei
Du, Ding-Zhu
Ibarra, Oscar

BibTeX cite key*:

DHL2009

Title, Booktitle

Title*:

Strong robustness of randomized rumor spreading protocols

Booktitle*:

Algorithms and Computation : 20th International Symposium, ISAAC 2009

Event, URLs

URL of the conference:

http://theory.utdallas.edu/ISAAC2009/index.html

URL for downloading the paper:

http://www.springerlink.com/content/x5172v3361nk2l58/fulltext.pdf

Event Address*:

Hawaii, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

16 December 2009

Event End Date:

18 December 2009

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

5878

Number:


Month:


Pages:

812-821

Year*:

2009

VG Wort Pages:

20

ISBN/ISSN:

978-3-642-10630-9

Sequence Number:


DOI:

10.1007/978-3-642-10631-6_82



Note, Abstract, ©

Note:

Full version available from arXiv:1001.3056

(LaTeX) Abstract:

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, we present a result precise up to $(1 \pm o(1))$ factors. We 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.

We show that if each transmission reaches its destination with a probability of $p \in (0,1]$, after $(1+\e)\left(\frac{1}{\log_2(1+p)}\log_2n+\frac{1}{p}\ln n\right)$ rounds the quasirandom protocol has informed all $n$ nodes in the network with probability at least $1-n^{-p\e/40}$. Note that this is faster than the intuitively natural $1/p$ factor increase over the run-time of approximately $\log_2 n + \ln n $ for the non-corrupted case.

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.

HyperLinks / References / URLs:

http://arxiv.org/pdf/1001.3056v1



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DHL2009,
AUTHOR = {Doerr, Benjamin and Huber, Anna and Levavi, Ariel},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
TITLE = {Strong robustness of randomized rumor spreading protocols},
BOOKTITLE = {Algorithms and Computation : 20th International Symposium, ISAAC 2009},
PUBLISHER = {Springer},
YEAR = {2009},
VOLUME = {5878},
PAGES = {812--821},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Hawaii, USA},
ISBN = {978-3-642-10630-9},
DOI = {10.1007/978-3-642-10631-6_82},
NOTE = {Full version available from arXiv:1001.3056},
}


Entry last modified by Benjamin Doerr, 01/20/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/14/2010 05:36:34 PM
Revisions
2.
1.
0.

Editor(s)
Benjamin Doerr
Anja Becker
Anna Huber

Edit Dates
20.01.2011 15:34:48
04.03.2010 15:10:08
02/14/2010 05:36:34 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section