Low Randomness Rumor Spreading via Hashing

George Giakkoupis, Thomas Sauerwald, He Sun, Philipp Woelfel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all 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 wellstudied 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, e.g., [10, 17, 6, 15], require Ω(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 [15].
Original languageEnglish
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France
Number of pages12
Publication statusPublished - 2012
EventSTACS 2012 : Symposium on Theoretical Aspects of Computer Science - Paris, France
Duration: 29 Feb 20123 Mar 2012


ConferenceSTACS 2012 : Symposium on Theoretical Aspects of Computer Science
Abbreviated titleSTACS 2012


Dive into the research topics of 'Low Randomness Rumor Spreading via Hashing'. Together they form a unique fingerprint.

Cite this