Dynamic page migration with stochastic requests

ABSTRACT

The page migration problem is one of subproblems of data management in networks. It occurs in a distributed network of processors sharing one indivisible memory page of size D. During runtime, the processors access a unit of data from the page, and the system is allowed to migrate the page between the processors. The problem is to compute (on-line) a schedule of page movements to minimize the total communication cost.The Dynamic Page Migration problem is an extension to the page migration. It attempts to model the network dynamics, occurring, for example, in mobile networks. However, the pace of changes is restricted, i.e. the distances between processors can change only by a constant per round. The movement of the nodes induce changes in the communication cost between each pair of nodes, which is proportional to the distance between them raised to some power α. This is typical for mobile wireless networks, where nodes can move with a constant speed, and the cost of communication is measured in terms of energy used for sending the data. Thus, by setting α equal to the propagation exponent of the medium, cost minimization becomes minimizing the total energy consumption in the system.However, as proven in [7], if both network mobility and request sequence are created by an adversary, then the competitive ratio is polynomially large in D and in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we consider a scenario in which the network mobility is adversarial, but the requests are generated randomly by a stochastic process. We design an algorithm MTFR for this scenario, and prove that it is O(1)-competitive, on expectation and with high probability.

REFERENCES

• 1: 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]
• 2: 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
• 3: Yair Bartal , Moses Charikar , Piotr Indyk, On page migration and other relaxed task systems, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.43-52, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: 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]
• 5: M. Bienkowski, M. Dynia, and M. Korzeniowski. Improved algorithms for dynamic page migration. In Proc. of the 22nd Symp. on Theoretical Aspects of Computer Science (STACS), pages 365--376, 2005.
• 6: M. Bienkowski and M. Korzeniowski. Dynamic page migration under brownian motion. In Proc. of the European Conf. in Parallel Processing (Euro-Par), 2005. To appear.
• 7: Marcin Bienkowski , Miroslaw Korzeniowski , Friedhelm Meyer auf der Heide, Fighting against two adversaries: page migration in dynamic networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007923]
• 8: M. Bienkowski and F. Meyer auf der Heide. Page migration in dynamic networks. In Proc. of the 30th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), 2005. To appear.
• 9: 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 University, 1989.
• 10: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 11: Marek Chrobak , Lawrence L. Larmore , Nick Reingold , Jeffery Westbrook, Page Migration Algorithms Using Work Functions, Proceedings of the 4th International Symposium on Algorithms and Computation, p.406-415, December 15-17, 1993
• 12: I. S. Gradshteyn, I. M. Ryzhik, A. Jeffrey, and D. Zwillinger. Table of Integrals, Series, and Products. San Diego, CA: Academic Press, 6th edition, 2000.
• 13: Elias Koutsoupias , Christos H. Papadimitriou, Beyond Competitive Analysis, SIAM Journal on Computing, v.30 n.1, p.300-317, 2000 [doi>10.1137/S0097539796299540]
• 14: Carsten Lund , Nick Reingold , Jeffery Westbrook , Dicky C. K. Yan, On-Line Distributed Data Management, Proceedings of the Second Annual European Symposium on Algorithms, p.202-214, September 26-28, 1994
• 15: S. Rajesekaran, P. M. Pardalos, J. H. Reif, and J. Rolim. Handbook of Randomized Computing, volume II. Kluwer Academic Publishers, 2001.
• 16: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 17: 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]
• 18: J. Westbrook. Randomized algorithms for multiprocessor page migration. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 7:135--150, 1992.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Stochastic processes; Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
data management, dynamic networks, mobile networks, online algorithms, page migration