Algoritmos de consistencia rápida orientados por la demanda en sistemas distribuidos de gran escala

Résumé

La Internet actual nos ofrece grandes oportunidades, pero también enormes retos. Uno de ellos es el desarrollo de sistemas de grandes dimensiones, de alto desempeño, tolerantes a los cambios, fallos y retardos impredecibles que ocurren en Internet. Una herramienta para tratar con este reto es la replicación de consistencia débil. Los algoritmos de replicación los podemos clasificar en consistencia fuerte y consistencia débil. La consistencia fuerte asegura que todas las réplicas mantengan exactamente el mismo contenido. Cuando un cliente accede a una réplica para hacer una escritura, todo el sistema se bloquea, el cliente sólo recibe una respuesta hasta que la escritura ha terminado y ha sido propagaada a todas las réplicas del sistema. Los algoritmos de consistencia débil solo garantizan que en un tiempo finito pero no acotado el sistema será consistente. Cuando un cliente accede a una réplica para hacer una escritura, el cliente inmediatamente recibe una respuesta, y la escritura se propaga a todas las réplicas del sistema posteriormente. El volumen de demanda de un servicio en cada nodo de un sistema distribuido de enorme escala suele ser muy desigual; como en muchas otras redes sociales, la actividad, interés o participación está distribuida por toda la red, en muchos casos siguiendo la ley de Zipf. Esto genera una distribución geográfica de la demanda con zonas de alta demanda y zonas de baja demanda. Sin embargo, los algoritmos de consistencia débil anteriores no tienen en cuenta la demanda. Por tanto mi tesis es que los algoritmos de replicación de consistencia débil deben propagar los cambios de manera preferencial a los nodos con mayor demanda, para que mayor cantidad de clientes accedan a contenidos frescos en menor cantidad de tiempo. En esta tesis se propone Fast consistency (FC), un nuevo algoritmo distribuido de consistencia débil que desarrollamos a partir del algoritmo Time-Stamped Anti-Entropy (T