We 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.
['Chryssis Georgiou', 'Seth Gilbert', 'Rachid Guerraoui', 'Dariusz R. Kowalski']
Asynchronous gossip