The omega failure in the crash-recovery model

Abstract

El diseño y la verificación de algoritmos y aplicaciones distribuidas tolerantes a fallos son tareas complejas. Para estudiarlas, se han identificado varios problemas estándar. Uno de los más importantes es el Consenso, el problema de varios procesos intentando acordar una decisión común. El problema del Consenso no puede ser resuelto determinísticamente en sistemas asíncronos donde los procesos pueden fallar. Para salvar esta imposibilidad, Chandra y Toueg propusieron los detectores no fiables de fallos.

En esta tesis estudiamos, por primera vez, el detector no fiable de fallos Omega en el modelo de sistema de fallo-y-recuperación (Crash-Recovery). Más concretamente nos centramos en el diseño de algoritmos que implementan dicho detector de fallos en modelos de sincronía parcial donde los procesos pueden caer y luego recuperarse, para los que se ha demostrado que el Consenso se puede resolver.

En primer lugar redefinimos el detector de fallos Omega para el modelo de fallo-y-recuperación. Definimos los detectores de fallos Omegacr1 y Omegacr2 para sistemas sin y con memoria estable respectivamente. Seguidamente, proponemos un conjunto de ocho algoritmos distribuidos que funcionan en modelos de sistema de fallo-y-recuperación (ligeramente) diferentes. Respecto a la eficiencia, se han implementado dos algoritmos eficientes en cuanto a comunicación (communication-efficient), uno para Omegacr1 y el otro para Omegacr2.

Además, proponemos dos algoritmos que implementan detectores de fallos Eventually Perfect, <>P. En el modelo de fallo-y-recuperación no es posible implementar un detector de fallos de la clase <>P. Por ello, se han definido e implementado los detectores de fallos <>Pcr y <>Pk-cr, que satisfacen propiedades más débiles. Los algoritmos están basados en el uso de un servicio de elección de líder, que es proporcionado por el detector de fallos Omegacr2. Finalmente, proponemos tres algoritmos de elección de agregador y agregación de datos para redes de sensores inalámbricas, construidos sobre nuestras implementaciones del detector de fallos Omegacr2.