Startseite > Publikationen > Publikationen


Bienkowski, Marcin;Korzeniowski, Miroslaw;Meyer auf der Heide, Friedhelm:

Fighting Against Two Adversaries: Page Migration in Dynamic Network.

In: Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), Apr. 2004


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 indivisible 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 numerous times by many researchers, and
some online algorithms were proven to achieve a cost within a constant factor of the
optimal offline solution. However, all results were achieved under the assumption that the
communication costs between processors were fixed during the execution of the whole process.

In this paper we consider a model in which the communication costs can change in each time step,
but the pace of the changes is restricted. This is typical in mobile networks, 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 process, and an adversary dictates only which processor issues
a request. To analyze such a hybrid case, we introduce the notion of expected competitive ratio
and prove that, for the case where constant number of processors perform a random walk
on a torus or on a mesh of diameter $sqrtD$, it is $O(log^2 D)$.




author = {Bienkowski, Marcin and Korzeniowski, Miroslaw and Meyer auf der Heide, Friedhelm},
title = {Fighting Against Two Adversaries: Page Migration in Dynamic Network},
booktitle = {Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004)},
month = apr,
year = {2004},

BibTeX in die Zwischenablage kopieren