MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Karp, Richard
Schindelhauer, Christian
Shenker, Scott
Vöcking, Berthold
dblp
dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
Voecking2000
Title, Booktitle
Title*:
Randomized Rumor Spreading
Booktitle*:
41th Annual Symposium on Foundations of Computer Science (FOCS-00)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Redondo Beach, USA
Language:
English
Event Date*
(no longer used):
November, 12-4
Organization:
IEEE Computer Society
Event Start Date:
12 November 2000
Event End Date:
14 November 2000
Publisher
Name*:
IEEE
URL:
Address*:
Washington, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
November
Pages:
565-574
Year*:
2000
VG Wort Pages:
30
ISBN/ISSN:
0-7695-0852-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We investigate the class of so-called epidemic algorithms that are commonly used for the lazy transmission of
updates to distributed copies of a database. These algorithms use a simple randomized communication
mechanism to ensure robustness. Suppose $n$ players communicate in parallel rounds in each of which every
player calls a randomly selected communication partner. In every round, players can generate rumors
(updates) that are to be distributed among all players. Whenever communication is established between two
players, each one must decide which of the rumors to transmit. The major problem (arising due to the
randomization) is that players might not know which rumors their partners have already received. For
example, a standard algorithm forwarding each rumor from the calling to the called players for $\Theta(\ln
n)$ rounds needs to transmit the rumor $\Theta(n \ln n)$ times in order to ensure that every player finally
receives the rumor with high probability.

We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the
positive side, we show that the communication overhead can be reduced significantly. We give an algorithm
using only $O(n \ln\ln n)$ transmissions and $O(\ln n)$ rounds. In addition, we prove the robustness of this
algorithm, e.g., against adversarial failures. On the negative side, we show that any address-oblivious algorithm
(i.e., an algorithm that does not use the addresses of communication partners) needs to send $\Omega(n \ln\ln
n)$ messages for each rumor regardless of the number of rounds. Furthermore, we give a general lower bound
showing that time- and communication-optimality cannot be achieved simultaneously using random phone
calls, that is, every algorithm that distributes a rumor in $O(\ln n)$ rounds needs $\omega(n)$ transmissions.
URL for the Abstract:
http://www.mpi-sb.mpg.de/~voecking/abstracts/FOCS00.html
Keywords:
randomized algorithms, distributed algorithms, broadcasting, epidemic algorithms
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Voecking2000,
AUTHOR = {Karp, Richard and Schindelhauer, Christian and Shenker, Scott and V{\"o}cking, Berthold},
TITLE = {Randomized Rumor Spreading},
BOOKTITLE = {41th Annual Symposium on Foundations of Computer Science (FOCS-00)},
PUBLISHER = {IEEE},
YEAR = {2000},
ORGANIZATION = {IEEE Computer Society},
PAGES = {565--574},
ADDRESS = {Redondo Beach, USA},
MONTH = {November},
ISBN = {0-7695-0852-9},
}


Entry last modified by Christine Kiesel, 03/02/2010
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)
Berthold Voecking
Created
02/27/2001 05:19:48 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Berthold Voecking
Berthold Voecking
Edit Dates
30.05.2005 16:47:37
30.05.2005 16:35:57
30.05.2005 16:35:24
17/03/2002 17:31:50
28/02/2001 12:23:43