![](http://image.absoluteastronomy.com/images//topicimages/noimage.gif)
Metrical task systems
Encyclopedia
Metrical task systems are abstract models for competitive analysis of online computation. Metrical task systems play roles in online problems such as paging
, list accessing, and the k-server problem
(in finite spaces). Metrical task systems were formulated by Borodin
, Linial, and Saks.
with a metric
and a transition table. These are used to represent all possible configurations.
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 spaceMetric 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 modelAdversary (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 analysisCompetitive 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 problemK-server problemThe 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 algorithmOnline algorithmIn 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 algorithmPage replacement algorithmIn 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 computingReal-time computingIn 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...