Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

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

Action:

login to update
Options:




Library Locked Library locked




Author, Editor(s)
Author(s):
Winzen, Caroladblp

BibTeX cite key*:

Winzen2013

Title

Title*:

Direction-Reversing Quasi-Random Rumor Spreading with Restarts

Journal

Journal Title*:

Information Processing Letters
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier
Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

113
Number:


Publishing Date:

2013

Pages*:

921-926
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

Doerr and Fouz [\emph{Asymptotically Optimal Randomized Rumor Spreading}, ICALP 2011] presented a new quasi-random PUSH algorithm for the rumor spreading problem on complete graphs.
Their protocol is the first randomized PUSH protocol with an asymptotically optimal running time.
This is achieved by equipping all nodes with the same lists, and by allowing them to do a random restart after encountering an already informed node.

Here in this work, we show that
the same running time can be achieved if every second random restart is replaced by a reversion of the direction in which the nodes follow their lists. Put differently, our \emph{direction-reversing quasi-random rumor spreading protocol with random restarts} achieves the same running time as the hybrid model by employing only (roughly) half the number of random choices.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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:

@ARTICLE{Winzen2013,
AUTHOR = {Winzen, Carola},
 TITLE = {Direction-Reversing Quasi-Random Rumor Spreading with Restarts},
 JOURNAL = {Information Processing Letters},
 PUBLISHER = {Elsevier},
 YEAR = {2013},
 VOLUME = {113},
 PAGES = {921--926},
}

Entry last modified by Carola Winzen, 02/17/2014
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
01/14/2014 03:58:25 PM
Revision
1.
0.


Editor
Carola Winzen
Carola Winzen


Edit Date
01/14/2014 09:43:01 PM
01/14/2014 03:58:25 PM