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

DOI10.4230/LIPICS.ICALP.2017.13zbMATH Open1441.68293arXiv1609.00831OpenAlexW2963801628MaRDI QIDQ5111342FDOQ5111342

Jaroslaw Byrka, Marcin Mucha, Marcin Bienkowski

Publication date: 27 May 2020

Abstract: We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive 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 LP) 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.

Full work available at URL: https://arxiv.org/abs/1609.00831

Recommendations

• Dynamic Beats Fixed
• Competitive distributed file allocation.
• STACS 2005
• Asymptotically optimal online page migration on three points
• Asymptotically optimal online page migration on three points

zbMATH Keywords

online algorithmscompetitive analysisfactor-revealing linear programsfile migration

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Cited In (4)

• A \(3 + \Omega (1)\) lower bound for page migration
• Dynamic Beats Fixed
• Dynamic Balanced Graph Partitioning
• Online facility location with mobile facilities

This page was built for publication: Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111342)