The infinite-server problem is the kk-server problem with infinitely many servers, all initially stationed at a single source point of a metric space; it was introduced by Coester, Koutsoupias, and Lazos together with an equivalence theorem: the problem is competitive on every metric space if and only if the resource-augmentation (h,k)(h,k)-server problem (an online algorithm with kk servers competing against an offline adversary with hh servers) is competitive on every metric space for some k=O(h)k = O(h), with the same equivalence also holding when every metric space is replaced by the real line. Subsequent work of Bienkowski, Byrka, Coester, and Jeż refuted competitiveness on general metric spaces and proved an Ω(log⁡D)\Omega(\log D) lower bound on trees of depth DD, while the best upper bound on such trees remains O(2D⋅D)O(2^D \cdot D), and the natural Move-Only-Outwards algorithm on depth-DD layered graphs has competitive ratio exactly D−12D - \tfrac{1}{2}. The objective is to settle the surviving open core of the source paper's open-problem list: (i) characterize the metric spaces on which the infinite-server problem is competitive — with the real line, where the known bounds are a lower bound of λ≈3.146\lambda \approx 3.146 and no finite upper bound at all, as the flagship open instance — together with usable criteria such as a decision procedure and parameter-based upper bounds; (ii) determine the correct dependence of the competitive ratio on the depth DD for trees and layered graphs, including the exact ratio for D=4D = 4, known only to lie between 3 and 3.5; and (iii) decide whether the deterministic and randomized competitive ratios are separated, since the only known superconstant lower-bound construction is inherently fractional.

Background

In the kk-server problem, an online algorithm controls kk servers in a metric space and must serve a sequence of requests that arrive one at a time, each request being a point to which some server must be moved; the goal is to minimize the total distance traveled, and each move must be decided without knowledge of future requests. An online algorithm is ρ\rho-competitive if its total cost is at most ρ\rho times the optimal offline cost up to an additive constant independent of the request sequence, and strictly ρ\rho-competitive if the additive constant can be zero. Manasse, McGeoch, and Sleator introduced this problem and conjectured that a kk-competitive algorithm exists on every metric space with more than kk points; the work function algorithm of Koutsoupias and Papadimitriou — which at each step moves the server prescribed by an optimal offline solution of the sequence seen so far — achieves the best known general bound of 2k−12k-1. In the resource-augmentation variant called the (h,k)(h,k)-server problem, or kk-server against weak adversaries, an online algorithm with kk servers is compared to an offline adversary with only h≤kh \le k servers. Koutsoupias showed that the work function algorithm is 2h2h-competitive simultaneously for all h≤kh \le k. Since Sleator and Tarjan's analysis of paging (the uniform-metric case), a modest augmentation has been known to bring the ratio down to k/(k−h+1)k/(k-h+1), which tends to 11 as k/hk/h grows; analogous bounded-ratio results hold for weighted stars and, by work of Bansal, Eliáš, Jeż, and Koumoutsos, for trees of bounded depth. Whether a bounded ratio survives on every metric as k/h→∞k/h \to \infty was for three decades a major open question, with the best general lower bounds at the time, 2.42.4 and 3.1463.146, coming from depth-2 trees and from the infinite-server problem respectively. Coester, Koutsoupias, and Lazos introduced the infinite-server problem as the natural k→∞k \to \infty limit: infinitely many servers, all initially at a distinguished point of the metric space called the source, serve the requests; deploying a fresh server from the source to a request is called spawning. Their equivalence theorem states that the infinite-server problem is competitive on every metric space if and only if the (h,k)(h,k)-server problem is competitive on every metric space for some k=O(h)k = O(h), and likewise with the real line in place of every metric space; for a fixed general metric space, only the direction from (h,k)(h,k)-server competitiveness to infinite-server competitiveness is proved. So the infinite-server problem is exactly the question of how much resource augmentation helps the kk-server problem. The known landscape is as follows. On metrics whose nonzero distances all lie within constant factors of one another, spawning a server to every newly requested point is competitive. A tight lower bound of λ≈3.146\lambda \approx 3.146, where λ\lambda is the largest real solution of λ=2+ln⁡λ\lambda = 2 + \ln \lambda, holds on any metric containing an infinite subspace of small diameter at positive distance from the source — in particular on the real line — generalizing a tight bound of Csirik, Imreh, Noga, Seiden, and Woeginger for paging with purchasable cache slots, and it transfers to the (h,k)(h,k)-server problem on the line even as k/h→∞k/h \to \infty. On edge-weighted trees of depth DD (the number of edges from the root, where all servers start, to the deepest node), the ratio is at most O(2D⋅D)O(2^D \cdot D), inherited from the (h,k)(h,k)-server algorithm of Bansal et al. through the equivalence theorem. On layered graphs of depth DD — graphs whose nodes are arranged in layers 0,…,D0,\dots,D, whose edges join only adjacent layers, whose metric is the number of edges on a shortest path, and whose unique layer-00 node is the source — the natural algorithm MOO ('Move Only Outwards', which only ever moves servers in the direction away from the source) has competitive ratio exactly D−12D-\tfrac{1}{2}; this is optimal for D≤3D \le 3, while for D≥4D \ge 4 the ratio is known only to be at least 33. Bienkowski, Byrka, Coester, and Jeż then showed that the ratio on trees of depth DD is at least Ω(log⁡D)\Omega(\log D) and consequently that no algorithm for the infinite-server problem has constant competitive ratio on general metric spaces, answering the original general-metrics question negatively. Classical techniques do not crack the remaining cases: speed-adjusted variants of the Double Coverage algorithm (which, on the line, moves the two servers adjacent to the request toward it), the work function algorithm, and balancing algorithms are all provably non-competitive for the infinite-server problem even on the line, and the only structural reduction available — partitioning the metric into distance rings [rn,rn+1)[r^n, r^{n+1}) around the source — merely reduces the line question to the case where all requests lie in a single bounded interval at positive distance from the source. Unlike the kk-server problem, whose (conjectured) answer depends only on the number of points of the metric, competitiveness of the infinite-server problem depends delicately on the geometry of the metric space, and no characterization is known.

Problem Statement

Infinitely many servers start at a distinguished source point ss of a metric space MM; requests arrive one at a time at points of MM, and each request must be served by moving some server to its point (deploying a new server from ss is allowed and costs its distance from ss), with each move decided without knowledge of future requests; the objective is to minimize total movement cost. An algorithm is ρ\rho-competitive if its total cost is at most ρ\rho times the optimal offline cost up to an additive constant independent of the request sequence (strictly ρ\rho-competitive if the additive constant is zero), and the problem is competitive on MM if some algorithm has bounded competitive ratio there. Determine how the geometry of MM governs competitiveness of this infinite-server problem, via the following questions, each of which is posed in the source paper and its follow-up literature: (1) Characterization: determine exactly which metric spaces admit a deterministic online algorithm with bounded competitive ratio for the infinite-server problem, and the corresponding question for randomized algorithms. (On the relationship with resource augmentation: by the source's Theorem 2.2, if for every hh the (h,k)(h,k)-server problem on a fixed metric space has bounded competitive ratio for some k=k(h)k = k(h), then the infinite-server problem on that space is competitive; the full equivalence with the (h,k)(h,k)-server problem for some k=O(h)k = O(h) is established in the source globally, over all metric spaces, and for the real line, not per arbitrary fixed metric space.) The flagship open instance is the real line with the source at the origin: is the infinite-server problem competitive there? Usable forms of the answer are also sought: a decision procedure that, given a concrete metric, decides membership in the competitive versus the non-competitive class; competitive-ratio upper bounds expressed in terms of natural metric parameters such as the aspect ratio (the ratio of the largest to the smallest nonzero distance); and the optimal strict competitive ratio on finite nn-point metrics as a function of nn (on a finite metric the non-strict ratio is trivially 11 — spawn a server to every point, at a fixed additive cost — so the strict version is the meaningful question). (2) Dependence on depth: for edge-weighted trees of depth DD with all servers starting at the root, determine the optimal competitive ratio ρ(D)\rho(D), known to satisfy Ω(log⁡D)≤ρ(D)≤O(2D⋅D)\Omega(\log D) \le \rho(D) \le O(2^D \cdot D); for layered graphs of depth DD (nodes in layers 0,…,D0,\dots,D, edges only between adjacent layers, shortest-path edge count as the metric, the unique layer-00 node as source), determine ρ(D)\rho(D), known to equal 1.51.5 for D=2D=2 and 2.52.5 for D=3D=3 and to satisfy 3≤ρ(D)≤D−123 \le \rho(D) \le D-\tfrac{1}{2} for D≥4D \ge 4 — in particular, decide whether any algorithm asymptotically beats the Move-Only-Outwards bound D−12D-\tfrac{1}{2}, and settle the exact competitive ratio for D=4D=4, known to lie between 33 and 3.53.5. (3) Randomization: determine whether the deterministic and randomized competitive ratios of the infinite-server problem — and of the (h,k)(h,k)-server problem as k/h→∞k/h \to \infty — are separated. These questions share one scientific objective: a structural map of which metric geometries permit competitive online server management with unlimited resources — the analogue, for the infinite-server problem, of the classical dichotomy of the kk-server problem, which depends only on the number of points of the metric space.

References

  1. Christian Coester, Elias Koutsoupias, Philip Lazos. The Infinite Server Problem. ACM Transactions on Algorithms 17(3), Article 20, 1-23, 2021. DOI: 10.1145/3456632, https://doi.org/10.1145/3456632; open-access journal copy: https://ir.cwi.nl/pub/31078/31078.pdf
  2. Christian Coester, Elias Koutsoupias, Philip Lazos. The Infinite Server Problem. arXiv:1702.08474, https://arxiv.org/abs/1702.08474; conference version in Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2017), Article 14, DOI: 10.4230/LIPIcs.ICALP.2017.14, https://doi.org/10.4230/LIPIcs.ICALP.2017.14
  3. Marcin Bienkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż. Unbounded lower bound for k-server against weak adversaries. Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020), pages 1165-1169. DOI: 10.1145/3357713.3384306; arXiv:1911.01592, https://arxiv.org/abs/1911.01592
  4. Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos. The (h,k)-Server Problem on Bounded Depth Trees. ACM Transactions on Algorithms 15(2), Article 28, 2019. DOI: 10.1145/3301314, https://doi.org/10.1145/3301314; conference version in Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 1022-1037, DOI: 10.1137/1.9781611974782.65; arXiv:1608.08527, https://arxiv.org/abs/1608.08527
  5. Sébastien Bubeck, Christian Coester, Yuval Rabani. The Randomized k-Server Conjecture is False!. Proceedings of the 55th ACM Symposium on Theory of Computing (STOC 2023), pages 581-594. DOI: 10.1145/3564246.3585132; arXiv:2211.05753, https://arxiv.org/abs/2211.05753
  6. János Csirik, Csanád Imreh, John Noga, Steve S. Seiden, Gerhard J. Woeginger. Buying a Constant Competitive Ratio for Paging. Proceedings of the 9th Annual European Symposium on Algorithms (ESA 2001), pages 98-108. DOI: 10.1007/3-540-44676-1_8, https://doi.org/10.1007/3-540-44676-1_8
  7. Mark Manasse, Lyle McGeoch, Daniel Sleator. Competitive algorithms for on-line problems. Proceedings of the 20th ACM Symposium on Theory of Computing (STOC 1988), pages 322-333. DOI: 10.1145/62212.62243, https://doi.org/10.1145/62212.62243
  8. Elias Koutsoupias, Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM 42(5):971-983, 1995. DOI: 10.1145/210118.210128, https://doi.org/10.1145/210118.210128
  9. Elias Koutsoupias. Weak adversaries for the k-server problem. Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), pages 444-449. DOI: 10.1109/sffcs.1999.814616, https://doi.org/10.1109/sffcs.1999.814616
  10. Daniel D. Sleator, Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM 28(2):202-208, 1985. DOI: 10.1145/2786.2793, https://doi.org/10.1145/2786.2793
  11. Christian Coester, Elias Koutsoupias. The online k-taxi problem. Proceedings of the 51st ACM Symposium on Theory of Computing (STOC 2019), pages 1136-1147. DOI: 10.1145/3313276.3316370; arXiv:1807.06645, https://arxiv.org/abs/1807.06645
  12. Christian Coester, Tze-Yang Poon. Online 3-Taxi on General Metrics. arXiv:2510.25861, 2025, https://arxiv.org/abs/2510.25861; conference version in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)