## Aktuell:

#### 05. Juli 2019

## Get to Know HNI am 11. Juli 2019

Jedes Jahr begrüßt das Heinz Nixdorf Institut zahlreiche, neue wissenschaftliche Mitarbeiter/innen. Das „Get to know ...

# Publikationen

Bienkowski, Marcin:

in a distributed network of processors sharing one indivisible memory page of size D. During runtime,

the processors access a unit of data from the page, and the system is allowed to migrate the page

between the processors. The problem is to compute (on-line) a schedule of page movements

to minimize the total communication cost.

The Dynamic Page Migration problem is an extension to the page migration.

It attempts to model the network dynamics, occurring, for example, in mobile networks.

However, the pace of changes is restricted, i.e. the distances between processors can

change only by a constant per round.

The movement of the nodes induce changes in the communication cost between each pair of nodes,

which is proportional to the distance between them raised to some power $alpha$.

This is typical for mobile wireless networks, where nodes can move with a constant speed,

and the cost of communication is measured in terms of energy used for sending the data.

Thus, by setting $alpha$ equal to the propagation exponent of the medium,

cost minimization becomes minimizing the total energy consumption in the system.

However, as proven in citedynamic-page-migration, if both network mobility and

request sequence are created by an adversary, then the competitive ratio is polynomially large in D and

in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we

consider a scenario in which the network mobility is adversarial, but the requests are

generated randomly by a stochastic process. We design an algorithm MTFR for this scenario,

and prove that it is O(1)-competitive, on expectation and with high probability.

BibTeX in die Zwischenablage kopieren

# Dynamic Page Migration with Stochastic Requests.

In: Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005), S. 270-278, Las Vegas, Nevada, USA, 17. - 20. Jul. 2005, ACM Press, New York, NY, USA## Abstract

The page migration problem is one of subproblems of data management in networks. It occursin a distributed network of processors sharing one indivisible memory page of size D. During runtime,

the processors access a unit of data from the page, and the system is allowed to migrate the page

between the processors. The problem is to compute (on-line) a schedule of page movements

to minimize the total communication cost.

The Dynamic Page Migration problem is an extension to the page migration.

It attempts to model the network dynamics, occurring, for example, in mobile networks.

However, the pace of changes is restricted, i.e. the distances between processors can

change only by a constant per round.

The movement of the nodes induce changes in the communication cost between each pair of nodes,

which is proportional to the distance between them raised to some power $alpha$.

This is typical for mobile wireless networks, where nodes can move with a constant speed,

and the cost of communication is measured in terms of energy used for sending the data.

Thus, by setting $alpha$ equal to the propagation exponent of the medium,

cost minimization becomes minimizing the total energy consumption in the system.

However, as proven in citedynamic-page-migration, if both network mobility and

request sequence are created by an adversary, then the competitive ratio is polynomially large in D and

in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we

consider a scenario in which the network mobility is adversarial, but the requests are

generated randomly by a stochastic process. We design an algorithm MTFR for this scenario,

and prove that it is O(1)-competitive, on expectation and with high probability.

## Dateien

paper.pdf## Bibtex

@inproceedings{hniid=2453,

author = {Bienkowski, Marcin},

title = {Dynamic Page Migration with Stochastic Requests},

booktitle = {Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005)},

pages = {270-278},

address = {Las Vegas, Nevada, USA},

publisher = {ACM Press, New York, NY, USA},

month = {17~-~20~} # jul,

year = {2005},

}

author = {Bienkowski, Marcin},

title = {Dynamic Page Migration with Stochastic Requests},

booktitle = {Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005)},

pages = {270-278},

address = {Las Vegas, Nevada, USA},

publisher = {ACM Press, New York, NY, USA},

month = {17~-~20~} # jul,

year = {2005},

}

BibTeX in die Zwischenablage kopieren