  We study the randomized k-server problem on metric spaces consisting of
widely separated subspaces. We give a method which extends existing algorithms
to larger spaces with the growth rate of the competitive quotients being at
most O(log k). This method yields o(k)-competitive algorithms solving the
randomized k-server problem, for some special underlying metric spaces, e.g.
HSTs of "small" height (but unbounded degree). HSTs are important tools for
probabilistic approximation of metric spaces.
