On the Complexity of Asynchronous Gossip

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.


Publié dans:
Proceedings of the 27th Annual Symposium on Principles of Distributed Computing
Présenté à:
27th Annual Symposium on Principles of Distributed Computing, Toronto, Canada, August, 2008
Année
2008
Mots-clefs:
Laboratoires:




 Notice créée le 2008-06-05, modifiée le 2019-01-17

n/a:
Télécharger le documentPDF
Lien externe:
Télécharger le documentURL
Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)