Playing push vs pull: models and algorithms for disseminating dynamic data in networks

ABSTRACT

Consider a network in which a collection of source nodes maintain and periodically update data objects for a collection of sink nodes, each of which periodically accesses the data originating from some specified subset of the source nodes. We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. Our focus is on the following "push-pull" approach for this data dissemination problem. Whenever a data object is updated, its source relays the update to a designated subset of nodes, its push set; similarly, whenever a sink requires an update, it propagates its query to a designated subset of nodes, its pull set. The push and pull sets need to be chosen such that every pull set of a sink intersects the push sets of all its sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements.We formulate and study several variants of the above data dissemination problem, that take into account different paradigms for routing between sources (resp., sinks) and their push sets (resp., pull sets) -- multicast, unicast, and controlled broadcast -- as well as the aggregability of the data objects. Under the multicast model, we present an optimal polynomial time algorithm for tree networks, which yields a randomized O(log n)-approximation algorithm for n-node general networks, for which the problem is hard to approximate within a constant factor. Under the unicast model, we present a randomized O(log n)-approximation algorithm for non-metric costs and a matching hardness result. For metric costs, we present an O(1)-approximation and matching hardness result for the case where the interests of any two sinks are either disjoint or identical. Finally, under the controlled broadcast model, we present optimal polynomial-time algorithms.While our optimization problems have been formulated in the context of data communication in networks, our problems also have applications to network design and multicommodity facility location and are of independent interest.

REFERENCES

• 1: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 2: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
• 3: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 4: H. Chernoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493--509, 1952.
• 5: Miroslav Chlebík , Janka Chlebíková, Approximation Hardness of the Steiner Tree Problem on Graphs, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.170-179, July 03-05, 2002
• 6: Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301447]
• 7: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
• 10: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993 ]
• 11: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13--30, 1963.
• 12: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 13: G. Konjevod, R. Ravi, and F. S. Salman. On approximating planar metrics by tree metrics. Information Processing Letters, 80(4):213--219, 2001.
• 14: G. Kortsarz. On the hardness of approximating spanners. Algorithmica, 30(3):432--450, 2001.
• 15: Guy Kortsarz , David Peleg, Generating Low-Degree 2-Spanners, SIAM Journal on Computing, v.27 n.5, p.1438-1456, Oct. 1998 [doi>10.1137/S0097539794268753]
• 16: Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D ]
• 17: Xin Liu , Qingfeng Huang , Ying Zhang, Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031510]
• 18: R. Ravi , A. Sinha, Multicommodity facility location, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 19: Gabriele Reich , Peter Widmayer, Beyond Steiner's Problem: A VLSI Oriented Generalization, Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, p.196-210, June 14-16, 1989
• 20: D. Sandler, A. Mislove, A. Post, and P. Druschel. Feedtree: Sharing web micronews with peer-to-peer event notification. In Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS'05), Ithaca, New York, Feb. 2005.
• 21: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 22: Maxim Sviridenko, An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.240-257, May 27-29, 2002
• 23: Chaitanya Swamy , Amit Kumar, Primal-Dual Algorithms for Connected Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.256-270, September 17-21, 2002
• 24: David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani, A primal-dual approximation algorithm for generalized Steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.708-717, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167268]
• 25: Neal E. Young, K-medians, facility location, and the Chernoff-Wald bound, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.86-95, January 09-11, 2000, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Network problems; Graph algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
NP-Completeness, approximation algorithms, data dissemination, multicast tree, network design, push & pull