000124981 001__ 124981
000124981 005__ 20190316234305.0
000124981 037__ $$aCONF
000124981 245__ $$aOn the Complexity of Asynchronous Gossip
000124981 260__ $$c2008
000124981 269__ $$a2008
000124981 336__ $$aConference Papers
000124981 520__ $$aIn this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. In the latter case, we present three randomized algorithms for achieving gossip, each offering a different trade-off between time and message complexity. We then show how to use these gossip algorithms to develop message-efficient asynchronous (randomized) consensus protocols.
000124981 6531_ $$aGossip
000124981 6531_ $$aEpidemic
000124981 6531_ $$aAsynchrony
000124981 6531_ $$aComplexity
000124981 6531_ $$aAdaptive versus Oblivious Adversary
000124981 6531_ $$aRandomization
000124981 6531_ $$aConsensus
000124981 700__ $$aGeorgiou, Chryssis
000124981 700__ $$0240435$$g176464$$aGilbert, Seth
000124981 700__ $$g105326$$aGuerraoui, Rachid$$0240335
000124981 700__ $$aKowalski, Dariusz
000124981 7112_ $$dAugust, 2008$$cToronto, Canada$$a27th Annual Symposium on Principles of Distributed Computing
000124981 773__ $$tProceedings of the 27th Annual Symposium on Principles of Distributed Computing
000124981 8564_ $$uhttp://www.podc.org/podc2008/$$zURL
000124981 8564_ $$uhttps://infoscience.epfl.ch/record/124981/files/AsynchGossip-PODC08.pdf$$zn/a$$s252262
000124981 909C0 $$xU10407$$0252114$$pDCL
000124981 909CO $$ooai:infoscience.tind.io:124981$$qGLOBAL_SET$$pconf$$pIC
000124981 937__ $$aLPD-CONF-2008-025
000124981 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000124981 980__ $$aCONF