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


Show entries of:

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

Action:

login to update

Options:









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
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)
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


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