Improved algorithms for dynamic page migration

Abstract The dynamic page migration problem [4] is defined in a distributed network of n mobile nodes sharing one indivisible memory page of size D. During runtime, the nodes can both access a unit of data from the page and move with a constant speed, thus changing the costs of communication. The problem is to compute online a schedule of page movements to minimize the total communication cost. In this paper we construct and analyze the first deterministic algorithm for this problem. We prove that it achieves an (up to a constant factor) optimal competitive ratio O(n · √ D). We show that the randomization of this algorithm improves this ratio to O ( √ D · log n) (against an oblivious adversary). This substantially improves an O(n · √ D) upper bound from [4]. We also give an almost matching lower bound of Ω ( √ D · √ log n) for this problem.