Startseite > Publikationen > Publikationen


Bienkowski, Marcin;Korzeniowski, Miroslaw;Dynia, Miroslaw:

Improved Algorithms for Dynamic Page Migration.

In: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), S. 365-376, 2005


The dynamic page migration problem citedynamic-page-migration 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 cdot sqrtD)$. We show that the randomization of this algorithm
improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary).
This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration.
We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.




author = {Bienkowski, Marcin and Korzeniowski, Miroslaw and Dynia, Miroslaw},
title = {Improved Algorithms for Dynamic Page Migration},
booktitle = {Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)},
pages = {365-376},
year = {2005},

BibTeX in die Zwischenablage kopieren