Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Angelopoulos, Spyros
Doerr, Benjamin
Huber, Anna
Panagiotou, Konstantinos

dblp
dblp
dblp
dblp



BibTeX cite key*:

ADHP2009

Title

Title*:

Tight bounds for quasirandom rumor spreading

Journal

Journal Title*:

The Electronic Journal of Combinatorics

Journal's URL:

http://www.combinatorics.org/

Download URL
for the article:

http://www.combinatorics.org/Volume_16/PDF/v16i1r102.pdf

Language:

English

Publisher

Publisher's
Name:

Department of Mathematics of the University of Pennsylvania

Publisher's URL:


Publisher's
Address:

Philadelphia, PA

ISSN:

1077-8926

Vol, No, Year, pp.

Volume:

16

Number:

1

Month:


Year*:

2009

Pages:

R102,1-R102,19

Number of VG Pages:

33

Sequence Number:

R102

DOI:


Abstract, Links, (C)

Note:


(LaTeX) Abstract:

This paper addresses the following fundamental problem: Suppose that in a group of $n$ people,
where each person knows all other group members, a single person holds a piece
of information that must be disseminated to everybody within the group.
How should the people propagate the information so that after short time everyone is informed?

The classical approach, known as the {\em push model}, requires that in each round,
every informed person selects some other person in the group at random, whom it then informs.
In a different model, known as the \emph{quasirandom push model}, each person maintains a cyclic list, i.e., permutation,
of all members in the group (for instance, a contact list of persons).
Once a person is informed, it chooses a random member in its own list,
and from that point onwards, it informs a new person per round, in the order dictated by the list.

In this paper we show that with probability $1-o(1)$ the quasirandom protocol informs everybody in
$(1 \pm o(1))\log_2 n+\ln n$ rounds; furthermore we also show that this bound is tight. This result, together with previous work on the randomized push model, demonstrates that irrespectively of the choice of lists, quasirandom broadcasting is as fast as broadcasting in the randomized push model, up to lower order terms. At the same
time it reduces the number of random bits from $O(\log^2 n)$ to only $\lceil\log_2 n\rceil$ per person.

URL for the Abstract:


Categories / Keywords:


HyperLinks / References / URLs:


Copyright Message:

http://www.combinatorics.org/index.html
Full-text access to all papers is available for free. No registration or subscription is required, though we offer a free email notification service

Personal Comments:


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:

@MISC{ADHP2009,
AUTHOR = {Angelopoulos, Spyros and Doerr, Benjamin and Huber, Anna and Panagiotou, Konstantinos},
TITLE = {Tight bounds for quasirandom rumor spreading},
JOURNAL = {The Electronic Journal of Combinatorics},
PUBLISHER = {Department of Mathematics of the University of Pennsylvania},
YEAR = {2009},
NUMBER = {1},
VOLUME = {16},
PAGES = {R102,1--R102,19},
ADDRESS = {Philadelphia, PA},
ISBN = {1077-8926},
}


Entry last modified by Benjamin Doerr, 01/20/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)
[Library]
Created
02/14/2010 04:52:47 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Benjamin Doerr
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
20.01.2011 15:43:27
26.02.2010 15:39:47
26.02.2010 15:32:23
26.02.2010 15:25:07
02/14/2010 05:04:39 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section