Fighting Against Two Adversaries: Page Migration in Dynamic Networks (extended abstract)

Page migration is one of the fundamental subproblems in the framework of data management in networks. It occurs in a distributed network of processors sharing one indivis-ible memory page of size D, which is stored in one of the processors. During runtime, processors access unit size data items from the page, and the system is allowed to move the page from one processor to another in order to minimize the total communication cost. This problem was considered in the online setting numer-ous times by many researchers, and some online algorithms were proven to achieve a cost within a constant factor of the optimal oine solution. However, all results were achieved under the assumption that the communication costs between processors were xed during the execution of the whole pro-cess. In this paper we consider a model in which the commu-nication costs can change in each time step, but the pace of the changes is restricted. This is typical in mobile net-works, and also models the dynamics of networks that are not exclusively dedicated to the page migration. If both changes of the network and the request sequence are given by some adversarial entity, we prove a tight bound on the competitive ratio of the problem. However, the size of this ratio motivates us to assume that the changes of communication costs are modeled by some stochastic pro-cess, and an adversary dictates only which processor issues The full version of this paper is available unde