Abstract
Gossip protocols are communication protocols in which, periodically, every node of a network exchanges information with some other node chosen according to some (randomized) strategy. These protocols have recently found various types of applications for the management of distributed systems. Spatial gossip protocols are gossip protocols that use the underlying spatial structure of the network, in particular for achieving the ”closest-first” property. This latter property states that the closer a node is to the source of a message the more likely it is to receive this message within a prescribed amount of time. Spatial gossip protocols find many applications, including the propagation of alarms in sensor networks, and the location of resources in P2P networks. We design a sub-linear spatial gossip protocol for arbitrary graphs metric. More specifically, we prove that, for any graph metric with maximum degree Δ, for any source s and any ball centered at s with size b, new information is spread from s to all nodes in the ball within \(O( (\sqrt {b \log b}\, \log \log b + \Delta) \log b )\) rounds, with high probability. Moreover, when applied to general metrics with uniform density, the same protocol achieves a propagation time of O(log2 bloglogb) rounds.
Both authors received additional supports from the ANR project ”ALADDIN”, from the INRIA project ”GANG”.
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
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: 6th ACM Symposium on Principles of Distributed Computing (PODC), pp. 1–12 (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)
Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal Augmentation Schemes for Network Navigability: Overcoming the \(\sqrt{n}\)-Barrier. In: 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 1–7 (2007)
Frieze, A., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Math. 10, 57–77 (1985)
Gupta, I., Kermarrec, A.-M., Ganesh, A.: Efficient Epidemic-Style Protocols for Reliable and Scalable Multicast. In: 21st Symposium on Reliable Distributed Systems (SRDS), pp. 180–189 (2002)
Kempe, D., Dobra, A., Gehrke, J.: Computing Aggregate Information using Gossip. In: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS (2003)
Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. In: 33rd ACM Symposium on Theory of Computing, pp. 163–172 (2001)
Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based communication mechanisms. In: Proc. 43rd IEEE Symp. on Foundations of Computer Science, pp. 471–480 (2002)
Luo, J., Eugster, P., Hubaux, J.-P.: Route driven gossip: probabilistic reliable multicast in ad hoc networks. In: 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 2229–2239 (2003)
Pittel, B.: On spreading a rumour. SIAM J. Applied Math. 47, 213–223 (1987)
Plaxton, G., Rajaraman, R., Richa, A.: Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In: 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 311–320 (1997)
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
Baumann, H., Fraigniaud, P. (2010). Sub-linear Universal Spatial Gossip Protocols. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-11476-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11475-5
Online ISBN: 978-3-642-11476-2
eBook Packages: Computer ScienceComputer Science (R0)