En la tercera clase de Sistemas Distribuidos del doctorado Sergio Arévalo ha utilizado el artículo Unreliable Failure Detectors for Reliable Distributed Systems (referencia de la publicación en ACM). El objetivo es encontrar un escenario donde utilizando sistemas distribuidos asíncronos (transmisión de mensajes y computación de tareas sin acotación de tiempos) se pueda resolver el problema de consenso.
Para ello se introducen en el sistema distrubuido unos nuevos elementos conocidos como Detectores de Fallos (no fiables). Con su ayuda podremos asegurar que en un sistema asíncrono con Detectores de Fallos, se puede resolver el problema de consenso. La resolución a este problema nos permitirá resolver otros como el radiado atómico, group membership, compromiso atómico y elección de lider (algo que no hemos visto aún hoy).
Los Detectores de Fallos son módulos que se incorporan a cada nodo del sistema distribuido y, tienen como peculiaridad, que se conectan entre sí por un sistema parcialmente síncrono.
El Modelo de Sistema que se plantea para demostrar la resolución del problema de consenso es un Sistema Asíncrono con Detectores de Fallos No Fiables (que se comunican por su red parcialmente síncrona). Existe un conjunto finito de procesos que pueden fallar tipo crash (aún no hemos visto los diferentes tipos de fallos que existen) y que se comunican por canales fiables entre cada par de procesos. Se define un algoritmo en este sistema como el conjunto de los autómatas deterministas, uno por cada proceso. La computación son los pasos que se realizan en el algoritmo que pueden ser: envío, recepción, computación y fallo.
En este Modelo de Sistema se incluye un Detector de Fallos en cada uno de los procesos. Este detector funciona como un servicio que informa a cada nodo de los sospechosos de fallo de los demás nodos (al ser detectores no fiables, hay sospechosos que pueden luego no ser fallos).
El Detector <>P, luego veremos que significa <>P, lo que hace es enviar mensajes de heart-beat a los demás módulos. Tiene unos temporizadores que si vencen antes de recibir respuesta al heart-beat, hacen que el detector marque el nodo como sospechoso de haber fallado. Si luego se recibe la respuesta de heart-beat, se elimina el nodo de la lista de sospechosos y se ajusta el temporizador de ese nodo a un valor mayor. Con este esquema de funcionamiento tarde o temprano se logrará que el valor de los temporizadores sea mayor que la cota del sistema parcialmente síncrono que une a los detectores, y ya no habrá sospechosos que no sean fallos reales.
Sobre los Detectores es fundamental definir dos propiedades que marcan su funcionamiento: completitud (un proceso que falla tarde o temprano sospechamos de él) y precisión (si un proceso no falla tarde o temprano no sospechamos de él). Estas propiedades son complementarias y según como las cumplan un detector, lo clasificaremos de una forma o de otra.
La completitud de un detector puede ser Débil si al fallar un proceso tarde o temprano al menos un proceso correcto sospecha de él, o fuerte si sospechan tarde o temprano del proceso fallido todos los procesos correctos.
Respecto a la precisión, no encontramos con cuatro escenarios: Débil si al menos un proceso correcto no es sospechoso para nadie, Fuerte si todo proceso correcto no es sospechoso para nadie, Débil tarde o temprano y Fuerte tarde o temprano.
De las combinación de las posibiles completitudes y precisiones nos salen 8 posibles Detectores de los que finalmente nos interesan <>P, <>S, <>Q y <>W (competitud fuerte con precisión débil y fuerte tarde o temprano, y completitud débil con precisión débil y fuerte tarde o temprano respectivamente).
Precisión
Fuerte Débil Fuerte ToT Débil ToT
Completitud Fuerte P S <>P <>S
Completitud Débil Q W <>Q <>W
P, Q, S y W son detectores no implementables, por los que son en los otro cuatro en los que nos centraremos. De estos cuatro detectores, vamos a ver que existen ciertas equivalencias entre ellos.
Se dice que un Detector es más fuerte que otro si existe un algoritmo que pueda convertir el detector más fuerte en el más débil. Por definición por ejemplo, P>=Q (es más fuerte). El algortimo sería tan sencillo como seleccionar cualquiera de los procesos correctos que tienen como fallido un proceso sospechosos y tendríamos ya un proceso correcto que sospecha de uno fallido, tal y como pide la completitud débil. Esta misma relación se cumple para: S>=W, <>P>=<>Q, <>S>=<>W. Pero se comprueba también que existen algoritmos de radiado que permiten pasar también de los detectores con completidud débil a detectores con completidud fuerte, por lo que finalmente se dice que hay una relación de equivalencia entre los detectores cuyas relaciones hemos mostrado anteriormente. Es importante indicar que estos algorítmos se ejecutan en el sistema asíncrono.
Como conclusiones de esta clase, comienza a estar muy claro lo que son sistemas síncronos, parcialmente síncronos y asíncronos, de todos los ejemplos que hemos visto en el día de hoy. Vemos como gracias a los detectores de fallos no fiables conectados en un sistema parcialmente síncrono, somos capaces de resolver el problema de consenso en sistemas asíncronos. Un poco de sincronismo en el sistema nos permite pues lograr resultados en los sistemas distribuidos más “salvajes”: los asíncronos.
Eventually consistent failure detectors es un artículo sobre detectores de fallos escrito entre otros por Sergio Arévalo.
