English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Tight Bounds for Quasirandom Rumor Spreading

MPS-Authors
/persons/resource/persons44020

Angelopoulos,  Spyros
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44649

Huber,  Anna
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45156

Panagiotou,  Konstantinos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Angelopoulos, S., Doerr, B., Huber, A., & Panagiotou, K. (2009). Tight Bounds for Quasirandom Rumor Spreading. The Electronic Journal of Combinatorics, 16(1). Retrieved from http://www.combinatorics.org/Volume_16/PDF/v16i1r102.pdf.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18E2-D
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.