We address the problem of constructing randomized online algorithms for the Metrical Task Systems (MTS) problem on a metric
against an oblivious adversary. Restricting our attention to the class of “work-based” algorithms, we provide a framework for designing algorithms that uses the technique of
. For the case when
is a uniform metric, we exhibit two algorithms that arise from this framework, and we prove a bound on the competitive ratio of each. We show that the second of these algorithms is ln
) competitive, which is the current state-of-the art for the uniform MTS problem.