(Note that the tree is unweighted, and the distance $d_T(\cdot,\cdot)$ counts the number of edges between two nodes in $T$.) We define ${\mbox{\sf F}}^{k}(X) = \min_T {\mbox{\sf F}}^{k}_{T}(X)$. It is clear form the definition that ${\mbox{\sf F}}^{1}(X) \geq {\mbox{\sf F}}^{2}(X) \geq \cdots \geq {\mbox{\sf F}}^{n}(X) = m$ for all $X$.

Observe that we implicitly assume that during every access at most one server moves. In addition, we may assume that if some server is already placed at the requested node, then no movement happens. Algorithms with these two restrictions are called *lazy*. As argued in the $k$-server literature (see e.g. [@kserver_survey]), non-lazy server movements can always be postponed to a later time, keeping track of the “virtual” locations of servers. In other words, every $k$-server algorithm can be simulated by a lazy algorithm, without additional cost. We therefore assume throughout the paper that $k$-server/$k$-finger executions are lazy.

Consider some (lazy) $k$-finger execution $(\vec{f},\vec{\ell})$ in tree $T$, for access sequence $X$. We can view $\vec{f}$ as an explicit sequence of elementary steps ${\ensuremath{\mathcal S}}= {\ensuremath{\mathcal S}}^k_{T, \vec{f}, \vec{\ell}}$, where in each step we move one of the fingers to its parent or to one of its children in $T$. We further 