Superestabilización

La superestabilización es un concepto de tolerancia a fallos en la computación distribuida . Los algoritmos distribuidos superestabilizadores combinan las características de los algoritmos autoestabilizadores y los algoritmos dinámicos . Un algoritmo superestabilizador, al igual que cualquier otro algoritmo autoestabilizador, puede iniciarse en un estado arbitrario y, finalmente, convergerá a un estado válido. Además, un algoritmo superestabilizador se recupera rápidamente de un único cambio en la topología de la red (añadir o eliminar una arista o un nodo).

Cualquier algoritmo autoestabilizador se recupera de un cambio en la topología de la red; la configuración del sistema tras dicho cambio puede tratarse como cualquier otra configuración inicial arbitraria. Sin embargo, en un algoritmo autoestabilizador, la convergencia tras un único cambio en la topología de la red puede ser tan lenta como la convergencia desde un estado inicial arbitrario. En el estudio de los algoritmos superestabilizadores, se presta especial atención al tiempo necesario para recuperarse de un único cambio en la topología de la red.

El tiempo de estabilización de un algoritmo superestabilizador se define exactamente igual que en el caso de un algoritmo autoestabilizador: el tiempo que tarda en converger a un estado legítimo desde una configuración arbitraria. Dependiendo del modelo computacional, el tiempo se mide, por ejemplo, en rondas de comunicación síncronas o en ciclos asíncronos.

El tiempo de superestabilización es el tiempo necesario para recuperarse de un único cambio de topología. Se supone que el sistema se encuentra inicialmente en una configuración legítima. Posteriormente, se modifica la topología de la red; el tiempo de superestabilización es el tiempo máximo que tarda el sistema en alcanzar nuevamente una configuración legítima. De manera similar, la medida de ajuste es el número máximo de nodos que deben cambiar su estado tras dichos cambios.

Las "configuraciones casi legítimas" que se producen tras un cambio de topología pueden modelarse formalmente mediante el uso de predicados de paso : un predicado de paso es un predicado que se cumple tras un único cambio en la topología de la red, y también durante la convergencia a una configuración legítima.

• 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.
• Dolev, Shlomi (2000), Autoestabilización , MIT Press , ISBN 0-262-04178-2, Sección 7.1.