The Harmonic k-server conjecture: is the Harmonic algorithm $\frac{k(k+1)}{2}$-competitive on every metric space?

A long-standing open problem in online algorithms asks for the exact competitive ratio of the Harmonic algorithm, the natural memoryless randomized algorithm for the $k$-server problem, which serves a request by moving the server at distance $d_i$ with probability proportional to $1/d_i$. The conjecture asserts that Harmonic is $\frac{k(k+1)}{2}$-competitive on every metric space against the adaptive online adversary, matching the known lower bound of $\frac{k(k+1)}{2}$ attained on a uniform metric with one edge contracted to an arbitrarily small length. The best known upper bound, $O(2^k \log k)$, is due to Bartal and Grove (2000) and has not been improved in over 25 years; because Harmonic keeps no state beyond the server positions, proving the conjecture would establish that the memoryless rule attains the optimal quadratic ratio, whereas the polynomial-time polylogarithmic algorithms of Coester and Cosson (2026) maintain a distribution over polynomially many configurations and are not memoryless. The conjecture was restated as open in the source paper (Christou, Fotakis, and Koumoutsos, WAOA 2020), whose own subject is the generalized $k$-server problem on uniform metrics, where memoryless algorithms have a tight $\Theta(k!)$ competitive ratio and Harmonic is the unique optimum. The conjecture remains open as of 2026: the best known upper bound for Harmonic is still $O(2^k \log k)$ (Bartal and Grove, 2000).

Background

The $k$-server problem is a central model of online computation: $k$ mobile servers occupy points of a metric space, a sequence of requests arrives one at a time, each request names a point that must be served immediately by moving some server to it, and the cost is the total distance moved. Because each request must be served before the next is revealed, no online algorithm can match the optimal offline schedule; an online algorithm is called $c$-competitive if its total cost is at most $c$ times the offline optimum on every request sequence, up to an additive constant independent of the sequence. Paging (caching under misses) is exactly the $k$-server problem on a uniform metric, where all distances are equal.

For deterministic algorithms, the classical $k$-server conjecture posits a $k$-competitive algorithm on every metric space; the best known deterministic result is the $(2k-1)$-competitive work-function algorithm of Koutsoupias and Papadimitriou. For randomized algorithms the guarantee depends on the adversary model. An oblivious adversary fixes the whole request sequence in advance, and the algorithm's expected cost is compared with the optimal offline cost of that sequence. An adaptive online adversary chooses each next request using the algorithm's past random behavior while itself serving every request online, and the algorithm's expected cost is compared with the adversary's expected cost; a legal adaptive online adversary may precommit to a fixed request sequence and serve it with the optimal offline schedule (an optimal schedule need only move servers to requested points), so competitiveness against the adaptive online adversary implies the same against an oblivious adversary and is the stronger guarantee. It is the benchmark under which the classical analyses of the algorithm studied here are stated, and the standard one when comparing memoryless algorithms.

A memoryless randomized algorithm decides which server to move based only on the current server positions and the requested point — not on the request history — so it keeps no state beyond the server positions and computes each move instantly. The canonical memoryless algorithm is Harmonic: to serve a request at point $r$ when the servers sit at distances $d_1, \dots, d_k$ from $r$, it moves server $i$ with probability $(1/d_i)/\sum_j (1/d_j)$, that is, with probability inversely proportional to distance. On uniform metrics Harmonic is exactly $k$-competitive. Coppersmith, Doyle, Raghavan, and Snir extended this: on resistive metrics — metrics realizable as electrical networks whose edge resistances give the distances — the random-walk interpretation of Harmonic yields $k$-competitiveness via electrical-network identities, which is optimal among memoryless algorithms. On arbitrary metrics these identities break down. Grove first proved that Harmonic is nonetheless competitive on every metric space, with ratio $O(k \cdot 2^k)$; Bartal and Grove refined the analysis to $O(2^k \log k)$, which remains the best known upper bound more than 25 years later. In the other direction, the best known lower bound on Harmonic's competitive ratio is $\frac{k(k+1)}{2}$: on a uniform metric with a single edge contracted to an arbitrarily small length, Harmonic's ratio approaches $\frac{k(k+1)}{2}$ from below. Upper and lower bounds thus differ by an exponential factor, and the widely repeated conjecture is that the lower-bound value is the truth: Harmonic is $\frac{k(k+1)}{2}$-competitive on every metric space.

The conjecture matters beyond its own statement. Randomized $k$-server algorithms with memory achieve polylogarithmic competitive ratios on general metrics (e.g., $O(\log n \log^2 k)$ via multiscale entropic regularization, Bubeck, Cohen, Lee, Lee, and Madry, 2018; the randomized $k$-server conjecture of polylogarithmic competitiveness was later refuted by an $\Omega(\log^2 k)$ lower bound, Bubeck, Coester, and Rabani, 2023 — a separate conjecture, not the Harmonic one). Those algorithms, however, were implicit or computationally inefficient, maintaining distributions over exponentially many configurations; Coester and Cosson (2026) recently derandomized this line of work, obtaining the first polynomial-time randomized $k$-server algorithm with a polylogarithmic ratio on arbitrary metrics, but their algorithm maintains a distribution over polynomially many server configurations — it is not memoryless. Among memoryless algorithms, Harmonic's exponential bound is still the best known on general metrics: proving the Harmonic conjecture would settle that the natural memoryless rule attains the optimal quadratic ratio while keeping zero state and computing each move instantly.

The conjecture is approached through a neighboring problem. In the generalized $k$-server problem of Koutsoupias and Taylor, the $k$ servers move in $k$ separate metric spaces and a request is a $k$-tuple of points, one per space, each served by the corresponding server. Christou, Fotakis, and Koumoutsos (WAOA 2020) determined the power of memoryless algorithms for the generalized problem on uniform metrics exactly: the competitive ratio is $\Theta(k!)$ — Harmonic achieves $k \cdot \alpha_k$ with $\alpha_k = 1 + (k-1)\alpha_{k-1} = \Theta((k-1)!)$, no memoryless algorithm does better, and Harmonic is the unique optimum. Their introduction restates the classical Harmonic conjecture above as a long-standing open problem that their uniform-metric techniques do not address, and their concluding remarks pose a further, distinct question about memoryless algorithms on other metric families (such as weighted stars), noting that for the weighted and generalized $k$-server problems memoryless algorithms are not competitive on arbitrary metric spaces even for $k=2$ (Chrobak and Sgall; Koutsoupias and Taylor) — a barrier for those variants that does not apply to the classical problem, where Harmonic itself is competitive on every metric space. The conjecture is considered here in its standard formulation.

Problem Statement

Is the Harmonic algorithm $\frac{k(k+1)}{2}$-competitive on every metric space?

In the $k$-server problem, $k$ servers occupy points of a metric space; each request names a point and must be served by moving some server to it at cost equal to the distance moved. The Harmonic algorithm is the memoryless randomized algorithm that, when a request arrives at a point $r$ not occupied by any server (so every server sits at a strictly positive distance $d_i$ from $r$), moves the server currently at distance $d_i$ from $r$ with probability $\frac{1/d_i}{\sum_j 1/d_j}$ (inversely proportional to distance, normalized); a request at an occupied point is served at zero cost. The benchmark is the adaptive online adversary: an adversary that chooses each next request using the algorithm's past random moves while itself serving every request online, and whose own total movement cost is the comparison target. The conjecture asserts that for every $k$, every metric space, and every initial configuration there is a constant $a$ — which may depend on $k$, on the metric space, and on the initial configuration, but not on the adversary's requests — such that for every adaptive online adversary ADV,

$$\mathbb{E}[\mathrm{cost}_{\mathrm{Harmonic}}] \le \frac{k(k+1)}{2} \cdot \mathbb{E}[\mathrm{cost}_{\mathrm{ADV}}] + a.$$

In any single run, only the finitely many points consisting of the initial server positions and the requested points are ever visited; and since a legal adaptive online adversary may precommit to a fixed request sequence $\sigma$ and serve it with the optimal offline schedule, the conjecture implies the weaker oblivious form $\mathbb{E}[\mathrm{cost}_{\mathrm{Harmonic}}(\sigma)] \le \frac{k(k+1)}{2} \cdot \mathrm{OPT}(\sigma) + a$ for every fixed sequence $\sigma$, where $\mathrm{OPT}(\sigma)$ is the cost of an optimal offline service schedule. The conjecture is usually quoted without fixing the adversary model; this record states it in the stronger adaptive-online form, the benchmark of the classical analyses of Harmonic and the standard benchmark in the memoryless-algorithms literature. The conjectured constant is the best possible, since on a uniform metric with one edge contracted to an arbitrarily small length Harmonic's competitive ratio approaches $\frac{k(k+1)}{2}$ from below; the best upper bound currently known is $O(2^k \log k)$ (Bartal and Grove, 2000).

A refutation must exhibit a metric space, a number of servers, and adaptive online adversary strategies whose violation cannot be absorbed by any additive constant: because a single finite request sequence can always be repaired by enlarging $a$, a valid counterexample takes the form of a family of adaptive online adversaries $(\mathrm{ADV}_n)$ on a fixed metric space, fixed $k$, and a fixed initial configuration for which $\mathbb{E}[\mathrm{cost}_{\mathrm{Harmonic}}] - \frac{k(k+1)}{2} \cdot \mathbb{E}[\mathrm{cost}_{\mathrm{ADV}_n}]$ grows without bound; in particular, a family of fixed request sequences $(\sigma_n)$ for which $\mathbb{E}[\mathrm{cost}_{\mathrm{Harmonic}}(\sigma_n)] - \frac{k(k+1)}{2} \cdot \mathrm{OPT}(\sigma_n)$ grows without bound — an asymptotic competitive ratio strictly above $\frac{k(k+1)}{2}$ — suffices, and a family of instances over growing $k$ with ratio $\omega(k^2)$ refutes the quadratic form of the conjecture.

References

1. Dimitris Christou, Dimitris Fotakis, Grigorios Koumoutsos. Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics. In Approximation and Online Algorithms (WAOA 2020), Lecture Notes in Computer Science, vol. 12806, pp. 143-158, 2021. DOI: 10.1007/978-3-030-80879-2_10, https://doi.org/10.1007/978-3-030-80879-2_10; arXiv:2007.08669, https://arxiv.org/abs/2007.08669
2. Yair Bartal, Eddie Grove. The harmonic k-server algorithm is competitive. Journal of the ACM 47(1):1-15, 2000. DOI: 10.1145/331605.331606, https://doi.org/10.1145/331605.331606
3. E. F. Grove. The harmonic online k-server algorithm is competitive. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC 1991), pp. 260-266. DOI: 10.1145/103418.103448, https://doi.org/10.1145/103418.103448
4. Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan. More on random walks, electrical networks, and the harmonic k-server algorithm. Information Processing Letters 84(5):271-276, 2002. DOI: 10.1016/S0020-0190(02)00287-9, https://doi.org/10.1016/S0020-0190(02)00287-9
5. Elias Koutsoupias. The k-server problem. Computer Science Review 3(2):105-118, 2009. DOI: 10.1016/j.cosrev.2009.04.002, https://doi.org/10.1016/j.cosrev.2009.04.002
6. Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir. Random walks on weighted graphs and applications to on-line algorithms. Journal of the ACM 40(3):421-453, 1993. DOI: 10.1145/174130.174131, https://doi.org/10.1145/174130.174131
7. 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
8. Ashish Chiplunkar, Sundar Vishwanathan. Randomized Memoryless Algorithms for the Weighted and the Generalized k-server Problems. ACM Transactions on Algorithms 16(1), Article 14, pp. 14:1-14:28, 2020. DOI: 10.1145/3365002, https://doi.org/10.1145/3365002. Preprint under a different title: On Randomized Memoryless Algorithms for the Weighted k-server Problem. arXiv:1301.0123, https://arxiv.org/abs/1301.0123
9. Marek Chrobak, Jiri Sgall. The weighted 2-server problem. Theoretical Computer Science 324(2-3):289-312, 2004. DOI: 10.1016/j.tcs.2004.05.020, https://doi.org/10.1016/j.tcs.2004.05.020
10. Elias Koutsoupias, David Scot Taylor. The CNN problem and other k-server variants. Theoretical Computer Science 324(2-3):347-359, 2004. DOI: 10.1016/j.tcs.2004.06.002, https://doi.org/10.1016/j.tcs.2004.06.002
11. Nikhil Bansal, Marek Elias, Grigorios Koumoutsos, Jesper Nederlof. Competitive Algorithms for Generalized k-Server in Uniform Metrics. ACM Transactions on Algorithms 19(1), Article 8, pp. 8:1-8:15, 2023 (conference version: SODA 2018, pp. 992-1001). DOI: 10.1145/3568677, https://doi.org/10.1145/3568677
12. Marcin Bienkowski, Lukasz Jez, Pawel Schmidt. Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics. In 30th International Symposium on Algorithms and Computation (ISAAC 2019), Leibniz International Proceedings in Informatics (LIPIcs), pp. 14:1-14:14. arXiv:1810.00580, https://arxiv.org/abs/1810.00580
13. Sebastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee, Aleksander Madry. k-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 3-16. arXiv:1711.01085, https://arxiv.org/abs/1711.01085
14. Sebastien Bubeck, Christian Coester, Yuval Rabani. The Randomized k-Server Conjecture is False! In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pp. 581-594. arXiv:2211.05753, https://arxiv.org/abs/2211.05753
15. Christian Coester, Romain Cosson. Randomized k-server in polynomial time. In International Colloquium on Automata, Languages and Programming (ICALP 2026), Leibniz International Proceedings in Informatics (LIPIcs), pp. 65:1-65:20, 2026. arXiv:2605.01497, https://arxiv.org/abs/2605.01497
16. Nikhil Ayyadevara, Ashish Chiplunkar. The Randomized Competitive Ratio of Weighted k-server is at least Exponential. In 29th Annual European Symposium on Algorithms (ESA 2021), LIPIcs vol. 204, pp. 9:1-9:11. arXiv:2102.11119, https://arxiv.org/abs/2102.11119
17. Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma. A Decomposition Approach to the Weighted k-server Problem. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024), Leibniz International Proceedings in Informatics (LIPIcs), pp. 6:1-6:17. arXiv:2410.06485, https://arxiv.org/abs/2410.06485
18. Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar. Weighted k-Server Admits an Exponentially Competitive Algorithm. In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pp. 4188-4208. arXiv:2507.12130, https://arxiv.org/abs/2507.12130
19. Junhao Gan, Xiao Sun, Seeun William Umboh. Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems. arXiv:2607.07098, 2026, https://arxiv.org/abs/2607.07098