000124981 001__ 124981
000124981 005__ 20190117210459.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$$aGilbert, Seth$$g176464
000124981 700__ $$0240335$$aGuerraoui, Rachid$$g105326
000124981 700__ $$aKowalski, Dariusz
000124981 7112_ $$a27th Annual Symposium on Principles of Distributed Computing$$cToronto, Canada$$dAugust, 2008
000124981 773__ $$tProceedings of the 27th Annual Symposium on Principles of Distributed Computing
000124981 8564_ $$uhttp://www.podc.org/podc2008/$$zURL
000124981 8564_ $$s252262$$uhttps://infoscience.epfl.ch/record/124981/files/AsynchGossip-PODC08.pdf$$zn/a
000124981 909C0 $$0252114$$pDCL$$xU10407
000124981 909CO $$ooai:infoscience.tind.io:124981$$pconf$$pIC
000124981 937__ $$aLPD-CONF-2008-025
000124981 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000124981 980__ $$aCONF