may again require $O(\log{k})$ operations to fix, i.e. property (2). Any efficient balancing strategy (e.g. red-black tree) may be used.

Online simulation of multi-finger BSTs (Theorem \[thm: online simulation\]) {#sec3}
===========================================================================

Consider the optimal (offline) $k$-finger execution $\vec{f}$ for access sequence $X \in [n]^m$, with static reference tree $T$ and initial finger-placement $\vec{\ell}$. We wish to simulate it by a dynamic *online* BST. The construction proceeds in two stages: (1) A simulation of $\vec{f}$ by a sequence ${\ensuremath{\mathcal S}}$ of steps that describe finger-movements and rotations-at-fingers, starting from an arbitrary BST $T_0$ and arbitrary finger locations $\vec{\ell}_0$. The sequence ${\ensuremath{\mathcal S}}$ is *online*, i.e. it is constructed without knowledge of the optimal initial state $T$,$\vec{\ell}$, and it correctly serves the sequence $X$, as its elements are revealed one-by-one. (2) A step-by-step simulation of ${\ensuremath{\mathcal S}}$ by a standard BST algorithm using the result of §\[sec2\]. Since ${\ensuremath{\mathcal S}}$ is online, the BST algorithm is also online.

As before, we denote by ${\mbox{\sf F}}^k(X) = {\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}}(X)$ the cost of the optimal offline execution. Observe that this is exactly the $k$-server optimum with the tree metric defined by $T$ and initial configuration of servers $\vec{\ell}$. If $T$ and $\vec{\ell}$ were 