Título: Gestión de Memoria Eficiente en Paxos Generalizado.

Director: Alexey Gotsman.

Co-Director: Sebastián Uchitel.

Jurados: Hernan Melgratti, Gisela Confalonieri.

Resumen:
Los protocolos de Replicación de Máquinas de Estado (RME) permiten a ciertas
aplicaciones (bajo fuertes garantías de consistencia) alcanzar tolerancia a fallos,
alta disponibilidad y un rendimiento escalable al replicar su estado en un contexto
distribuido. Como consecuencia, esto suele conducir a un crecimiento ilimitado del
estado del sistema, que requiere ser periódicamente truncado mediante la
“recolección de basura” de información obsoleta o desactualizada.
Los mecanismos de manejo de memoria son críticos para la aplicabilidad
práctica de estos protocolos pero son raramente formalizados, a pesar de requerir
modificaciones sustanciales a nivel del algoritmo. Como consecuencia, su
implementación permanece poco clara y errores en el manejo de memoria pueden
terminar comprometiendo la correctitud del protocolo a nivel general.

Los enfoques clásicos para el manejo de memoria se basan en el hecho de que
los logs de las réplicas se encuentran totalmente ordenados. Sin embargo,
las implementaciones de RME pueden ser considerablemente optimizadas al
aprovechar la conmutatividad de los comandos. Esta idea clave ha conducido al
desarrollo de una familia entera de protocolos de orden parcial, incluyendo el
reconocido protocolo de Paxos Generalizado, en el cual esta tesis se enfoca
principalmente. Desafortunadamente, las técnicas de recolección de basura
clásicas no son aplicables en este contexto, ya que estos protocolos mantienen
logs ordenados tan solo parcialmente. A pesar de que se han propuesto nuevas
soluciones para abordar este problema, las mismas conllevan desventajas significativas
de rendimiento ya que dependen de la introducción de checkpoints en el sistema que
interrumpen completamente la ejecución normal del protocolo. Más aún, los detalles
de implementación de estas técnicas y pruebas formales de su correctitud no han sido
publicados hasta el momento.

En esta tesis realizamos varias contribuciones para abordar estos problemas. En primer lugar,
definimos formalmente y demostramos rigurosamente una implementación para mecanismos de
checkpointing siguiendo las técnicas estándar que consideramos de bajo rendimiento.
En segundo lugar, proponemos un mecanismo innovador para recolección de basura en
protocolos de orden parcial que es capaz de realizar la gestión de memoria en paralelo
con la ejecución normal del algoritmo, sin degradar su rendimiento. Esta nueva técnica,
que se basa en un novedoso tipo de checkpoint cuyas dependencias son decididas en tiempo
de ejecución, es igualmente formalizada y demostrada correcta en este trabajo.