our results are not known to be tight. Improving them may reveal new insight about the power and limitations of the BST model.

In §\[sec2\] we describe our offline BST simulation. In §\[sec3\] we describe our new family of online algorithms. In §\[sec4\] we prove the main applications and further observations.

Offline simulation of multi-finger BSTs (Theorem \[thm: LF simulation\]) {#sec2}
========================================================================

Let $k \in {\mathbb N}$ , let $T$ be a BST on $[n]$, and let $X = (x_1,\dots,x_m) \in [n]^m$ be an access sequence. A $k$-*finger strategy* consists of a sequence $\vec{f} \in [k]^m$ where $f_t \in [k]$ specifies the finger that serves access $x_t$. Let $\vec{\ell} \in [n]^k$ be the [*initial vector*]{}, where $\ell_i \in [n]$ gives the initial location of finger $i$. The cost of strategy $(\vec{f},\vec{\ell})$ is ${\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}}(X) = \sum_{t=1}^m (1+d_T(x_t, x_{\sigma(f_t,t)}))$ where $\sigma(i,t) = \max\{j < t \mid f_j = i\}$ is the location of finger $i$ before time $t$, and $\sigma(i,1) = \ell_i$. Let ${\mbox{\sf F}}^{k}_T(X) = \min_{\vec{f}, \vec{\ell}} {\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}} (X)$. In other words, for a fixed BST $T$ on keyset $[n]$, ${\mbox{\sf F}}^{k}_T(X)$ is the *$k$-server* optimum for serving $X$ in the metric space of the tree $T$. 