Asynchronous gossip
Ημερομηνία
2013Source
Journal of the ACMVolume
60Issue
2Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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. © 2013 ACM.