Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section