Parametrized Metrical Task Systems

Sébastien Bubeck, Yuval Rabani

Abstract: We consider parametrized versions of metrical task systems and metrical service systems, two fundamental models of online computing, where the constrained parameter is the number of possible distinct requests $m$. Such parametrization occurs naturally in a wide range of applications. Striking examples are certain power management problems, which are modeled as metrical task systems with $m=2$. We characterize the competitive ratio in terms of the parameter $m$ for both deterministic and randomized algorithms on hierarchically separated trees. Our findings uncover a rich and unexpected picture that differs substantially from what is known or conjectured about the unparametrized versions of these problems. For metrical task systems, we show that deterministic algorithms do not exhibit any asymptotic gain beyond one-level trees (namely, uniform metric spaces), whereas randomized algorithms do not exhibit any asymptotic gain even for one-level trees. In contrast, the special case of metrical service systems (subset chasing) behaves very differently. Both deterministic and randomized algorithms exhibit gain, for $m$ sufficiently small compared to $n$, for any number of levels. Most significantly, they exhibit a large gain for uniform metric spaces and a smaller gain for two-level trees. Moreover, it turns out that in these cases (as well as in the case of metrical task systems for uniform metric spaces with $m$ being an absolute constant), deterministic algorithms are essentially as powerful as randomized algorithms. This is surprising and runs counter to the ubiquitous intuition/conjecture that, for most problems that can be modeled as metrical task systems, the randomized competitive ratio is polylogarithmic in the deterministic competitive ratio.

1. Introduction

In online computing, an algorithm must make decisions about its state (e.g., which server is active, which memory page is loaded) without knowing future requests. The Metrical Task System (MTS) is a grand unified model for such problems. In a standard MTS, an algorithm manages $n$ states, and each request specifies a cost for being in each state. The goal is to minimize the sum of service costs and transition costs.

Historically, researchers assumed that any request was possible. However, in real-world applications like power management, there might only be a few types of requests (e.g., "high demand" or "low demand"). This paper investigates the Parametrized MTS, asking: if there are only $m$ distinct possible requests, how does the competitive ratio change?

2. Methodology

The authors employ a theoretical approach centered on Hierarchically Separated Trees (HSTs). HSTs are a standard mathematical tool used to approximate complex metric spaces by representing them as trees where distances increase rapidly toward the root. The analysis focuses on:

  • One-level HSTs: Uniform metric spaces where the distance between any two distinct states is constant.
  • Two-level HSTs: "Paired-uniform" structures where states are grouped into pairs.
  • Metrical Service Systems (MSS): A special case of MTS (subset chasing) where state costs are binary (0 or $\infty$).

The study uses the minimax principle for lower bounds and variants of the marking algorithm for upper bounds.

3. Key Insights and Results

The results reveal a stark contrast between simple and complex metric spaces, and between the MTS and MSS models.

3.1 The Uniform Exception and the Collapse of Benefits

In simple uniform metric spaces (1-level HSTs), limiting the number of request types $m$ makes deterministic algorithms significantly more powerful—nearly as efficient as randomized ones. However, for general MTS, this advantage vanishes almost immediately as the metric space complexity increases. In a two-level tree, even with only $m=2$ possible requests, a deterministic algorithm's performance is no better than if there were infinite request types.

3.2 Refuting Folklore Conjectures

A long-standing "folklore conjecture" suggests that for most MTS problems, the best randomized algorithm is exponentially better (polylogarithmic) than the best deterministic one. This work provides a counterexample: for $m=2$ in uniform spaces, both ratios are $\Theta(\log n)$.

3.3 MSS vs. MTS

Unlike general MTS, Metrical Service Systems (MSS) benefit from having few request types across all levels of tree metrics. In these cases, the competitive ratio becomes a function of $m$ rather than $n$, provided $n$ is sufficiently large.

Competitive ratios for 1-level HSTs (uniform metric spaces).
Competitive ratios for 2-level HSTs (paired-uniform metric spaces).

4. Conclusion and Future Work

For MTS, parametrization by $m$ only offers asymptotic gains in the simplest of spaces. For MSS, it provides a massive gain, making complexity independent of the total number of states $n$.

Future research directions include establishing tight bounds for trees with three or more levels and exploring specific metrics like the "real line" or "weighted stars." Additionally, the concept of "leaky randomization"—how much information an adversary needs to force a randomized algorithm to perform as poorly as a deterministic one—presents a promising information-theoretic frontier for online algorithms.

Summary updated

Abstract

We consider parametrized versions of metrical task systems and metrical service systems, two fundamental models of online computing, where the constrained parameter is the number of possible distinct requests $m$. Such parametrization occurs naturally in a wide range of applications. Striking examples are certain power management problems, which are modeled as metrical task systems with $m=2$. We characterize the competitive ratio in terms of the parameter $m$ for both deterministic and randomized algorithms on hierarchically separated trees. Our findings uncover a rich and unexpected picture that differs substantially from what is known or conjectured about the unparametrized versions of these problems. For metrical task systems, we show that deterministic algorithms do not exhibit any asymptotic gain beyond one-level trees (namely, uniform metric spaces), whereas randomized algorithms do not exhibit any asymptotic gain even for one-level trees. In contrast, the special case of metrical service systems (subset chasing) behaves very differently. Both deterministic and randomized algorithms exhibit gain, for $m$ sufficiently small compared to $n$, for any number of levels. Most significantly, they exhibit a large gain for uniform metric spaces and a smaller gain for two-level trees. Moreover, it turns out that in these cases (as well as in the case of metrical task systems for uniform metric spaces with $m$ being an absolute constant), deterministic algorithms are essentially as powerful as randomized algorithms. This is surprising and runs counter to the ubiquitous intuition/conjecture that, for most problems that can be modeled as metrical task systems, the randomized competitive ratio is polylogarithmic in the deterministic competitive ratio.
BibTeX
@inproceedings{bubeck2020parametrized,
  author = {Sébastien Bubeck and Yuval Rabani},
  title = {{Parametrized Metrical Task Systems}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  doi = {10.4230/lipics.approx/random.2020.54},
}
Figure