Autoestabilización - Self-stabilization

La autoestabilización es un concepto de tolerancia a fallas en sistemas distribuidos . Dado cualquier estado inicial, un sistema distribuido autoestabilizado terminará en un estado correcto en un número finito de pasos de ejecución .

A primera vista, la garantía de autoestabilización puede parecer menos prometedora que la de los algoritmos de tolerancia a fallos más tradicionales, que tienen como objetivo garantizar que el sistema permanezca siempre en un estado correcto bajo ciertos tipos de transiciones de estado. Sin embargo, esa tolerancia a fallas tradicional no siempre se puede lograr. Por ejemplo, no se puede lograr cuando el sistema se inicia en un estado incorrecto o está dañado por un intruso. Además, debido a su complejidad, es muy difícil depurar y analizar sistemas distribuidos. Por lo tanto, es muy difícil evitar que un sistema distribuido alcance un estado incorrecto. De hecho, algunas formas de autoestabilización se incorporan en muchas redes informáticas y de telecomunicaciones modernas , ya que les da la capacidad de hacer frente a fallas que no estaban previstas en el diseño del algoritmo.

Muchos años después de que el artículo seminal de Edsger Dijkstra en 1974, este concepto sigue siendo importante, ya que presenta una base importante para los sistemas informáticos de autogestión y sistemas de alta disponibilidad . Como resultado, el artículo de Dijkstra recibió el premio ACM PODC Influential-Paper Award 2002 , uno de los más altos reconocimientos en la comunidad de computación distribuida. Además, después de la muerte de Dijkstra, el premio cambió de nombre y ahora se llama Premio Dijkstra.

Historia

EW Dijkstra en 1974 presentó el concepto de autoestabilización, lo que provocó más investigaciones en esta área. Su demostración implicó la presentación de algoritmos de exclusión mutua autoestabilizantes . También mostró los primeros algoritmos de autoestabilización que no se basaban en supuestos sólidos en el sistema. Algunos protocolos anteriores utilizados en la práctica realmente se estabilizaron, pero solo asumiendo la existencia de un reloj que era global para el sistema y asumiendo un límite superior conocido en la duración de cada transición del sistema. Solo diez años después, cuando Leslie Lamport señaló la importancia del trabajo de Dijkstra en una conferencia de 1983 llamada Simposio sobre principios de computación distribuida, los investigadores dirigieron su atención a este elegante concepto de tolerancia a fallas. En su charla, Lamport declaró:

Considero que esta es la obra más brillante de Dijkstra, al menos su artículo publicado más brillante. Es casi completamente desconocido. Considero que es un hito en el trabajo sobre tolerancia a fallas ... Considero que la autoestabilización es un concepto muy importante en la tolerancia a fallas y un campo muy fértil para la investigación.

Posteriormente, el trabajo de Dijkstra fue galardonado con el influyente premio de papel ACM-POPDC, que luego se convirtió en el Premio Dijkstra en Computación Distribuida de ACM (la Asociación de Maquinaria de Computación) otorgado en el simposio anual ACM-POPDC.

Descripción general

Un algoritmo distribuido se autoestabiliza si, a partir de un estado arbitrario, se garantiza que convergerá a un estado legítimo y permanecerá en un conjunto legítimo de estados a partir de entonces. Un estado es legítimo si, a partir de este estado, el algoritmo satisface su especificación. La propiedad de autoestabilización permite que un algoritmo distribuido se recupere de una falla transitoria independientemente de su naturaleza. Además, no es necesario inicializar un algoritmo de autoestabilización, ya que eventualmente comienza a comportarse correctamente independientemente de su estado inicial.

El artículo de Dijkstra, que introduce el concepto de autoestabilización, presenta un ejemplo en el contexto de un "anillo simbólico", una red de computadoras ordenadas en círculo. Aquí, cada computadora o procesador puede "ver" el estado completo de un procesador que lo precede inmediatamente y que este estado puede implicar que el procesador "tiene un token" o que "no tiene un token". Uno de los requisitos es que exactamente uno de ellos debe "tener una ficha" en un momento dado. El segundo requisito prescribe que cada nodo "pasa el token" a la computadora / procesador que lo sucede para que el token finalmente circule por el anillo.

• No tener un token es un estado correcto para cada computadora en esta red, ya que el token puede estar en otro equipo. Sin embargo, si todas las computadoras están en el estado de "no tener un token", entonces la red no está en el estado correcto.
• De manera similar, si más de una computadora "tiene un token", entonces este no es un estado correcto para la red, aunque no se puede observar que sea incorrecto al ver cualquier computadora individualmente. Dado que cada computadora puede "observar" sólo los estados de sus dos vecinos, es difícil para las computadoras decidir si la red en conjunto está en un estado correcto.

Los primeros algoritmos de autoestabilización no detectaron errores explícitamente para posteriormente repararlos. En cambio, empujaron constantemente al sistema hacia un estado legítimo. Dado que los métodos tradicionales para detectar un error a menudo eran muy difíciles y consumían mucho tiempo, se consideró conveniente tal comportamiento. (El método descrito en el documento citado anteriormente recopila una gran cantidad de información de toda la red en un solo lugar; después de eso, intenta determinar si el estado global recopilado es correcto; incluso esa determinación por sí sola puede ser una tarea difícil).

Mejoras de eficiencia

Más recientemente, los investigadores han presentado métodos más nuevos para la detección de errores livianos para sistemas autoestabilizantes mediante verificación local. y para tareas generales.

El término local se refiere a una parte de una red informática. Cuando se utiliza la detección local, no se requiere que una computadora en una red se comunique con toda la red para detectar un error; el error se puede detectar haciendo que cada computadora se comunique solo con sus vecinos más cercanos. Estos métodos de detección local simplificaron considerablemente la tarea de diseñar algoritmos de autoestabilización. Esto se debe a que el mecanismo de detección de errores y el mecanismo de recuperación se pueden diseñar por separado. Los algoritmos más nuevos basados ​​en estos métodos de detección también resultaron ser mucho más eficientes. Además, estos artículos sugirieron transformadores generales bastante eficientes para transformar algoritmos no autoestabilizantes para que se vuelvan autoestabilizantes. La idea es

1. Ejecute el protocolo no autoestabilizador, al mismo tiempo,
2. detectar fallas (durante la ejecución del protocolo dado) utilizando los métodos de detección mencionados anteriormente,
3. luego, aplique un protocolo de "reinicio" (autoestabilizador) para devolver el sistema a un estado inicial predeterminado y, finalmente,
4. reinicie el protocolo dado (no autoestabilizador).

La combinación de estas 4 partes es autoestabilizante (siempre que no haya un disparo de falla durante las fases de corrección de fallas, por ejemplo). Los protocolos iniciales de autoestabilización también se presentaron en los artículos anteriores. Más adelante se presentaron protocolos de reinicio más eficientes, p. Ej.

Se introdujo una eficiencia adicional con la noción de protocolos adaptables al tiempo. La idea detrás de estos es que cuando solo se produce una pequeña cantidad de errores, el tiempo de recuperación puede (y debe) acortarse. Los algoritmos de autoestabilización originales de Dijkstra no tienen esta propiedad.

Una propiedad útil de los algoritmos de autoestabilización es que pueden estar compuestos de capas si las capas no presentan dependencias circulares . El tiempo de estabilización de la composición está entonces limitado por la suma de los tiempos de estabilización individuales de cada capa.

Más tarde surgieron nuevos enfoques del trabajo de Dijkstra, como el caso de Krzysztof Apt y la propuesta de Ehsan Shoja, que demostró cómo la autoestabilización se puede formular de forma natural utilizando los conceptos estándar de los juegos estratégicos, en particular el concepto de una ruta de mejora. Este trabajo en particular buscó demostrar el vínculo entre la autoestabilización y la teoría de juegos.

Complejidad del tiempo

La complejidad temporal de un algoritmo de autoestabilización se mide en rondas o ciclos (asincrónicos).

• Una ronda es el seguimiento de ejecución más corto en el que cada procesador ejecuta al menos un paso.
• De manera similar, un ciclo es el seguimiento de ejecución más corto en el que cada procesador ejecuta al menos una iteración completa de su lista de comandos ejecutados repetidamente.

Para medir el tiempo de estabilización de la salida, se define un subconjunto de las variables de estado para que sean visibles externamente (la salida ). Ciertos estados de salidas se definen como correctos (legítimos). Se dice que el conjunto de las salidas de todos los componentes del sistema se ha estabilizado en el momento en que comienza a ser correcto, siempre que permanezca correcto indefinidamente, a menos que ocurran fallas adicionales. El tiempo de estabilización de salida es el tiempo (el número de rondas (asíncronas) ) hasta que se estabiliza la salida.

Definición

Un sistema se autoestabiliza si y solo si:

1. Partiendo de cualquier estado, se garantiza que el sistema eventualmente alcanzará un estado correcto ( convergencia ).
2. Dado que el sistema está en un estado correcto, se garantiza que permanecerá en un estado correcto, siempre que no ocurra ninguna falla ( cierre ).

Se dice que un sistema se autoestabiliza aleatoriamente si y solo si se autoestabiliza y el número esperado de rondas necesarias para alcanzar un estado correcto está limitado por alguna constante . ${\ Displaystyle k}$

Es bien sabido que el diseño de la autoestabilización en el sentido mencionado anteriormente es un trabajo difícil. De hecho, una clase de algoritmos distribuidos no tiene la propiedad de verificación local: la legitimidad del estado de la red no puede ser evaluada por un solo proceso. El caso más obvio es el token-ring de Dijkstra definido anteriormente: ningún proceso puede detectar si el estado de la red es legítimo o no en el caso de que haya más de un token presente en procesos no vecinos. Esto sugiere que la autoestabilización de un sistema distribuido es una especie de inteligencia colectiva donde cada componente está tomando acciones locales, basadas en su conocimiento local, pero eventualmente esto garantiza la convergencia global al final.

Para ayudar a superar la dificultad de diseñar la autoestabilización como se definió anteriormente, se idearon otros tipos de estabilización. Por ejemplo, la estabilización débil es la propiedad de que un sistema distribuido tiene la posibilidad de alcanzar su comportamiento legítimo desde todos los estados posibles. La estabilización débil es más fácil de diseñar, ya que solo garantiza la posibilidad de convergencia para algunas ejecuciones del sistema distribuido en lugar de convergencia para cada ejecución.

Un algoritmo de autoestabilización es silencioso si y solo si converge a un estado global donde los valores de los registros de comunicación utilizados por el algoritmo permanecen fijos.

Trabajo relacionado

Una extensión del concepto de autoestabilización es el de superestabilización . La intención aquí es hacer frente a sistemas distribuidos dinámicos que sufren cambios topológicos. En la teoría clásica de la autoestabilización, los cambios arbitrarios se ven como errores en los que no se dan garantías hasta que el sistema se ha estabilizado nuevamente. Con los sistemas superestabilizadores, existe un predicado de pasaje que siempre se satisface mientras se reconfigura la topología del sistema.

Referencias

enlaces externos

• libcircle : una implementación de autoestabilización que utiliza el paso de tokens para la terminación.