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: Goto entry point

 Author, Editor
 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:

 (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},
BOOKTITLE = {41th Annual Symposium on Foundations of Computer Science (FOCS-00)},
PUBLISHER = {IEEE},
YEAR = {2000},
ORGANIZATION = {IEEE Computer Society},
PAGES = {565--574},