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 log3 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Karp, R., Schindelhauer, C., Shenker, S., Vöcking, B.: Randomized rumor spreading. In: FOCS (2000)
Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: PODC (1987)
Birman, K., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., Minsky, Y.: Bimodal multicast. ACM Trans. on Comp. Sys. 17, 41–86 (1999)
Eugster, P., Guerraoui, R., Handurukande, S., Kermarrec, A.-M., Kouznetsov, P.: Lightweight probabilistic broadcast. ACM Trans. on Comp. Sys. 21(4) (2003)
Kermarrec, A., Massoulie, L., Ganesh, A.: Probabilistic reliable multicast in ad hoc networks. IEEE Trans. on Parallel and Distr. Syst. 14 (2003)
Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. Journal of ACM, 943–967 (2004)
Chaintreau, A., Le Boudec, J.-Y., Ristanovic, N.: The age of gossip: spatial mean field regime. In: SIGMETRICS (2009)
Chlebus, B.S., Kowalski, D.R.: Robust gossiping with an application to consensus. J. Comput. Syst. Sci. 72(8), 1262–1281 (2006)
Chlebus, B.S., Kowalski, D.R.: Time and communication efficient consensus for crash failures (2006)
Frieze, A.M., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics (10), 55–77 (1985)
Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213–223 (1987)
Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol. 450, pp. 128–137. Springer, Heidelberg (1990)
Elsässer, R.: On the communication complexity of randomized broadcasting in random-like graphs. In: SPAA (2006)
Berenbrink, P., Elsaesser, R., Friedetzky, T.: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In: PODC (2008)
Elsässer, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: SODA (2008)
Elsässer, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci. 410(36), 3414–3427 (2009)
Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: SODA (2008)
Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 366–377. Springer, Heidelberg (2009)
Doerr, B., Huber, A., Levavi, A.: Strong robustness of randomized rumor spreading protocols. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878. Springer, Heidelberg (2009)
Czumaj, A., Gasieniec, L., Pelc, A.: Time and cost trade-offs in gossiping. SIAM Journal on Discrete Mathematics 11, 400–413 (1998)
Georgiou, C., Gilbert, S., Guerraoui, R., Kowalski, D.R.: On the complexity of asynchronous gossip. In: PODC (2008)
Hromkovic, J., Klasing, R., Pelc, A., Ruzika, P., Unger, W.: Dissemination of information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Springer, Heidelberg (2005)
Ben-Or, M., Pavlov, E., Vaikuntanathan, V.: Byzantine agreement in the full-information model in O(log n) rounds. In: STOC (2006)
Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous byzantine agreement and leader election with full information. In: SODA, pp. 1038–1047 (2008)
King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA, pp. 990–999 (2006)
King, V., Saia, J.: Fast, scalable byzantine agreement in the full information model with a nonadaptive adversary. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805. Springer, Heidelberg (2009)
Gilbert, S., Kowalski, D.: Distributed agreement with optimal communication complexity. In: SODA (2010)
Alistarh, D., Gilbert, S., Guerraoui, R., Zadimoghaddam, M.: How efficient can gossip be? (technical report), https://infoscience.epfl.ch/record/148544
Dubhashi, D., Ranjan, D.: Balls and bins: A study in negative dependence. Random Structures and Algorithms 13, 99–124 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alistarh, D., Gilbert, S., Guerraoui, R., Zadimoghaddam, M. (2010). How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange). In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds) Automata, Languages and Programming. ICALP 2010. Lecture Notes in Computer Science, vol 6199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14162-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-14162-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14161-4
Online ISBN: 978-3-642-14162-1
eBook Packages: Computer ScienceComputer Science (R0)