La autoestabilización es un concepto de tolerancia a fallos en sistemas distribuidos . Dado un estado inicial, un sistema distribuido autoestabilizado llegará a 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 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 es 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 fallos que no se previeron en el diseño del algoritmo.
Muchos años después del artículo seminal 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 de 2002 , uno de los mayores reconocimientos en la comunidad de computación distribuida. [1] Además, después de la muerte de Dijkstra, el premio cambió de nombre y ahora se llama Premio Dijkstra.
En 1974, EW Dijkstra presentó el concepto de autoestabilización, lo que dio pie a nuevas 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 autoestabilizadores que no dependían de suposiciones sólidas sobre el sistema. Algunos protocolos anteriores utilizados en la práctica sí se estabilizaban, pero sólo suponiendo la existencia de un reloj que era global para el sistema y suponiendo un límite superior conocido para 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 Symposium on Principles of Distributed Computing , los investigadores [4] dirigieron su atención a este elegante concepto de tolerancia a fallos. En su charla, Lamport afirmó:
Considero que este 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 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. [3]
Posteriormente, el trabajo de Dijkstra fue galardonado con el premio ACM-PODC al artículo más influyente, que luego se convirtió en el Premio Dijkstra en Computación Distribuida de la ACM (Asociación para Maquinaria Computacional), otorgado en el simposio anual ACM-PODC. [5]
Un algoritmo distribuido es autoestabilizador 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, un algoritmo autoestabilizador no tiene que inicializarse 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 ordenadores ordenados en un círculo. Aquí, cada ordenador 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 "pasa el token" al ordenador/procesador que lo sucede para que el token finalmente circule por el anillo. [5] [6]
Los primeros algoritmos de autoestabilización no detectaban errores explícitamente para luego repararlos, sino que empujaban constantemente el 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, se consideró deseable este comportamiento. (El método descrito en el artículo citado anteriormente recopila una enorme 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 de peso ligero para sistemas autoestabilizadores utilizando 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 de 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 vecinas más cercanas. Estos métodos de detección local simplificaron considerablemente la tarea de diseñar algoritmos autoestabilizadores. 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] ). Los protocolos de autoestabilización iniciales también se presentaron en los artículos anteriores. Protocolos de reinicio más eficientes se presentaron más tarde, por ejemplo, [12]
Se introdujo una mayor eficiencia con el concepto de protocolos adaptables al tiempo. [13] La idea detrás de estos protocolos es que cuando se produce una pequeña cantidad de errores, el tiempo de recuperación puede (y debe) ser breve. Los algoritmos de autoestabilización originales de Dijkstra no tienen esta propiedad.
Una propiedad útil de los algoritmos autoestabilizadores es que pueden estar compuestos de capas si las capas no presentan ninguna dependencia circular . 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]
Posteriormente 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 las variables de estado como visibles externamente (la salida ). Se definen ciertos estados de salida 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 se mantenga correcto indefinidamente, a menos que se produzcan fallos adicionales. El tiempo de estabilización de la 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 solo si es autoestabilizador y el número esperado de rondas necesarias para alcanzar un estado correcto está limitado por alguna constante . [15]
Se sabe 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 único 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 en 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 toma acciones locales, en función de su conocimiento local, pero eventualmente esto garantiza la convergencia global al final.
Para ayudar a superar la dificultad de diseñar la autoestabilización definida 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 cada estado posible. [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 la de superestabilización . [18] La intención aquí es abordar sistemas distribuidos dinámicos que experimentan cambios topológicos. En la teoría clásica de 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 sistemas superestabilizadores, hay un predicado de paso que siempre se satisface mientras se reconfigura la topología del sistema.
Una teoría que comenzó en el área de la autoestabilización es la que verifica (de manera distribuida) que la colección de estados de los nodos de una red obedece a algún predicado. Esa teoría ha crecido más allá de la autoestabilización y ha dado lugar a nociones como "NP distribuida" (una versión distribuida de NP (complejidad) ), Conocimiento Cero distribuido (una versión distribuida de Conocimiento Cero ), etc. El Premio a la Innovación en Computación Distribuida del Coloquio Internacional sobre Complejidad Estructural de la Información y la Comunicación (SIRROCO) de 2024 se otorgó por iniciar esa teoría.
