MPI-INF D1 Publications: Unpublished/Draft

Unpublished, Draft, To Appear
@UnPublished
Unveröffentlicht, Entwurf

Show entries of:

this year (2021) | last year (2020) | two years ago (2019) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

Winzen, Carola

dblp

BibTeX citekey*:

Winzen2011b

Title, Booktitle

Title*:

Direction-Reversing Quasi-Random Rumor Spreading with Restarts

Vol, No, pp., Year

Month:	March	Year:	2011
Language:	English	Pages:	19

Abstract, Links, ©

Note:
LaTeX Abstract:	In a recent work, Doerr and Fouz [\emph{Asymptotically Optimal Randomized Rumor Spreading}, in ArXiv] present a new quasi-random PUSH algorithm for the rumor spreading problem (also known as gossip spreading or message propagation problem). Their \emph{hybrid protocol} outperforms all known PUSH protocols. In this work, we add to the hybrid protocol a direction-reversing element. We show that this \emph{direction-reversing quasi-random rumor spreading protocol with random restarts} yields a constant factor improvement over the hybrid model, if we allow the same dose of randomness. Put differently, our protocol achieves the same broadcasting time as the hybrid model by employing only (roughly) half the number of random choices.
Categories / Keywords:	Randomized Algorithms, Rumor Spreading, Broadcasting in Networks, Quasi-Randomness
HyperLinks / References / URLs:	http://arxiv.org/abs/1103.2429
Personal Comments:
File Upload:

Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	experts only
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@UNPUBLISHED{Winzen2011b,
AUTHOR = {Winzen, Carola},
TITLE = {Direction-Reversing Quasi-Random Rumor Spreading with Restarts},
YEAR = {2011},
PAGES = {19},
MONTH = {March},
}

Entry last modified by Thomas Sauerwald, 03/28/2011

Edit History (please click the blue arrow to see the details)

	Editor(s) Carola Winzen	Created 03/21/2011 01:26:43 PM
Revision 1. 0.	Editor Thomas Sauerwald Carola Winzen	Edit Date 03/28/2011 10:23:16 AM 03/21/2011 01:26:43 PM

Attachment Section