Hispanopedia Wiki
Articulo de referencia

Autoestabilización

La autoestabilización es un concepto de tolerancia a fallos en sistemas distribuidos . Dado cualquier estado inicial, un sistema distribuido autoestabilizador alcanzará un estad...

Hispanopedia WikiContenido en espanolLectura gratuita

La autoestabilización es un concepto de tolerancia a fallos en sistemas distribuidos . Dado cualquier estado inicial, un sistema distribuido autoestabilizador alcanzará 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 tolerancia a fallos más tradicional de los algoritmos, cuyo objetivo es garantizar que el sistema permanezca siempre en un estado correcto ante ciertos tipos de transiciones de estado. Sin embargo, esta 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 corrompido 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 proporciona la capacidad de gestionar fallos no 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 constituye una base esencial para los sistemas informáticos autogestionados y tolerantes a fallos . Como resultado, el artículo de Dijkstra recibió el premio ACM PODC Influential-Paper Award de 2002 , uno de los máximos reconocimientos en la comunidad de computación distribuida. [ 1 ] Además, tras el fallecimiento de Dijkstra, el premio pasó a llamarse Premio Dijkstra.

Historia

En 1974, EW Dijkstra presentó el concepto de autoestabilización, lo que impulsó nuevas investigaciones en este campo. [ 2 ] Su demostración incluyó la presentación de algoritmos de exclusión mutua autoestabilizadores . [ 3 ] También mostró los primeros algoritmos autoestabilizadores que no dependían de supuestos estrictos sobre el sistema. Algunos protocolos anteriores utilizados en la práctica sí se estabilizaban, pero solo asumiendo la existencia de un reloj global para el sistema y un límite superior conocido para la duración de cada transición del sistema. Fue solo diez años después, cuando Leslie Lamport destacó la importancia del trabajo de Dijkstra en una conferencia de 1983 llamada Simposio sobre Principios de Computación Distribuida, que los investigadores [ 4 ] dirigieron su atención a este elegante concepto de tolerancia a fallos. En su discurso, Lamport afirmó:

Considero que este es el trabajo más brillante de Dijkstra, o al menos, su artículo publicado más brillante. Es prácticamente desconocido. Lo considero un hito en el trabajo sobre tolerancia a fallos... Considero que la autoestabilización es un concepto muy importante en la tolerancia a fallos y un campo de investigación muy fértil. [ 3 ]

Posteriormente, el trabajo de Dijkstra fue galardonado con el premio ACM-PODC al artículo influyente, que luego se convirtió en el Premio Dijkstra de Computación Distribuida de la ACM (Association for Computing Machinery), otorgado en el simposio anual de la ACM-PODC. [ 5 ]

Descripción general

Un algoritmo distribuido es autoestabilizador si, partiendo de un estado arbitrario, se garantiza su convergencia a un estado legítimo y su permanencia en un conjunto legítimo de estados a partir de entonces. Un estado es legítimo si, partiendo de este estado, el algoritmo cumple con su especificación. La propiedad de autoestabilización permite que un algoritmo distribuido se recupere de un fallo transitorio, independientemente de su naturaleza. Además, un algoritmo autoestabilizador no necesita 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 " anillo de tokens " — una red de computadoras dispuestas en círculo. En este caso, cada computadora o procesador puede "ver" el estado completo del procesador inmediatamente anterior, y este estado puede implicar que el procesador "tiene un token" o "no lo tiene". [ 5 ] [ 6 ] Uno de los requisitos es que exactamente uno de ellos debe "tener un token" en todo momento. El segundo requisito prescribe que cada nodo "pase el token" a la computadora/procesador que le sigue, de modo que el token finalmente circule por el anillo. [ 5 ] [ 6 ]

  • Que cada ordenador de esta red no posea un token es un estado correcto, ya que otro ordenador puede tenerlo. Sin embargo, si todos los ordenadores se encuentran en el estado de "no poseer un token", entonces la red en su conjunto no está en un estado correcto.
  • De igual modo, si más de una computadora posee un token, esto no representa un estado correcto para la red, aunque no se pueda observar que sea incorrecto al analizar cada computadora individualmente. Dado que cada computadora solo puede observar los estados de sus dos vecinas, les resulta difícil determinar si la red en su conjunto se encuentra en un estado correcto.

Los primeros algoritmos autoestabilizadores no detectaban errores explícitamente para corregirlos posteriormente. En cambio, impulsaban constantemente el sistema hacia un estado legítimo. Dado que los métodos tradicionales para detectar errores [ 7 ] solían ser muy difíciles y lentos, este comportamiento se consideraba 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, intenta determinar si el estado global recopilado es correcto; incluso esa determinación por sí sola puede ser una tarea difícil).

Mejoras en la eficiencia

Más recientemente, los investigadores han presentado métodos más novedosos para la detección de errores ligeros para sistemas autoestabilizadores que utilizan comprobació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 un ordenador de la red se comunique con toda la red para detectar un error ; el error puede detectarse haciendo que cada ordenador se comunique solo con sus vecinos más cercanos. 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 pueden diseñarse por separado. Los algoritmos más recientes 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:

  1. Ejecutar el protocolo no autoestabilizador, al mismo tiempo,
  2. detectar fallos (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. reiniciar el protocolo dado (no autoestabilizador).

La combinación de estas 4 partes es autoestabilizadora (siempre que no haya un desencadenante de falla durante las fases de corrección de fallas, p. ej., [ 11 ] ). Los protocolos autoestabilizadores iniciales también se presentaron en los artículos anteriores. Posteriormente se presentaron protocolos de reinicio más eficientes, p. ej., [ 12 ].

Se introdujo una mayor eficiencia con el concepto de protocolos adaptativos al tiempo. [ 13 ] La idea detrás de estos es que, cuando se produce un número reducido de errores, el tiempo de recuperación puede (y debe) acortarse. Los algoritmos de autoestabilización originales de Dijkstra no poseen esta propiedad.

Una propiedad útil de los algoritmos autoestabilizadores es que pueden estar compuestos de capas si estas no presentan dependencias circulares . El tiempo de estabilización de la composición queda entonces limitado por la suma de los tiempos de estabilización individuales de cada capa. [ 6 ]

Más adelante surgieron nuevos enfoques del trabajo de Dijkstra, como 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 buscaba demostrar el vínculo entre la autoestabilización y la teoría de juegos .

complejidad temporal

La complejidad temporal de un algoritmo autoestabilizador se mide en rondas o ciclos (asíncronos).

  • Una ronda es la secuencia de ejecución más corta en la que cada procesador ejecuta al menos un paso.
  • De manera similar, un ciclo es la secuencia de ejecución más corta en la 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 como visible externamente (la salida ). Ciertos estados de las salidas se definen como correctos (legítimos). Se dice que el conjunto de 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 la salida es el tiempo (el número de rondas (asíncronas) ) hasta que la salida se estabiliza. [ 8 ]

Definición

Un sistema es autoestabilizador si y solo si:

  1. Partiendo de cualquier estado, está garantizado 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 es autoestabilizador aleatorio si y solo si es autoestabilizador y el número esperado de rondas necesarias para alcanzar un estado correcto está acotado por alguna constante.k{\displaystyle k}. [ 15 ]

El diseño de la autoestabilización en el sentido antes mencionado es, como bien se sabe, una tarea compleja. De hecho, una clase de algoritmos distribuidos carece de 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 evidente es el anillo de tokens de Dijkstra, definido anteriormente: ningún proceso puede detectar si el estado de la red es legítimo o no cuando hay más de un token en procesos no vecinos. Esto sugiere que la autoestabilización de un sistema distribuido es una especie de inteligencia colectiva donde cada componente realiza acciones locales, basándose en su conocimiento local, pero que, en última instancia, garantiza la convergencia global.

Para superar la dificultad de diseñar la autoestabilización tal 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 cada estado posible. [ 16 ] 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 la convergencia para cada ejecución.

Un algoritmo autoestabilizador 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. [ 17 ]

Una extensión del concepto de autoestabilización es el de superestabilización . [ 18 ] El objetivo 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, sin garantías hasta que el sistema se haya estabilizado nuevamente. En los sistemas superestabilizadores, existe un predicado de paso que siempre se satisface mientras se reconfigura la topología del sistema.

Una teoría que surgió en el ámbito de la autoestabilización consiste en verificar (de forma distribuida) que el conjunto de estados de los nodos de una red cumple con algún predicado. Esta teoría ha trascendido la autoestabilización y ha dado lugar a conceptos como "NP distribuido" (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 haber impulsado dicha teoría.

Referencias

  1. ↑ "Premio al artículo influyente de PODC: 2002" , Simposio de ACM sobre principios de computación distribuida , consultado el 1 de septiembre de 2009.
  2. ↑ Dijkstra, Edsger W. (1974), "Sistemas autoestabilizadores a pesar del control distribuido" (PDF) , Communications of the ACM , 17 (11): 643–644 , doi : 10.1145/361179.361202 , S2CID 11101426 .
  3. 1 2 Dolev, Shlomi (2000). Autoestabilización . Cambridge, MA: The MIT Press. pág. 3. ISBN  978-0262041782.
  4. ↑ Lamport, Leslie (1985), "Problemas resueltos, problemas sin resolver y no problemas en concurrencia" (PDF) , ACM SIGOPS Operating Systems Review , 19 (4): 34–44 , doi : 10.1145/858336.858339 , S2CID 228819 .
  5. ^ Chaudhuri , Soma ; Das, Samir; Pablo, Himadri; Tirthapura, Srikanta (2007). Computación distribuida y redes: Octava Conferencia Internacional, ICDCN 2006, Guwahati, India, 27 al 30 de diciembre de 2006, Actas . Berlín: Springer. pag. 108.ISBN​  978-3540681397.
  6. 1 2 3 Shlomi Dolev , Shlomo Moran , Amos Israeli: Autoestabilización de sistemas dinámicos asumiendo únicamente atomicidad de lectura/escritura. Computación distribuida, volumen 7, páginas 3-16 (1993).
  7. ↑ Katz, Shmuel; Perry, Kenneth J. (1993), "Extensiones autoestabilizadoras para sistemas de paso de mensajes", Distributed Computing , 7 (1): 17–26 , doi : 10.1007/BF02278852 , S2CID 37245790 .
  8. 1 2 Awerbuch, Baruch ; Patt-Shamir, Boaz; Varghese, George (1991), "Autoestabilización mediante comprobación y corrección local", Actas del 32.º Simposio sobre Fundamentos de la Informática (FOCS) , págs. 268–277 , CiteSeerX 10.1.1.211.8704 , doi : 10.1109/SFCS.1991.185378 , ISBN   978-0-8186-2445-2, S2CID 8320293 .
  9. ↑ Afek, Yehuda ; Kutten, Shay ; Yung, Moti (1997), "El paradigma de detección local y sus aplicaciones a la autoestabilización" , Theoretical Computer Science , 186 ( 1–2 ): 199–229 , doi : 10.1016/S0304-3975(96)00286-1 , MR 1478668 .
  10. ↑ Shlomi Dolev , Yehuda Afek: Estabilizador local. Revista de Computación Paralela y Distribuida, Volumen 62, Número 5, mayo de 2002, Páginas 745-765.
  11. ↑ Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, Shlomi Dolev . Autoestabilización mediante comprobación local y reinicio global. WDAG 1994: 326-339.
  12. ↑ [Baruch Awerbuch, Shay Kutten , Yishay Mansour, Boaz Patt-Shamir, George Varghese. Sincronización autoestabilizadora óptima en el tiempo. ACM STOC 1993: 652-661.]
  13. ↑ Shay Kutten , Boaz Patt-Shamir: Estabilización de protocolos adaptativos en el tiempo. Theor. Comput. Sci. 220(1): 93-111 (1999).
  14. ^ de Bóer, Frank; Bonsangue, Marcello; Rutten, enero (2018). Apto . Cham: Springer. pag. 22.ISBN​  9783319900889.
  15. ↑ Dolev, Shlomi (2000), Autoestabilización , MIT Press , ISBN 978-0-262-04178-2.
  16. ↑ Gouda, Mohamed (1995), El triunfo y la tribulación de la estabilización de sistemas , Actas del 9º taller internacional sobre algoritmos distribuidos..
  17. ↑ Shlomi Dolev , Mohamed G. Gouda y Marco Schneider. Requisitos de memoria para la estabilización silenciosa . En PODC '96: Actas del decimoquinto simposio anual de la ACM sobre principios de computación distribuida , páginas 27-34, Nueva York, NY, EE. UU., 1996. ACM Press. Resumen extendido en línea .
  18. ↑ Dolev, Shlomi ; Herman, Ted (1997), "Protocolos superestabilizadores para sistemas distribuidos dinámicos", Chicago Journal of Theoretical Computer Science , 3 : 1–40 , doi : 10.4086/cjtcs.1997.004, artículo 4.
  • libcircle : una implementación de autoestabilización que utiliza el paso de tokens para la terminación.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Self-stabilization&oldid=1334264528 "