On the complexity of asynchronous gossip
Chryssis Georgiou, Seth Lewis Gilbert, Rachid Guerraoui, Dariusz Rafal Kowalski · 2008
In 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. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary.