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: 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},