Abstract
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 \(\mathcal{X}\). We extend the previous results of [4]: we develop algorithms for the case where \(\mathcal{X}\) is a ring, and prove that with high probability they achieve a competitive ratio of \(\tilde{\mathcal{O}} (\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 \(\tilde{\Omega}(\sqrt{D})\).
Partially supported by DFG-Sonderforschungsbereich 376 “Massive Parallelität: Algorithmen Entwurfsmethoden Anwendungen” and by the Future and Emerging Technologies programme of the EU under EU Contract 001907 DELIS “Dynamically Evolving, Large Scale Information Systems”.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Awerbuch, B., Bartal, Y., Fiat, A.: Competitive distributed file allocation. In: Proc. of the 25th ACM Symp. on Theory of Computing (STOC), pp. 164–173 (1993)
Bartal, Y., Charikar, M., Indyk, P.: On page migration and other relaxed task systems. Theoretical Computer Science 268(1), 43–66 (2001)
Bienkowski, M., Dynia, M., Korzeniowski, M.: Improved algorithms for dynamic page migration. In: Proc. of the 22nd Symp. on Theoretical Aspects of Computer Science (STACS), pp. 365–376 (2005)
Bienkowski, M., Korzeniowski, M., Meyer auf der Heide, F.: Fighting against two adversaries: Page migration in dynamic networks. In: Proc. of the 16th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 64–73 (2004)
Black, D.L., Sleator, D.D.: Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University (1989)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Chrobak, M., Larmore, L.L., Reingold, N., Westbrook, J.: Page migration algorithms using work functions. In: Proc. of the 4th Int. Symp. on Algorithms and Computation (ISAAC), pp. 406–415 (1993)
Lund, C., Reingold, N., Westbrook, J., Yan, D.C.K.: Competitive online algorithms for distributed data management. SIAM Journal on Computing 28(3), 1086–1111 (1999)
Rajesekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J.: Handbook of Randomized Computing, vol. II. Kluwer Academic Publishers, Dordrecht (2001)
Rosenthal, J.S.: Convergence rates for Markov chains. SIAM Review 37(3), 387–405 (1995)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)
Westbrook, J.: Randomized algorithms for multiprocessor page migration. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 7, 135–150 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bienkowski, M., Korzeniowski, M. (2005). Dynamic Page Migration Under Brownian Motion. In: Cunha, J.C., Medeiros, P.D. (eds) Euro-Par 2005 Parallel Processing. Euro-Par 2005. Lecture Notes in Computer Science, vol 3648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549468_105
Download citation
DOI: https://doi.org/10.1007/11549468_105
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28700-1
Online ISBN: 978-3-540-31925-2
eBook Packages: Computer ScienceComputer Science (R0)