El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de análisis competitivo (el otro es sistemas de tarea métrica). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera de peticiones.
El problema fue presentado por Mark Manasse, Lyle Un. McGeoch Y Daniel Sleator (1990). La cuestión abierta más prominente respecto del problema k-server es la llamada cojetura k-server, también presentado por Manasse, McGeoch y Sleator. Esta conjetura declara que hay un algoritmo para solucionar el problema k-server en un espacio métrico arbitrario y para cualquier número k de servidores que tiene proporción competitiva al menos k. Manasse, McGeoch y Sleator fueron capaces de probar su conjetura cuando k = 2, y para valores más generales de k cuando el espacio métrico está restringido para tener exactamente k+1 puntos. Chrobak y Larmore (1991) probaron la conjetura para la métrica (norma) de árbol.  El caso especial de métrica (norma) en que todas distancias son iguales es llamado el problema de paginación porque modela el problema de algoritmos de sustitución de página en cachés de memoria, y era también ya sabido tener un algoritmo k-competitivo (Sleator y Tarjan 1985). Manasse, McGeoch y Sleator (1990) probaron que existe un algoritmo con proporción competitiva finita para cualquier constante k y cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) probaron que el algoritmo Work Function (WFA) tiene proporción competitiva 2k - 1. Aun así, a pesar de los esfuerzos de muchos otros investigadores, reduciendo la proporción competitiva a k o proporcionando una cota inferior mejorada, se mantiene aun abierto. El escenario creído más común es que el WFA es k-competitivo. Respecto a esto, en el año 2000 Bartal y Koutsoupias mostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica (norma) de k+2 puntos).
En 2011, se encontró un algoritmo aleatorio de costo Õ(log2k log3n).[1]​