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
Goto entry point
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
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
Attachment Section
Attachment Section