known, we could conclude part (1) by running an arbitrary *online* $k$-server algorithm defined on tree metrics.

To this end, we mention two online $k$-server algorithms, the deterministic “double coverage” algorithm of Chrobak and Larmore [@chrobak] (Algorithm A) and the very recently announced randomized algorithm of Lee [@Lee; @Bubeck] (Algorithm B). It is known that the cost of Algorithms A, resp. B is at most $k$-times, resp. $O((\log{k})^{6})$ times ${\mbox{\sf F}}^k$. We only describe Algorithm A, as it is particularly intuitive. To obtain the claimed result, we need the much more complex Algorithm B. (By using Algorithm A we get an overall factor $O(k \log{k})$.)

During the execution of Algorithm A, given a current access request $x_t$, call those servers (fingers) *active*, whose path to $x_t$ in $T$ does not contain another server. If several servers are in the same location, one of them is chosen arbitrarily to be active. Algorithm A serves $x_t$ as follows: as long as there is no server on $x_t$, move all active servers one step closer to $x_t$. Observe that as servers move, some of them may become inactive. Algorithm A (as described) may need to move multiple servers during one access. It can, 