Task systems are mathematical objects used to model the set of possible configurations of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states.
If the cost function to change states is a metric, the task system is a metrical task system (MTS). This is the most common type of task systems.
Metrical task systems generalize online problems such as paging, list accessing, and the k-server problem (in finite spaces).
Formal definition.
A task system is a pair formula_1 where formula_2 is a set of states and formula_3 is a distance function. If formula_4 is a metric, formula_1 is a metrical task system. An input to the task system is a sequence formula_6 such that for each formula_7, formula_8 is a vector of formula_9 non-negative entries that determine the processing costs for the formula_9 states when processing the formula_7th task.
An algorithm for the task system produces a schedule formula_12 that determines the sequence of states. For instance, formula_13 means that the formula_7th task formula_8 is run in state formula_16. The processing cost of a schedule is
formula_17
The objective of the algorithm is to find a schedule such that the cost is minimized.
Known results.
As usual for online problems, the most common measure to analyze algorithms for metrical task systems is the competitive analysis, where the performance of an online algorithm is compared to the performance of an optimal offline algorithm. For deterministic online algorithms, there is a tight bound formula_18 on the competitive ratio due to Borodin et al. (1992).
For randomized online algorithms, the competitive ratio is lower bounded by formula_19 and upper bounded by formula_20. The lower bound is due to Bartal et al. (2006, 2005). The upper bound is due to Bubeck, Cohen, Lee and Lee (2018) who improved upon a result of Fiat and Mendel (2003).
There are many results for various types of restricted metrics.