Startseite > Publikationen > Publikationen


Bienkowski, Marcin;Korzeniowski, Miroslaw:

Dynamic Page Migration under Brownian Motion.

In: Proc. of the European Conference in Parallel Processing (Euro-Par), S. 962-971, 2005


We consider Dynamic Page Migration (DPM) problem, one of the
fundamental subproblems of data management in dynamically changing networks. We investigate a hybrid scenario,
where access patterns to the shared object are dictated by an adversary, and each processor performs a random
walk in X. We extend the previous results of citedynamic-page-migration: we develop
algorithms for the case where X is a ring, and prove that with high probability they achieve
a competitive ratio of $tildeØ (min sqrt[4]D, n )$, where $D$ is the size of the shared object
and $n$ is the number of nodes in the network. These results hold also for any
d-dimensional torus or mesh with diameter at least $tildeOmega(sqrtD)$.




author = {Bienkowski, Marcin and Korzeniowski, Miroslaw},
title = {Dynamic Page Migration under Brownian Motion},
booktitle = {Proc. of the European Conference in Parallel Processing (Euro-Par)},
pages = {962-971},
year = {2005},

BibTeX in die Zwischenablage kopieren