##
**Competitive algorithms for server problems.**
*(English)*
Zbl 0705.68023

Summary: The k-server problem is that of planning the motion of k mobile servers on the vertices of a graph under a sequence of requests for service. Each request consists of the name of a vertex, and is satisfied by placing a server at the requested vertex. The requests must be satisfied in their order of occurrence. The cost of satisfying a sequence of requests is the distance moved by the servers. We study on-line algorithms for this problem from the competitive point of view. That is, we seek to develop on-line algorithms whose performance on any sequence of requests is as close as possible to the performance of the optimum off-line algorithm. We obtain optimally competitive algorithms for several important cases. Because of the flexibility in choosing the distances in the graph and the number of servers, the k-server problem can be used to model a number of important paging and caching problems. It can also be used as a building block for solving more general problems. We show how server algorithms can be used to solve a seemingly more general class of problems known as task systems.

### MSC:

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

68R10 | Graph theory (including graph drawing) in computer science |

90B35 | Deterministic scheduling theory in operations research |

68W10 | Parallel algorithms in computer science |