Data management problems arise in a distributed network of processors where copies of shared variables are stored. One basic problem of the file allocation is page migration, where only one copy of the file can be kept in the network. During runtime, processors access unit size data items from this page, and the system is allowed to move the page from one processor to another in order to minimize the total communication cost.
The authors extend these concepts by allowing the nodes to move with restricted pace change, and with stochastic costs of communication. When both the changes of the network and the request sequence are given by some adversarial entity, the authors establish a tight bound on the competitive ratio of the problem.
This significant contribution combines the competitive analysis of an online problem with average stochastic processes, and two distinct independent resources. The results will be useful in mobile networks, and for networks that are not exclusively dedicated to page migration.
]]