id: 06070912
dt: a
an: 06070912
au: Giakkoupis, George; Sauerwald, Thomas; Sun, He; Woelfel, Philipp
ti: Low randomness rumor spreading via hashing.
so: Dürr, 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ür
    Informatik (ISBN 978-3-939897-35-4). LIPICS ‒ Leibniz International
    Proceedings in Informatics 14, 314-325, electronic only (2012).
py: 2012
pu: Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik
la: EN
cc: 
ut: parallel and distributed computing; randomness; rumor spreading
ci: 
li: doi:10.4230/LIPIcs.STACS.2012.314
ab: 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 $Ω(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)].
rv: