research-article

Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

Authors:

Marcin Bienkowski,

Jarosław Byrka,

Marcin MuchaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 4

Article No.: 46, Pages 1 - 21

https://doi.org/10.1145/3340296

Published: 25 July 2019 Publication History

Abstract

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive Move-To-Local-Min (Mtlm) algorithm by Bartal et al. (SODA 1997). Like Mtlm, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing linear program) of a single phase of the algorithm. We also show that if an online algorithm operates in phases of fixed length and the adversary is able to modify the graph between phases, then the competitive ratio is at least 4.086.

References

[1]

Susanne Albers and Hisashi Koga. 1995. Page migration with limited local memory capacity. In Proc. 4th Int. Workshop on Algorithms and Data Structures (WADS). 147--158.

Digital Library

[2]

Baruch Awerbuch, Yair Bartal, and Amos Fiat. 1993. Competitive distributed file allocation. In Proc. 25th ACM Symp. on Theory of Computing (STOC). 164--173.

Digital Library

[3]

Baruch Awerbuch, Yair Bartal, and Amos Fiat. 1993. Heat 8 dump: Competitive distributed paging. In Proc. 34th IEEE Symp. on Foundations of Computer Science (FOCS). 22--31.

Digital Library

[4]

Baruch Awerbuch, Yair Bartal, and Amos Fiat. 1998. Distributed paging for general networks. J. Algorithms 28, 1 (1998), 67--104.

Digital Library

[5]

Yossi Azar, Ilan Reuven Cohen, and Alan Roytman. 2017. Online lower bounds via duality. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA). 1038--1050.

Digital Library

[6]

Yair Bartal. 1995. Competitive Analysis of Distributed On-line Problems—Distributed Paging. Ph.D. Dissertation. Tel-Aviv University.

[7]

Yair Bartal. 1996. Distributed paging. In Dagstul Workshop on On-line Algorithms. 97--117.

Digital Library

[8]

Yair Bartal, Moses Charikar, and Piotr Indyk. 2001. On page migration and other relaxed task systems. Theor. Comput. Sci. 268, 1 (2001), 43--66. Also appeared in Proc. of the 8th SODA, pages 43--52, 1997.

Digital Library

[9]

Yair Bartal, Amos Fiat, and Yuval Rabani. 1995. Competitive algorithms for distributed data management. J. Comput. Syst. Sci. 51, 3 (1995), 341--358.

Digital Library

[10]

Shai Ben-David, Allan Borodin, Richard M. Karp, Gabor Tardos, and Avi Wigderson. 1994. On the power of randomization in online algorithms. Algorithmica 11, 1 (1994), 2--14.

Digital Library

[11]

Marcin Bienkowski. 2012. Migrating and replicating data in networks. Computer Science—Research and Development 27, 3 (2012), 169--179.

[12]

Marcin Bienkowski, Jaroslaw Byrka, Miroslaw Korzeniowski, and Friedhelm Meyer auf der Heide. 2009. Optimal algorithms for page migration in dynamic networks. J. Discrete Algorithms 7, 4 (2009), 545--569.

Digital Library

[13]

David L. Black and Daniel D. Sleator. 1989. Competitive Algorithms for Replication and Migration Problems. Technical Report CMU-CS-89-201. Department of Computer Science, Carnegie-Mellon University.

[14]

Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press.

Digital Library

[15]

Marek Chrobak, Lawrence L. Larmore, Nick Reingold, and Jeffery Westbrook. 1997. Page migration algorithms using work functions. J. Algorithms 24, 1 (1997), 124--157.

Digital Library

[16]

Bezalel Gavish and Olivia R. Liu Sheng. 1990. Dynamic file migration in distributed computer systems. Commun. ACM 33, 2 (1990), 177--189.

Digital Library

[17]

Makoto Imase and Bernard M. Waxman. 1991. Dynamic Steiner tree problem. SIAM J. Discrete Math. 4, 3 (1991), 369--384.

Digital Library

[18]

Carsten Lund, Nick Reingold, Jeffery Westbrook, and Dicky C. K. Yan. 1999. Competitive on-line algorithms for distributed data management. SIAM J. Comput. 28, 3 (1999), 1086--1111.

Digital Library

[19]

Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking, and Matthias Westermann. 1997. Exploiting locality for data management in systems of limited bandwidth. In Proc. 38th IEEE Symp. on Foundations of Computer Science (FOCS). 284--293.

Digital Library

[20]

Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symp. on Theory of Computing (STOC). 597--606.

Digital Library

[21]

Akira Matsubayashi. 2008. Uniform page migration on general networks. Int. J. Pure Appl. Math. 42, 2 (2008), 161--168.

[22]

Akira Matsubayashi. 2015. A 3+Omega(1) lower bound for page migration. In Proc. 3rd Int. Symp. on Computing and Networking (CANDAR). 314--320.

Digital Library

[23]

Akira Matsubayashi. 2015. Asymptotically optimal online page migration on three points. Algorithmica 71, 4 (2015), 1035--1064.

Digital Library

[24]

Akira Matsubayashi, Amanj Khorramian. 2016. Uniform page migration problem in Euclidean space. Algorithms 9, 3 (2016).

[25]

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. 2007. AdWords and generalized online matching. J. ACM 54, 5 (2007).

Digital Library

[26]

Friedhelm Meyer auf der Heide, Berthold Vöcking, and Matthias Westermann. 1999. Provably good and practical strategies for non-uniform data management in networks. In Proc. 7th European Symp. on Algorithms (ESA). 89--100.

Digital Library

[27]

Jeffery Westbrook. 1994. Randomized algorithms for the multiprocessor page migration. SIAM J. Comput. 23 (1994), 951--965.

Digital Library

Cited By

Ghodselahi AKuhn F(2023)Toward Online Mobile Facility Location on General MetricsTheory of Computing Systems10.1007/s00224-023-10145-967:6(1268-1306)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00224-023-10145-9
Feldkord BKnollmann TMalatyali MHeide F(2021)Managing Multiple Mobile ResourcesTheory of Computing Systems10.1007/s00224-020-10023-865:6(943-984)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00224-020-10023-8

Index Terms

Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
  2. Models of computation
    1. Interactive computation

Recommendations

The (h,k)-Server Problem on Bounded Depth Trees
Special Issue on Soda'17 and Regular Papers

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h ≤ k servers. The problem is very poorly understood beyond uniform ...
Online Results for Black and White Bin Packing

In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Online algorithms with advice for bin packing and scheduling problems

We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 4

October 2019

297 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3351875

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2019

Accepted: 01 June 2019

Revised: 01 May 2019

Received: 01 February 2018

Published in TALG Volume 15, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Polish National Science Centre
European Research Council (ERC)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghodselahi AKuhn F(2023)Toward Online Mobile Facility Location on General MetricsTheory of Computing Systems10.1007/s00224-023-10145-967:6(1268-1306)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00224-023-10145-9
Feldkord BKnollmann TMalatyali MHeide F(2021)Managing Multiple Mobile ResourcesTheory of Computing Systems10.1007/s00224-020-10023-865:6(943-984)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00224-020-10023-8

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents