Seminario de estudiantes

Muchas aplicaciones utilizan grandes cantidades de servidores alojados en la nube. Los usuarios de una aplicación generan tareas que deben ser distribuidas y ejecutadas por los servidores a medida que llegan al sistema. Un problema de load balancing consiste en determinar cómo deben distribuirse las tareas entre los servidores para minimizar el tiempo promedio que las tareas permanecen pendientes. Estos problemas son desafiantes porque muchas veces deben resolverse con información parcial y respetando restricciones de compatibilidad entre tareas y servidores.

En la práctica, los tiempos entre arribos y de ejecución de las tareas son aleatorios, por lo que el vector que describe la cantidad de tareas en cada servidor es un proceso estocástico. Para simplificar el análisis, se asume que estos tiempos tienen distribución exponencial y se obtiene una cadena de Markov de tiempo continuo. Resultados clásicos sobre load balancing se basan en obtener el límite fluido de este proceso cuando la cantidad de servidores y la tasa de arribos de las tareas tienden a infinito proporcionalmente. Este límite es una ley de grandes números funcional que permite aproximar el comportamiento del proceso por la solución de un sistema infinito de ecuaciones diferenciales. Cuando existen restricciones de compatibilidad no siempre es posible probar límites fluidos y por lo tanto debe recurrirse a otras técnicas.

La charla intentará ser autocontenida y hará énfasis en la intuición por encima de los detalles técnicos. En primer lugar, hablaremos brevemente sobre cadenas de Markov de tiempo continuo y un par de modelos básicos de teoría de colas. Luego, presentaremos algunos resultados clásicos sobre load balancing basados en límites fluidos. Por último, hablaremos de load balancing con restricciones de compatibilidad dadas por un grafo.

En la teoría de juegos clásica, los jugadores eligen acciones con el objetivo de maximizar su beneficio, sin conocer la estrategia del otro jugador. En la teoría de juegos de código abierto, en cambio, cada jugador está representado por un programa que puede inspeccionar el código de los demás antes de decidir qué hacer.

Esta modificación aparentemente sencilla cambia de manera profunda el comportamiento de juegos clásicos como el dilema del prisionero. En particular, aparecen estrategias capaces de condicionar su cooperación a la existencia de demostraciones formales sobre el comportamiento del oponente.

En esta charla introduciremos este modelo a partir del dilema del prisionero y estudiaremos varios ejemplos de estrategias, sus ventajas y desventajas, y como interactúan entre ellas. La explicación de este fenómeno involucra autorreferencia, demostrabilidad y una teoremas de la lógica matemática.

El objetivo será mostrar cómo ideas elementales de teoría de juegos, computación y lógica se combinan para producir comportamientos inesperados y dar lugar a una familia de problemas todavía abiertos.