metrics.

Our online BST algorithm relies on an online $k$-server in an almost black box fashion (the metric space underlying the $k$-server instance is induced by a static reference BST). Thus, improvements for $k$-server would directly yield improvements in our bounds. Despite the depth and generality of $k$-server (e.g. it also models the caching/paging problem), to our knowledge it has previously not been related to the BST problem.[^9]

It is known that in an arbitrary metric space with at least $k+1$ points, no deterministic online algorithm may have a competitive ratio better than $k$. In the randomized case the lower bound $\Omega(\log{k}/\log{\log{k}})$ holds, see e.g. [@kserver_survey]. (The lower bounds thus apply for a metric induced by a BST, for all $k<n$.) These results imply a remarkable separation between the $k$-server and BST problems. Dynamic optimality would require, by Theorem \[thm: LF simulation\], a BST cost of $O(\log{k})\cdot {\mbox{\sf F}}^k$. To match this, an online BST may not implicitly perform a deterministic $k$-server execution, since, in that case its overhead would have to be $\Omega{(k)}$. This indicates that improving Theorem \[thm: online simulation\] will likely require tools significantly different from $k$-server, which is surprising, given the similarity of the two formulations.

