Document Open Access Logo

The Infinite Server Problem

Authors Christian Coester, Elias Koutsoupias, Philip Lazos



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.14.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Christian Coester
Elias Koutsoupias
Philip Lazos

Cite AsGet BibTex

Christian Coester, Elias Koutsoupias, and Philip Lazos. The Infinite Server Problem. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.14

Abstract

We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which implies the same lower bound for the (h,k)-server problem even when k>>h and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case.
Keywords
  • Online Algorithms
  • k-Server
  • Resource Augmentation

Metrics

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

References

  1. Nikhil Bansal, Marek Eliáš, Łukasz Jeż, and Grigorios Koumoutsos. The (h,k)-server problem on bounded depth trees. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pages 1022-1037. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.65.
  2. Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos, and Kirk Pruhs. Tight bounds for double coverage against weak adversaries. In International Workshop on Approximation and Online Algorithms, pages 47-58. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-28684-6_5.
  3. Yair Bartal and Eddie Grove. The harmonic k-server algorithm is competitive. J. ACM, 47(1):1-15, January 2000. URL: http://dx.doi.org/10.1145/331605.331606.
  4. Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. Theoretical Computer Science, 324(2):337-345, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.06.001.
  5. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA, 1998. Google Scholar
  6. Marek Chrobak, Howard Karloff, Tom Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discret. Math., 4(2):172-181, March 1991. URL: http://dx.doi.org/10.1137/0404017.
  7. Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput., 20(1):144-148, February 1991. URL: http://dx.doi.org/10.1137/0220008.
  8. Marek Chrobak and Lawrence L. Larmore. The server problem and on-line games. In On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Citeseer, 1992. Google Scholar
  9. Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Pricing online decisions: Beyond auctions. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 73-91, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dx.doi.org/10.1137/1.9781611973730.7.
  10. János Csirik, Csanád Imreh, John Noga, Steven S. Seiden, and Gerhard J. Woeginger. Buying a constant competitive ratio for paging. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA'01, pages 98-108, London, UK, 2001. Springer-Verlag. URL: http://dx.doi.org/10.1007/3-540-44676-1_8.
  11. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. On the additive constant of the k-server work function algorithm. In International Workshop on Approximation and Online Algorithms, pages 128-134. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-12450-1_12.
  12. Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algorithms. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 454-463 vol.2, Oct 1990. URL: http://dx.doi.org/10.1109/FSCS.1990.89566.
  13. Sandy Irani and Ronitt Rubinfeld. A competitive 2-server algorithm. Information Processing Letters, 39(2):85-91, 1991. URL: http://dx.doi.org/10.1016/0020-0190(91)90160-J.
  14. Kamal Jain. Personal Communication. Google Scholar
  15. Elias Koutsoupias. Weak adversaries for the k-server problem. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS'99, Washington, DC, USA, 1999. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFFCS.1999.814616.
  16. Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, May 2009. URL: http://dx.doi.org/10.1016/j.cosrev.2009.04.002.
  17. Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. ACM, 42(5):971-983, September 1995. URL: http://dx.doi.org/10.1145/210118.210128.
  18. Elias Koutsoupias and Christos H. Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249-252, March 1996. URL: http://dx.doi.org/10.1016/0020-0190(96)00010-5.
  19. Mark Manasse, Lyle McGeoch, and Daniel Sleator. Competitive algorithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC'88, pages 322-333, New York, NY, USA, 1988. ACM. URL: http://dx.doi.org/10.1145/62212.62243.
  20. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, February 1985. URL: http://dx.doi.org/10.1145/2786.2793.
  21. Neal Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525-541, 1994. URL: http://dx.doi.org/10.1007/BF01189992.
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