de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Gossip vs. Markov Chains, and Randomness-efficient Rumor Spreading

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons79279

Guo,  Zeyu
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45576

Sun,  He
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Guo, Z., & Sun, H. (2015). Gossip vs. Markov Chains, and Randomness-efficient Rumor Spreading. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 411-430). Philadelphia, PA: SIAM. doi:10.1137/1.9781611973730.29.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-A256-C
Zusammenfassung
We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network. We present the first protocol for any expander graph $G$ with $n$ nodes such that, the protocol informs every node in $O(\log n)$ rounds with high probability, and uses $\tilde{O}(\log n)$ random bits in total. The runtime of our protocol is tight, and the randomness requirement of $\tilde{O}(\log n)$ random bits almost matches the lower bound of $\Omega(\log n)$ random bits for dense graphs. We further show that, for many graph families, polylogarithmic number of random bits in total suffice to spread the rumor in $O(\mathrm{poly}\log n)$ rounds. These results together give us an almost complete understanding of the randomness requirement of this fundamental gossip process. Our analysis relies on unexpectedly tight connections among gossip processes, Markov chains, and branching programs. First, we establish a connection between rumor spreading processes and Markov chains, which is used to approximate the rumor spreading time by the mixing time of Markov chains. Second, we show a reduction from rumor spreading processes to branching programs, and this reduction provides a general framework to derandomize gossip processes. In addition to designing rumor spreading protocols, these novel techniques may have applications in studying parallel and multiple random walks, and randomness complexity of distributed algorithms.