Document Open Access Logo

The k-Server Problem with Delays on the Uniform Metric Space

Authors Predrag Krnetić, Darya Melnyk, Yuyi Wang, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.61.pdf
  • Filesize: 434 kB
  • 13 pages

Document Identifiers

Author Details

Predrag Krnetić
  • Distributed Computing Group, ETH Zürich, Switzerland
Darya Melnyk
  • Distributed Computing Group, ETH Zürich, Switzerland
Yuyi Wang
  • Distributed Computing Group, ETH Zürich, Switzerland
Roger Wattenhofer
  • Distributed Computing Group, ETH Zürich, Switzerland

Cite AsGet BibTex

Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer. The k-Server Problem with Delays on the Uniform Metric Space. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.61

Abstract

In this paper, we present tight bounds for the k-server problem with delays in the uniform metric space. The problem is defined on n+k nodes in the uniform metric space which can issue requests over time. These requests can be served directly or with some delay using k servers, by moving a server to the corresponding node with an open request. The task is to find an online algorithm that can serve the requests while minimizing the total moving and delay costs. We first provide a lower bound by showing that the competitive ratio of any deterministic online algorithm cannot be better than (2k+1) in the clairvoyant setting. We will then show that conservative algorithms (without delay) can be equipped with an accumulative delay function such that all such algorithms become (2k+1)-competitive in the non-clairvoyant setting. Together, the two bounds establish a tight result for both, the clairvoyant and the non-clairvoyant settings.

Subject Classification

ACM Subject Classification
  • Theory of computation → K-server algorithms
  • Theory of computation → Caching and paging algorithms
  • Theory of computation → Online algorithms
Keywords
  • Online k-Server
  • Paging
  • Delayed Service
  • Conservative Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In Proceedings of the 49th Annual ACM SIGACT STOC, pages 551-563. ACM, 2017. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph S. Naor. A polylogarithmic-competitive algorithm for the k-server problem. In 2011 IEEE 52nd Annual FOCS, pages 267-276, 2011. Google Scholar
  3. Nikhil Bansal, Niv Buchbinder, and Joseph S. Naor. A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), 59(4):19, 2012. Google Scholar
  4. Marcin Bienkowski, Artur Kraska, and Paweł Schmidt. Online service with delay on a line. In SIROCCO, pages 237-248. Springer, 2018. Google Scholar
  5. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis, chapter 1, 3, 10, pages 1-22, 32-43, 150-181. Cambridge University Press, 2005. Google Scholar
  6. Marek Chrobak, H. Karloff, Tom Payne, and Sundar Vishwnathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4(2):172-181, 1991. Google Scholar
  7. Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k servers on trees. SIAM Journal on Computing, 20(1):144-148, 1991. Google Scholar
  8. Marek Chrobak and Jiří Sgall. The weighted 2-server problem. In Annual Symposium on Theoretical Aspects of Computer Science, pages 593-604. Springer, 2000. Google Scholar
  9. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online Matching: Haste Makes Waste! In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pages 333-344, New York, NY, USA, 2016. ACM. Google Scholar
  10. Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. Google Scholar
  11. Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, 2009. Google Scholar
  12. Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM (JACM), 42(5):971-983, 1995. Google Scholar
  13. Elias Koutsoupias and Christos H. Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249-252, 1996. Google Scholar
  14. Elias Koutsoupias and David Scot Taylor. The cnn problem and other k-server variants. In Annual Symposium on Theoretical Aspects of Computer Science, pages 581-592. Springer, 2000. Google Scholar
  15. J. R. Lee. Fusible hsts and the randomized k-server conjecture. In 2018 IEEE 59th Annual Symposium on FOCS, pages 438-449, October 2018. Google Scholar
  16. Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for online problems. In Proceedings of the twentieth annual ACM STOC, pages 322-333. ACM, 1988. Google Scholar
  17. Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11(2):208-230, 1990. Google Scholar
  18. Prabhakar Raghavan and Marc Snir. Memory versus randomization in on-line algorithms. In International Colloquium on Automata, Languages, and Programming, pages 687-703. Springer, 1989. Google Scholar
  19. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact