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 la autoestabilización puede parecer menos prometedora que la de los algoritmos más tradicionales de tolerancia a fallos, cuyo objetivo es garantizar que el sistema siempre permanezca en un estado correcto bajo ciertos tipos de transiciones de estado. Sin embargo, esa tolerancia a fallos 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 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 fallos que no estaban previstos en el diseño del algoritmo.
Muchos años después del artículo fundamental de Edsger Dijkstra en 1974, este concepto sigue siendo importante ya que presenta una base importante para los sistemas informáticos autogestionados y los sistemas tolerantes a fallos . Como resultado, el artículo de Dijkstra recibió el premio ACM PODC Influential-Paper Award 2002 , uno de los mayores reconocimientos en la comunidad de informática distribuida. [1] Además, después de la muerte de Dijkstra, el premio cambió de nombre y ahora se llama Premio Dijkstra.
EW Dijkstra presentó en 1974 el concepto de autoestabilización, lo que impulsó más investigaciones en esta área. [2] Su demostración implicó la presentación de algoritmos de exclusión mutua autoestabilizadores . [3] También mostró los primeros algoritmos de autoestabilización que no se basaban en suposiciones sólidas sobre el sistema. Algunos protocolos anteriores utilizados en la práctica en realidad se estabilizaron, pero solo suponiendo la existencia de un reloj global para el sistema y un límite superior conocido en la duración de cada transición del sistema. Sólo 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 [4] dirigieron su atención a este elegante concepto de tolerancia a fallos. En su charla, Lamport afirmó:
Considero que éste es el trabajo más brillante de Dijkstra; al menos, su artículo publicado más brillante. Es casi completamente desconocido. Lo considero un hito en el trabajo sobre la tolerancia a fallos... Considero que la autoestabilización es un concepto muy importante en la tolerancia a fallos y un campo muy fértil para la investigación. [3]
Posteriormente, el trabajo de Dijkstra recibió el premio al artículo influyente ACM-PODC, que luego se convirtió en el Premio Dijkstra en Computación Distribuida de ACM (la Asociación para Maquinaria de Computación) otorgado en el simposio anual de ACM-PODC. [5]
Un algoritmo distribuido se autoestabiliza si, partiendo 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 ese 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 autoestabilizador, 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 "token ring", 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 "no tiene un token". [5] [6] Uno de los requisitos es que exactamente uno de ellos debe "tener un token" en un momento dado. El segundo requisito prescribe que cada nodo "pase el token" a la computadora/procesador que le sucede para que el token finalmente circule por el anillo. [5] [6]
Los primeros algoritmos de autoestabilización no detectaban errores de forma explícita para posteriormente repararlos. En cambio, empujaron constantemente al sistema hacia un estado legítimo. Dado que los métodos tradicionales para detectar un error [7] eran a menudo muy difíciles y consumían mucho tiempo, este comportamiento se consideró deseable. (El método descrito en el artículo 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).
Más recientemente, los investigadores han presentado métodos más nuevos para la detección de errores livianos en sistemas autoestabilizadores mediante verificación local. [8] [9] y para tareas generales. [10]
El término local se refiere a una parte de una red informática. Cuando se utiliza la detección local, no es necesario 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 autoestabilizadores en autoestabilizadores. La idea es,
La combinación de estas 4 partes es autoestabilizante (siempre que no haya un desencadenante de falla durante las fases de corrección de falla, por ejemplo, [11] ). En los artículos anteriores también se presentaron los protocolos iniciales de autoestabilización. Posteriormente se presentaron protocolos de reinicio más eficientes, por ejemplo, [12]
Se introdujo una eficiencia adicional con la noción de protocolos de adaptación temporal. [13] La idea detrás de esto es que cuando solo ocurre 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 exhiben 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. [6]
Más tarde surgieron nuevos enfoques del trabajo de Dijkstra, como el caso de la propuesta de Krzysztof Apt y Ehsan Shoja, que demostró cómo la autoestabilización puede formularse de forma natural utilizando los conceptos estándar de los juegos estratégicos, en particular el concepto de camino de mejora. [14] Este trabajo en particular buscó demostrar el vínculo entre la autoestabilización y la teoría de juegos.
La complejidad temporal de un algoritmo autoestabilizador se mide en rondas o ciclos (asincrónicos).
Para medir el tiempo de estabilización de la salida, se define un subconjunto de variables de estado para que sean visibles externamente (la salida ). Ciertos estados de resultados 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 empieza a ser correcto, siempre que se mantenga correcto indefinidamente, salvo que se produzcan fallos adicionales. El tiempo de estabilización de salida es el tiempo (el número de rondas (asincrónicas) ) hasta que la salida se estabiliza. [8]
Un sistema es autoestabilizador si y sólo si:
Se dice que un sistema es autoestabilizador aleatorio si y sólo si es autoestabilizante y el número esperado de rondas necesarias para alcanzar un estado correcto está limitado por alguna constante . [15]
Es bien sabido que el diseño de la autoestabilización en el sentido antes mencionado es una tarea 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 evaluarse mediante 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 más de un token esté presente en procesos no vecinos. Esto sugiere que la autoestabilización de un sistema distribuido es una especie de inteligencia colectiva en la que cada componente toma acciones locales, basándose en su conocimiento local, pero, en última instancia, esto garantiza la convergencia global al final.
Para ayudar a superar la dificultad de diseñar la autoestabilización como se define 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. [16] La estabilización débil es más fácil de diseñar ya que simplemente garantiza una posibilidad de convergencia para algunas ejecuciones del sistema distribuido en lugar de convergencia para cada ejecución.
Un algoritmo autoestabilizador es silencioso si y sólo si converge a un estado global donde los valores de los registros de comunicación utilizados por el algoritmo permanecen fijos. [17]
Una extensión del concepto de autoestabilización es el de superestabilización . [18] 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 consideran errores en los que no se dan garantías hasta que el sistema se haya estabilizado nuevamente. Con los sistemas superestabilizadores, hay un predicado de paso que siempre se satisface mientras se reconfigura la topología del sistema.
Una Teoría que comenzó dentro del área de la autoestabilización es la de verificar (de manera distribuida) que el conjunto de los estados de los nodos en una red obedece a algún predicado. Esa teoría ha ido más allá de la autoestabilización y ha llevado a nociones como "NP distribuido" (una versión distribuida de NP (complejidad) ), Conocimiento Cero distribuido (una versión distribuida de Conocimiento Cero ), etc. El Coloquio Internacional sobre Información Estructural y Por iniciar esa teoría se otorgó el Premio Communication Complexity (SIRROCO) a la Innovación en Computación Distribuida de 2024.
