this case, the restriction that $R$ is static is essential.

\[thm: online simulation\] There exists an online randomized BST algorithm whose cost for serving $X \in [n]^m$, is $O\bigl((\log k)^7\bigr) \cdot {\mbox{\sf F}}^{k}(X) + \rho(n)$, for some fixed function $\rho(\cdot)$.

The result can be interpreted as follows. On sufficiently long access sequences, there is an online BST algorithm (in fact, a family of them) competitive with the $k$-finger bound, up to an overhead factor with moderate dependence on $k$. The randomized algorithm (as is standard in the online setting) assumes an oblivious adversary that does not know in advance the outcomes of the algorithm’s random coin-flips. The use of randomness seems essential to our approach. We propose as intriguing open questions to find a deterministic online BST with comparable guarantees and to narrow the gap between the online and offline results.

Due to its substantial amount of computation (outside the BST model), our online algorithm is of theoretical interest only. Nonetheless, the connection with the $k$-server problem allows us to “import” several techniques to the BST problem; some of these, such as the *double coverage* heuristic for $k$-server [@chrobak] are remarkably simple and may find their way to practical BST 