these bounds (up to a constant factor). However, any online BST (such as Splay or Greedy) must also match the dependence of $O(\log k)$ in the upper bound of $O(\log k) \cdot F^{k}(X)$, in order to be constant-competitive.

##### Techniques. The $k$-server problem. {#techniques.-the-k-server-problem. .unnumbered}

The $k$-server problem, introduced by Manasse, McGeoch, and Sleator [@Manasse] in 1988 is a central problem in online algorithms: Is there an online deterministic strategy for serving a sequence of requests by moving $k$ servers around, with a total movement cost at most $k$ times the optimal offline strategy? The question in its original form, for arbitrary metric spaces, remains open. Nonetheless, the problem has inspired a wealth of results and a rich set of techniques, many of which have found applications outside the $k$-server problem. A full survey is out of our scope, we refer instead to some prominent results [@Fiat; @Koutsoupias; @Seiden; @Raghavan; @Bartal; @Bansal], and the surveys [@Borodin §10, §11], [@kserver_survey]. Most relevantly for us, Chrobak and Larmore [@chrobak] gave in 1991, an intuitive, deterministic, $k$-competitive algorithm for *tree metrics*, and the very recently announced breakthrough of Lee [@Lee], building on Bubeck et al. [@Bubeck], gives an $O\bigl((\log{k})^6\bigr)$-competitive randomized algorithm for arbitrary 