Thek-server problem is a problem oftheoretical computer science in the category ofonline algorithms, one of two abstract problems onmetric spaces that are central to the theory ofcompetitive analysis (the other beingmetrical task systems). In this problem, an online algorithm must control the movement of a set ofkservers, represented as points in a metric space, and handlerequests 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 andDaniel Sleator (1988).[1] The most prominent open question concerning thek-server problem is the so-calledk-server conjecture, also posed by Manasse et al. This conjecture states that there is an algorithm for solving thek-server problem in an arbitrarymetric space and for any numberk of servers that has competitive ratio exactlyk. Manasse et al. were able to prove their conjecture whenk = 2, and for more general values ofk for some metric spaces restricted to have exactlyk+1 points.Chrobak andLarmore (1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called thepaging problem because it models the problem ofpage replacement algorithms in memory caches, and was also already known to have ak-competitive algorithm (Sleator andTarjan 1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constantk and any metric space, and finally Koutsoupias andPapadimitriou (1995) proved that Work Function Algorithm (WFA) has competitive ratio 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio tok or providing an improved lower bound remains open as of 2014[update]. The most common believed scenario is that the Work Function Algorithm isk-competitive. To this direction, in 2000 Bartal and Koutsoupias showed that this is true for some special cases (if the metric space is a line, a weighted star or any metric ofk+2 points).
Thek-server conjecture has also a version for randomized algorithms, which asks if exists a randomized algorithm with competitive ratio O(logk) in any arbitrary metric space (with at leastk + 1 points).[2] In 2011, a randomized algorithm with competitive bound Õ(log2k log3n) was found.[3][4] In 2017, a randomized algorithm with competitive bound O(log6 k) was announced,[5] but was later retracted.[6] In 2022 it was shown that the randomized version of the conjecture is false.[2][7][8]
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 ak-server problem, the servers are the technicians, sok = 2 and this is a 2-server problem. Washington and Baltimore are 35 miles (56 km) apart, while San Francisco is 3,000 miles (4,800 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 (110 km). After a year of this request pattern, the algorithm will have incurred 20,500 miles (33,000 km) travel: 3,000 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 6,000 miles (9,700 km) of travel once but then avoiding any future travel costs. The competitive ratio of our algorithm on this input is 20,500/6,000 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 both 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 ak-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.Thek-server conjecture states that similar solutions exist for problems with any larger number of technicians.
{{cite conference}}: CS1 maint: date and year (link)