Improved Algorithms for Dynamic Page Migration
M. Bienkowski, M. Dynia, M. Korzeniowski, in: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 365–376.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Bienkowski, Marcin;
Dynia, Miroslaw;
Korzeniowski, Miroslaw
Abstract
The dynamic page migration problem citedynamic-page-migration is defined in <br>a distributed network of $n$ mobile nodes sharing one indivisible memory page <br>of size $D$. During runtime, the nodes can both access a unit of data from<br>the page and move with a constant speed, thus changing the costs of communication.<br>The problem is to compute <em> online</em> a schedule of page movements<br>to minimize the total communication cost.<br><br>In this paper we construct and analyze the first deterministic algorithm for this problem. <br>We prove that it achieves an (up to a constant factor) optimal competitive ratio <br>$O(n cdot sqrtD)$. We show that the randomization of this algorithm <br>improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary). <br>This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration.<br>We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.
Publishing Year
Proceedings Title
Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)
forms.conference.field.series_title_volume.label
Lecture Notes in Computer Science
Page
365-376
ISBN
LibreCat-ID
Cite this
Bienkowski M, Dynia M, Korzeniowski M. Improved Algorithms for Dynamic Page Migration. In: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science. ; 2005:365-376. doi:10.1007/978-3-540-31856-9_30
Bienkowski, M., Dynia, M., & Korzeniowski, M. (2005). Improved Algorithms for Dynamic Page Migration. In Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS) (pp. 365–376). https://doi.org/10.1007/978-3-540-31856-9_30
@inproceedings{Bienkowski_Dynia_Korzeniowski_2005, series={Lecture Notes in Computer Science}, title={Improved Algorithms for Dynamic Page Migration}, DOI={10.1007/978-3-540-31856-9_30}, booktitle={Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)}, author={Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw}, year={2005}, pages={365–376}, collection={Lecture Notes in Computer Science} }
Bienkowski, Marcin, Miroslaw Dynia, and Miroslaw Korzeniowski. “Improved Algorithms for Dynamic Page Migration.” In Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 365–76. Lecture Notes in Computer Science, 2005. https://doi.org/10.1007/978-3-540-31856-9_30.
M. Bienkowski, M. Dynia, and M. Korzeniowski, “Improved Algorithms for Dynamic Page Migration,” in Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 365–376.
Bienkowski, Marcin, et al. “Improved Algorithms for Dynamic Page Migration.” Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 365–76, doi:10.1007/978-3-540-31856-9_30.
Google Scholar
ISBN Search