K-server problem
Encyclopedia
The k-server problem is a problem of theoretical computer science
in the category of online algorithm
s, one of two abstract problems on metric space
s that are central to the theory of competitive analysis
(the other being metrical task systems
). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.
The problem was first posed by Mark Manasse, Lyle A. McGeoch and Daniel Sleator
(1990). The most prominent open question concerning the k-server problem is the so-called k-server conjecture, also posed by Manasse et al. This conjecture states that there is an algorithm for solving the k-server problem in an arbitrary metric space
and for any number k of servers that has competitive ratio at most k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k when the metric space is restricted to have exactly k+1 points. Chrobak
and Larmore
(1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called the paging problem because it models the problem of page replacement algorithm
s in memory caches, and was also already known to have a k-competitive algorithm (Sleator
and Tarjan
1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constant k and any metric space, and finally Koutsoupias and Papadimitriou
(1995) proved a competitive ratio of 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio to k or providing an improved lower bound remains open .
Consider an algorithm for assigning servers to requests that always assigns the closest server to the request, and suppose that each weekday morning the customer in Washington needs assistance while each weekday afternoon the customer in Baltimore needs assistance, and that the customer in San Francisco never needs assistance. Then, our algorithm will assign one of the servers (say Mary) to the Washington area, after which she will always be the closest server and always be assigned to all customer requests. Thus, every day our algorithm incurs the cost of traveling between Washington and Baltimore and back, 70 miles (112.7 km). After a year of this request pattern, the algorithm will have incurred 20500 miles (32,991.5 km) travel: 3000 to send Mary to the East Coast, and 17,500 for the trips between Washington and Baltimore. On the other hand, an optimal adversary who knows the future request schedule could have sent both Mary and Noah to Washington and Baltimore respectively, paying 6000 miles (9,656 km) of travel once but then avoiding any future travel costs. The competitive ratio of our algorithm on this input is 20,500/6000 or approximately 3.4, and by adjusting the parameters of this example the competitive ratio of this algorithm can be made arbitrarily large.
Thus we see that always assigning the closest server can be far from optimal. On the other hand, it seems foolish for an algorithm that does not know future requests to send one of its technicians away from San Francisco, as the next request could be in that city and it would have to send someone back immediately. So it seems that it is difficult or impossible for a k-server algorithm to perform well relative to its adversary. However, for the 2-server problem there exists an algorithm that always has a total travel distance of at most twice the adversary's distance.
The k-server conjecture states that similar solutions exist for problems with any larger number of technicians.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
in the category of 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...
s, one of two abstract problems on 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...
s that are central to the theory of 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...
(the other being metrical task systems
Metrical task systems
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 this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.
The problem was first posed by Mark Manasse, Lyle A. McGeoch and Daniel Sleator
Daniel Sleator
Daniel Dominic Kaplan Sleator is a professor of computer science at Carnegie Mellon University. He discovered amortized analysis and he invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. He also pioneered the theory of link grammars and developed...
(1990). The most prominent open question concerning the k-server problem is the so-called k-server conjecture, also posed by Manasse et al. This conjecture states that there is an algorithm for solving the k-server problem in an arbitrary 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...
and for any number k of servers that has competitive ratio at most k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k when the metric space is restricted to have exactly k+1 points. Chrobak
Marek Chrobak
Marek Chrobak is a full professor at University of California, Riverside. He is known for his work competitive analysis of online algorithms, particularly for the k-server problem. His contributions, with his co-author Lawrence L...
and Larmore
Lawrence L. Larmore
Professor Lawrence L. Larmore is a theoretical computer scientist, and a professor at University of Nevada Las Vegas. He is best known for his work with competitive analysis of online algorithms, particularly for the k-server problem. His contributions, with his co-author Marek Chrobak, led to the...
(1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called the paging problem because it models the problem of 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...
s in memory caches, and was also already known to have a k-competitive algorithm (Sleator
Daniel Sleator
Daniel Dominic Kaplan Sleator is a professor of computer science at Carnegie Mellon University. He discovered amortized analysis and he invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. He also pioneered the theory of link grammars and developed...
and Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constant k and any metric space, and finally Koutsoupias and Papadimitriou
Christos Papadimitriou
Christos Harilaos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, United States...
(1995) proved a competitive ratio of 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio to k or providing an improved lower bound remains open .
Example
To make the problem more concrete, imagine sending customer support technicians to customers when they have trouble with their equipment. In our example problem there are two technicians, Mary and Noah, serving three customers, in San Francisco, California, Washington, DC, and Baltimore, Maryland. As a k-server problem, the servers are the technicians, so k = 2 and this is a 2-server problem. Washington and Baltimore are 35 miles (56.3 km) apart, while San Francisco is 3000 miles (4,828 km) away from both, and initially Mary and Noah are both in San Francisco.Consider an algorithm for assigning servers to requests that always assigns the closest server to the request, and suppose that each weekday morning the customer in Washington needs assistance while each weekday afternoon the customer in Baltimore needs assistance, and that the customer in San Francisco never needs assistance. Then, our algorithm will assign one of the servers (say Mary) to the Washington area, after which she will always be the closest server and always be assigned to all customer requests. Thus, every day our algorithm incurs the cost of traveling between Washington and Baltimore and back, 70 miles (112.7 km). After a year of this request pattern, the algorithm will have incurred 20500 miles (32,991.5 km) travel: 3000 to send Mary to the East Coast, and 17,500 for the trips between Washington and Baltimore. On the other hand, an optimal adversary who knows the future request schedule could have sent both Mary and Noah to Washington and Baltimore respectively, paying 6000 miles (9,656 km) of travel once but then avoiding any future travel costs. The competitive ratio of our algorithm on this input is 20,500/6000 or approximately 3.4, and by adjusting the parameters of this example the competitive ratio of this algorithm can be made arbitrarily large.
Thus we see that always assigning the closest server can be far from optimal. On the other hand, it seems foolish for an algorithm that does not know future requests to send one of its technicians away from San Francisco, as the next request could be in that city and it would have to send someone back immediately. So it seems that it is difficult or impossible for a k-server algorithm to perform well relative to its adversary. However, for the 2-server problem there exists an algorithm that always has a total travel distance of at most twice the adversary's distance.
The k-server conjecture states that similar solutions exist for problems with any larger number of technicians.