On the Complexity of Asynchronous Gossip

• Presented at: 27th Annual Symposium on Principles of Distributed Computing, Toronto, Canada, August, 2008
• Published in: Proceedings of the 27th Annual Symposium on Principles of Distributed Computing
• : , 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. 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.

Keywords: Gossip ; Epidemic ; Asynchrony ; Complexity ; Adaptive versus Oblivious Adversary ; Randomization ; Consensus

Reference

• LPD-CONF-2008-025

• URL: http://www.podc.org/podc2008/

Record created on 2008-06-05, modified on 2012-03-21