06070912

a

06070912 Giakkoupis, George Sauerwald, Thomas Sun, He Woelfel, Philipp Low randomness rumor spreading via hashing. D\"urr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th -- March 3rd, 2012. Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik (ISBN 978-3-939897-35-4). LIPICS -- Leibniz International Proceedings in Informatics 14, 314-325, electronic only (2012). 2012 Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik EN parallel and distributed computing randomness rumor spreading

doi:10.4230/LIPIcs.STACS.2012.314

Summary: 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 in [the first and the last author, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA '11). 449--461 (2011)].