Server saturation in skewed networks

Resumen: Consideramos una red de distribución de tareas motivada por sistemas de computación en la nube y redes de distribución de contenido. Hay dos tipos de nodos: despachadores y servidores. Cada despachador recibe tareas de acuerdo a un proceso de Poisson, y debe asignarlas inmediata e irrevocablemente a un servidor. Cada servidor coloca sus tareas en una cola y las procesa en orden de llegada, tardando un tiempo exponencial en cada una. Utilizamos un grafo bipartito para modelar restricciones de compatibilidad entre los despachadores y los servidores, i.e., cada despachador sólo puede enviar tareas a los servidores vecinos en el grafo. En la práctica, las restricciones de compatibilidad surgen por razones geográficas o la indisponibilidad de datos (en el servidor) necesarios para procesar las tareas que llegan a un despachador dado. El proceso que describe cómo evoluciona la cantidad de tareas en cada servidor es una cadena de Markov de tiempo continuo. Definimos estructuras locales en el grafo bipartito que llamamos vecindarios skewed, y probamos que su presencia genera colas largas en estado estacionario. Más precisamente, dada una sucesión de grafos bipartitos con servidores cuyo vecindario es skewed y de tamaño divergente, probamos que la esperanza en estado estacionario del largo de cola de estos servidores tiende a infinito. Informalmente, el vecindario de un servidor es skewed si contiene muchos despachadores cuyo grado en el grafo es bajo. Probamos que los vecindarios skewed aparecen en sucesiones de grafos aleatorios de tamaño divergente.