Problema del servidor k

Problema sin resolver en informática

Hay una${\displaystyle k}$-algoritmo competitivo para resolver el${\displaystyle k}$¿Problema del servidor en un espacio métrico arbitrario?

Más problemas sin resolver en informática

El problema de los k servidores es un problema de la informática teórica perteneciente a la categoría de algoritmos en línea , uno de los dos problemas abstractos sobre espacios métricos fundamentales para la teoría del análisis competitivo (el otro son los sistemas de tareas métricas ). En este problema, un algoritmo en línea debe controlar el movimiento de un conjunto de k servidores , representados como puntos en un espacio métrico, y gestionar las solicitudes, que también se representan como puntos en dicho espacio. A medida que llega cada solicitud, el algoritmo debe determinar qué servidor mover al punto solicitado. El objetivo del algoritmo es minimizar la distancia total recorrida por todos los servidores, en comparación con la distancia total que un adversario óptimo, conociendo de antemano toda la secuencia de solicitudes, podría haber recorrido.

El problema fue planteado por primera vez por Mark Manasse, Lyle A. McGeoch y Daniel Sleator (1988). ^{[ 1 ]} La pregunta abierta más destacada sobre el problema de k servidores es la llamada conjetura de k servidores, también planteada por Manasse et al. Esta conjetura afirma que existe un algoritmo para resolver el problema de k servidores en un espacio métrico arbitrario y para cualquier número k de servidores que tiene una razón competitiva exactamente k . Manasse et al. pudieron demostrar su conjetura cuando k = 2, y para valores más generales de k para algunos espacios métricos restringidos a tener exactamente k +1 puntos. Marek Chrobak y Lawrence L. Larmore (1991) demostraron la conjetura para métricas de árbol. El caso especial de métricas en las que todas las distancias son iguales se llama problema de paginación porque modela el problema de los algoritmos de reemplazo de páginas en cachés de memoria, y también se sabía que tenía un algoritmo k -competitivo ( Sleator y Tarjan 1985). Fiat et al. (1990) demostraron por primera vez que existe un algoritmo con razón competitiva finita para cualquier constante k y cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) demostraron que el Algoritmo de Función de Trabajo (WFA) tiene una razón competitiva de 2 k - 1. Sin embargo, a pesar de los esfuerzos de muchos otros investigadores, reducir la razón competitiva a k o proporcionar una cota inferior mejorada sigue siendo un problema abierto a fecha de 2014.El escenario más comúnmente aceptado es que el algoritmo de la función de trabajo es k -competitivo. En este sentido, en el año 2000 Bartal y Koutsoupias demostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica de k + 2 puntos).

La conjetura del k -servidor también tiene una versión para algoritmos aleatorios , que pregunta si existe un algoritmo aleatorio con razón competitiva O(log k ) en cualquier espacio métrico arbitrario (con al menos k + 1 puntos). ^{[ 2 ]} En 2011, se encontró un algoritmo aleatorio con límite competitivo Õ(log ² k log ^{3 n). [ 3 ] [ 4 ]} En 2017, se anunció un algoritmo aleatorio con límite competitivo O(log ^{6 k), [ 5 ]} pero posteriormente fue retractado. ^{[ 6 ]} En 2022 se demostró que la versión aleatoria de la conjetura es falsa. ^{[ 2 ] [ 7 ] [ 8 ]}

Para concretar el problema, imaginemos que enviamos técnicos de soporte a los clientes cuando tienen problemas con sus equipos. En nuestro ejemplo, hay dos técnicos, Mary y Noah, que atienden a tres clientes en San Francisco, California; Washington, D.C.; y Baltimore, Maryland. Como se trata de un problema de k servidores, los servidores son los técnicos, por lo que k = 2 y es un problema de 2 servidores. Washington y Baltimore están a 56 km (35 millas ) de distancia, mientras que San Francisco está a 4800 km (3000 millas) de ambas, e inicialmente Mary y Noah se encuentran en 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 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.

The k-server problem is also useful in an offline setting, that is, when the sequence of requests is completely known. For examples, for some algorithms the sequence of memory accesses is independent of the input (an example is matrix multiplication), and so the paging problem can be solved offline. This problem has been shown to be solvable in polynomial time.^[9]

• Chrobak, Marek ; Larmore, Lawrence L. (1991). "Un algoritmo óptimo en línea para K -servidores en árboles". SIAM Journal on Computing . 20 (1): 144– 148. CiteSeerX 10.1.1.53.2395 . doi : 10.1137/0220008 . 

• Chrobak, Marek ; Karloff, Howard ; Payne, Tom ; Vishwnathan, Sundar (1991). "Nuevos resultados sobre problemas de servidores". SIAM Journal on Discrete Mathematics . 4 (2): 172– 181. doi : 10.1137/0404017 .

• Fiat, A.; Rabani, Y.; Ravid, Y. (1990). " Algoritmos competitivos de k -servidores". Actas del 31.er Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 454–463 . 

• Koutsoupias, Elias; Papadimitriou, Christos H. (1995). "Sobre la conjetura del k -servidor". Journal of the ACM . 42 (5): 971– 983. doi : 10.1145/210118.210128 . S2CID 5813837 . 

• Manasse, Mark; McGeoch, Lyle A.; Sleator, Daniel D. (1990). "Algoritmos competitivos para problemas de servidores". Journal of Algorithms . 11 (2): 208– 230. doi : 10.1016/0196-6774(90)90003-W .

• Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Eficiencia amortizada de las reglas de actualización y paginación de listas" . Communications of the ACM . 28 (2): 202– 208. doi : 10.1145/2786.2793 . S2CID 2494305 .