Barely Random Algorithms and Collective Metrical Task Systems

Many online algorithms, such as those for the k-server problem or metrical task systems, rely on randomness for their optimal performance. However, generating random bits can be expensive and may not be feasible in all environments such as distributed systems. This paper tackles this problem by exploring ‘barely random algorithms’: algorithms that use a minimal amount of randomness while achieving near-optimal performance. This is especially important for resource-constrained environments, where generating random bits might be difficult.

The authors develop barely random algorithms for metrical task systems. They demonstrate that any fully randomized algorithm can be made barely random by using only 2log n random bits while maintaining competitiveness. Their approach hinges on a novel framework called ‘collective metrical task systems’, where multiple agents collaborate. This framework elegantly connects barely random algorithms with the resource-efficient aspect of collective algorithms. The research shows that a team of agents can achieve a competitive ratio significantly better than that of a single agent, underscoring the potential benefits of collaboration in solving online problems.