Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 518251.0, MPI für Informatik / Algorithms and Complexity Group
Tight bounds for quasirandom rumor spreading
Authors:Angelopoulos, Spyros; Doerr, Benjamin; Huber, Anna; Panagiotou, Konstantinos
Date of Publication (YYYY-MM-DD):2009
Title of Journal:The Electronic Journal of Combinatorics
Issue / Number:1
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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
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.
Last Change of the Resource (YYYY-MM-DD):2010-02-14
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.