License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.314
URN: urn:nbn:de:0030-drops-34417
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3441/
Go to the corresponding LIPIcs Volume Portal

Giakkoupis, George ; Sauerwald, Thomas ; Sun, He ; Woelfel, Philipp

Low Randomness Rumor Spreading via Hashing

pdf-format:
57.pdf (0.6 MB)

Abstract

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all n nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several well-studied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor in O(log n) rounds with high probability.
Previous explicit algorithms require Omega(n) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-based algorithm is within an O(log n)-factor of the theoretical minimum determined by [Giakkoupis and Woelfel, 2011].

BibTeX - Entry

@InProceedings{giakkoupis_et_al:LIPIcs:2012:3441,
  author =	{George Giakkoupis and Thomas Sauerwald and He Sun and Philipp Woelfel},
  title =	{{Low Randomness Rumor Spreading via Hashing}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{314--325},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3441},
  URN =		{urn:nbn:de:0030-drops-34417},
  doi =		{10.4230/LIPIcs.STACS.2012.314},
  annote =	{Keywords: Parallel and Distributed Computing, Randomness, Rumor Spreading}
}

Keywords: Parallel and Distributed Computing, Randomness, Rumor Spreading
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI