Metrical task systems are abstract models for competitive analysis of online computation. Metrical task systems play roles in online problems such as paging

Page replacement algorithm

In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated...

, list accessing, and the k-server problem

K-server problem

The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis...

 (in finite spaces). Metrical task systems were formulated by Borodin

Allan Borodin

Allan Bertram Borodin is a University of Toronto professor whose research is in computational complexity theory and algorithms.He has co-authored papers with some of the best researchers in computer science including his longtime friend and colleague Turing Award winner Stephen Cook...

, Linial, and Saks.

General description

In general terms, a metrical task system consists of a metric space

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...

 with a metric

Metric (mathematics)

In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...

 and a transition table. These are used to represent all possible configurations.

See also

• Adversary model
  Adversary (online algorithm)
  In computer science, an online algorithm measures its competitiveness against different adversary models. For deterministic algorithms, the adversary is the same, the adaptive offline adversary...
  
  
• Competitive analysis
  Competitive analysis (online algorithm)
  Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...
  
  
• K-server problem
  K-server problem
  The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis...
  
  
• Online algorithm
  Online algorithm
  In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
  
  
• Page replacement algorithm
  Page replacement algorithm
  In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated...
  
  
• Real-time computing
  Real-time computing
  In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...