  In this paper, we settle the randomized $k$-sever conjecture for the
following metric spaces: line, circle, Hierarchically well-separated tree
(HST). Specially, we show that there are $O(\log k)$-competitive randomized
$k$-sever algorithms for above metric spaces. For any general metric space with
$n$ points, we show that there is an $O( \log k \log n)$-competitive randomized
$k$-sever algorithm.

Data Structures and Algorithms