How efficient can gossip be? (On the cost of resilient information exchange)

Alistarh D-A, Gilbert S, Guerraoui R, Zadimoghaddam M. 2010. How efficient can gossip be? (On the cost of resilient information exchange). ICALP: International Colloquium on Automota, Languages and Programming, LNCS, vol. 6199 LNCS, 115–126.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Alistarh, Dan-AdrianIST Austria; Gilbert, Seth; Guerraoui, Rachid; Zadimoghaddam, Morteza
Series Title
LNCS
Abstract
Gossip, also known as epidemic dissemination, is becoming an increasingly popular technique in distributed systems. Yet, it has remained a partially open question: how robust are such protocols? We consider a natural extension of the random phone-call model (introduced by Karp et al. [1]), and we analyze two different notions of robustness: the ability to tolerate adaptive failures, and the ability to tolerate oblivious failures. For adaptive failures, we present a new gossip protocol, TrickleGossip, which achieves near-optimal O(n log 3 n) message complexity. To the best of our knowledge, this is the first epidemic-style protocol that can tolerate adaptive failures. We also show a direct relation between resilience and message complexity, demonstrating that gossip protocols which tolerate a large number of adaptive failures need to use a super-linear number of messages with high probability. For oblivious failures, we present a new gossip protocol, CoordinatedGossip, that achieves optimal O(n) message complexity. This protocol makes novel use of the universe reduction technique to limit the message complexity.
Publishing Year
Date Published
2010-01-01
Acknowledgement
We would like to thank Prof. Hagit Attiya and the anonymous reviewers for their useful comments on earlier drafts of this paper.
Volume
6199 LNCS
Issue
PART 2
Page
115 - 126
Conference
ICALP: International Colloquium on Automota, Languages and Programming
IST-REx-ID
755

Cite this

Alistarh D-A, Gilbert S, Guerraoui R, Zadimoghaddam M. How efficient can gossip be? (On the cost of resilient information exchange). In: Vol 6199 LNCS. Springer; 2010:115-126. doi:10.1007/978-3-642-14162-1_10
Alistarh, D.-A., Gilbert, S., Guerraoui, R., & Zadimoghaddam, M. (2010). How efficient can gossip be? (On the cost of resilient information exchange) (Vol. 6199 LNCS, pp. 115–126). Presented at the ICALP: International Colloquium on Automota, Languages and Programming, Springer. https://doi.org/10.1007/978-3-642-14162-1_10
Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Morteza Zadimoghaddam. “How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange),” 6199 LNCS:115–26. Springer, 2010. https://doi.org/10.1007/978-3-642-14162-1_10.
D.-A. Alistarh, S. Gilbert, R. Guerraoui, and M. Zadimoghaddam, “How efficient can gossip be? (On the cost of resilient information exchange),” presented at the ICALP: International Colloquium on Automota, Languages and Programming, 2010, vol. 6199 LNCS, no. PART 2, pp. 115–126.
Alistarh D-A, Gilbert S, Guerraoui R, Zadimoghaddam M. 2010. How efficient can gossip be? (On the cost of resilient information exchange). ICALP: International Colloquium on Automota, Languages and Programming, LNCS, vol. 6199 LNCS, 115–126.
Alistarh, Dan-Adrian, et al. How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange). Vol. 6199 LNCS, no. PART 2, Springer, 2010, pp. 115–26, doi:10.1007/978-3-642-14162-1_10.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar