  We consider metrical task systems on general metric spaces with $n$ points,
and show that any fully randomized algorithm can be turned into a randomized
algorithm that uses only $2\log n$ random bits, and achieves the same
competitive ratio up to a factor $2$. This provides the first order-optimal
barely random algorithms for metrical task systems, i.e. which use a number of
random bits that does not depend on the number of requests addressed to the
system. We put forward an equivalent view that we call collective metrical task
systems where $k$ agents in a metrical task system team up, and suffer the
average cost paid by each agent. Our results imply that such team can be
$O(\log n^2)$-competitive, as soon as $k\geq n^2$ (in comparison, a single
agent is $\Omega(n)$-competitive at best). We discuss implications on various
aspects of online decision making such as: distributed systems, transaction
costs, and advice complexity, suggesting broad applicability.
