Georgiou, ChryssisGilbert, SethGuerraoui, RachidKowalski, Dariusz R.2013-10-012013-10-012013-10-01201310.1145/2450142.2450147https://infoscience.epfl.ch/handle/20.500.14299/95104WOS:000318628500005We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. The algorithmic techniques proposed in this article can be used for improving the message complexity of distributed algorithms that rely on an all-to-all message exchange paradigm and are designed for an asynchronous environment. As an example, we show how to improve the message complexity of asynchronous randomized consensus.AlgorithmsReliabilityTheoryGossipepidemicasynchronycomplexityadaptive versus oblivious adversaryrandomizationconsensustext::journal::journal article::research article