Georgiou, ChryssisGilbert, SethGuerraoui, RachidKowalski, Dariusz2008-06-052008-06-052008-06-052008https://infoscience.epfl.ch/handle/20.500.14299/26087In 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.GossipEpidemicAsynchronyComplexityAdaptive versus Oblivious AdversaryRandomizationConsensustext::conference output::conference proceedings::conference paper