## Aktuell:

#### 18. September 2020

## Erste WiGeP-Tagung zur Virtuellen Produktentwicklung wieder möglich

Die Paderborner Professorin Iris Gräßler (Universität Paderborn, Heinz Nixdorf Institut) folgte gemeinsam mit 14 ...

# Publikationen

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

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

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)$.

BibTeX in die Zwischenablage kopieren

# Fighting Against Two Adversaries: Page Migration in Dynamic Network.

In: Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), Apr. 2004## 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 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 thecommunication 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)$.

## Dateien

hni1690.pdf## Bibtex

@inproceedings{hniid=1690,

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},

}

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