A data tracking scheme for general networks

ABSTRACT

Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of organizing a data tracking scheme for locating object copies. In this paper, we present a new tracking scheme for locating nearly copies of replicated objects in arbitrary distributed environments.

Our tracking scheme supports efficient accesses to data objects while keeping the local memory overhead low. In particular, our tracking scheme achieves an expected polylog(n)-approximation in the cost of any access operation, for an arbitrary network. The memory overhead incurred by our scheme is &Ogr;(polylog(n)) times the maximum number of objects stored at any node, with high probability. We also show that our tracking scheme adapts well to dynamic changes in the network.

REFERENCES

• 1: T. E. Anderson , M. D. Dahlin , J. M. Neefe , D. A. Patterson , D. S. Roselli , R. Y. Wang, Serverless network file systems, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.109-126, December 03-06, 1995, Copper Mountain, Colorado, United States
• 2: Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167142]
• 3: Baruch Awerbuch , Yair Bartal , Amos Fiat, Distributed paging for general networks, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.574-583, January 28-30, 1996, Atlanta, Georgia, United States
• 4: B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear cost sequential and distributed constructions. In Proceedings of the Thirty-Fourth Annual Symposium on Foundations of Computer Science, pages 638-647, 1993.
• 5: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 6: B. Awerbuch and D. Peleg. Sparse partitions. In Proceedings of the Thirty-First Annual IEEE Symposium on Foundations of Computer Science, pages 503-513, October 1990.
• 7: Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995 [doi>10.1145/210118.210132]
• 8: 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
• 9: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 10: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management, Journal of Computer and System Sciences, v.51 n.3, p.341-358, Dec. 1995 [doi>10.1006/jcss.1995.1073]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: J. L. Carter and M. N. Wegman. Universal Classes of Hash Functions. Journal of Computer and System Sciences, 18:143-154, 1979.
• 13: James D. Guyton , Michael F. Schwartz, Locating nearby copies of replicated Internet servers, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.288-298, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 14: S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L.Zhang, The placement ofInternet instrumentation, In Proceedings of IEEE INFOCOMM, 2000.
• 15: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 16: G. Konjevod, R. Ravi, and F. S. Salman. On approximating planar metrics by tree metrics. Submitted for publication in J. Algorithms, July 1997.
• 17: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 18: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 19: B. Maggs , F. Meyer auf der Heide , B. Voecking , M. Westermann, Exploiting Locality for Data Management in Systems of Limited Bandwidth, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.284, October 19-22, 1997
• 20: Friedhelm Meyer auf der Heide , Berthold Vöcking , Matthias Westermann, Caching in networks (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.430-439, January 09-11, 2000, San Francisco, California, United States
• 21: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 22: M. van Steen, F. J. Hauck, and A. S. Tanenbaum. A model for worldwide tracking of distributed objects. In Proceedings of the 1996 Conference on Telecommunications Information Networking Architecture (TINA 96), pages 203-212, September 1996.
• 23: Bang Ye Wu , Giuseppe Lancia , Vineet Bafna , Kun-Mao Chao , R. Ravi , Chuan Yi Tang, A polynomial time approximation scheme for minimum routing cost spanning trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.21-32, January 25-27, 1998, San Francisco, California, United States
• 24: Ouri Wolfson , Sushil Jajodia , Yixiu Huang, An adaptive data replication algorithm, ACM Transactions on Database Systems (TODS), v.22 n.2, p.255-314, June 1997 [doi>10.1145/249978.249982]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory, Verification