Competitive algorithms for distributed data management (extended abstract)

ABSTRACT

We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([C], [DF], [ML]), where copies of a file may be stored in the local storage of some subset of processors, copies may be replicated and discarded over time so as to optimize communication costs, but multiple copies must be kept consistent and at least one copy must be stored somewhere in the network at all times. We deal with competitive algorithms for minimizing communication costs, over arbitrary sequences of reads and writes, and arbitrary network topologies. We define the constrained file allocation problem to be the solution of many individual file allocation problems simultaneously, subject to the constraints of local memory size. We give competitive algorithms for this prblem on uniform networks. We then introduce distributed competitive algorithms for on-line data tracking (a generalization of mobile user tracking [AP1, AP3] to transform our competitive distributed data management algorithms into distributed algorithms themselves.

REFERENCES

• AP1: B. Awerbuch and D. Peleg. Online Tracking of Mobile Users. Technical Report MIT/LCS/TM- 410, Aug. 1989.
• AP2: B. Awerbuch and D. Peleg. Sparse Partitions. In Proc. of the 31st Ann. Syrup. on Foundations of Computer science, pages 503-513, October 1990.
• AP3: Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, Proceedings of the conference on Communications architecture & protocols, p.221-233, September 03-06, 1991, Zurich, Switzerland
• BBKTW: S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
• BLS: A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
• BS: D.L. Black and D.D. Sleator. Competitive Algorithms for Replication and Migration Problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon Universit-y, 1989.
• C: W.W. Chu. Optimal File Allocation in a Multiple Computer System. IEEE Transactions of Computers, 18(10), October 1969.
• CLRW: M. Chrobak, L. Larmore, N. Reingold, and J. Westbrook. Optimal Multiprocessor Migration Algorithms Using Work Functions. Unpublished.
• DF: Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982 [doi>10.1145/356876.356883]
• FKLMSY: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• HP: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• IW: M. Imase and B.M. Waxman. Dynamic Steiner Tree Problem. SIAM Journal on Discrete Mathematics, 4(3):369-384, August 1991.
• KMRS: A.R. Karlin, M.S. Manasse, L. Rudolph, and D.D. Sleator. Competitive Snoopy Caching. A1- gorithmica, 3(1):79-119, 1988.
• MMS: Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
• ML: Howard L. Morgan , K. Dan Levin, Optimal program and data locations in computer networks, Communications of the ACM, v.20 n.5, p.315-322, May 1977 [doi>10.1145/359581.359591]
• RS: Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
• ST: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• W: J. Westbrook. Randomized Algorithms for Multiprocessor Page Migration. Proc. of DIh/IACS Workshop on On-Line Algorithms, to appear.
• WY: J. Westbrook. and D.K. Yah. personal communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

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

General Terms:
Algorithms, Management, Theory