Spatial gossip and resource location protocols

ABSTRACT

The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.In many settings, such as a cluster of distributed computing hosts, new information is generated at individual nodes, and is most "interesting" to nodes that are nearby. Thus, we propose distance-based propagation bounds as a performance measure for gossip mechanisms: a node at distance d from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with d, and is independent of the size of the network.For nodes arranged with uniform density in Euclidean space, we present natural gossip mechanisms, called spatial gossip, that satisfy such a guarantee: new information is spread to nodes at distance d, with high probability, in O(log^{1 + ϵ} d) time steps. Such a bound combines the desirable qualitative features of uniform gossip, in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding, in which information is spread with a delay that is linear in the distance and independent of the network size. Our mechanisms and their analysis resolve a conjecture of Demers et al. [1987].We further show an application of our gossip mechanisms to a basic resource location problem, in which nodes seek to rapidly learn the location of the nearest copy of a resource in a network. This problem, which is of considerable practical importance, can be solved by a very simple protocol using Spatial Gossip, whereas we can show that no protocol built on top of uniform gossip can inform nodes of their approximately nearest resource within poly-logarithmic time. The analysis relies on an additional useful property of spatial gossip, namely that information travels from its source to sinks along short paths not visiting points of the network far from the two nodes.

REFERENCES

• 1: D. Agrawal , A. El Abbadi , R. C. Steinke, Epidemic algorithms in replicated databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-172, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263680]
• 2: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 3: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 4: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 5: F. Göbel , J. Orestes Cerdeira , H. J. Veldman, Label-connected graphs and the gossip problem, Discrete Mathematics, v.87 n.1, p.29-40, Jan. 19, 1991 [doi>10.1016/0012-365X(91)90068-D]
• 6: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, Scalable Fault-Tolerant Aggregation in Large Process Groups, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.433-442, July 01-04, 2001
• 7: Hedetniemi, S., Hedetniemi, S., and Liestman, A. 1988. A survey of gossiping and broadcasting in communication networks. Networks 18, 319--349.
• 8: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 9: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 10: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 11: David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
• 12: David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Journal of Computer and System Sciences, v.64 n.4, p.820-842, June 2002 [doi>10.1006/jcss.2002.1829]
• 13: Meng Lin , Keith Marzullo , Stefano Masini, Gossip versus Deterministic Flooding: Low Message Overhead and High Reliability for Broadcasting on Small Networks, University of California at San Diego, La Jolla, CA, 1999
• 14: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 15: Robbert Van Renesse, Scalable and Secure Resource Location, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 4, p.4012, January 04-07, 2000
• 16: van Renesse, R., Minsky, Y., and Hayden, M. 1998. A gossip-style failure-detection service. In Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing. 55--70.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Keywords:
Gossip, decentralized algorithm, resource location