In this work we study the k-Server problem. In this problem, we have k

servers on a metric space that must attend a sequence of requests with

the goal of minimizing the total distance moved by the servers. We

dedicate special attention to the k-server conjecture: any metric

space allows for a k-competitive k-server algorithm. This is one of

the most important open problems in online computing.

The work function algorithm, proposed by Chrobak and Larmore, is very

relevant to the conjecture. It has been proved that this algorithm is

k-competitive for several special cases of the k-server problem.

Furthermore, most researchers believe that the algorithm is indeed

k-competitive for any metric space. Thus, a deeper understanding of

this algorithm plays a special role in this work.

To analyze the work function algorithm, we use many auxiliary results

developed by several authors. In this work we tried to present a

collection of these results in a concise way. From this, we present a

proof of Koutsoupias and Papadimitriou's theorem: the work function

algorithm is (2k-1)-competitive for any metric space. This is the

most important result related to the k-server problem. Moreover, we

show that the k-server conjecture holds in some special cases.