La superestabilización es un concepto de tolerancia a fallos en la informática distribuida . Los algoritmos distribuidos de superestabilización combinan las características de los algoritmos autoestabilizadores y los algoritmos dinámicos . Un algoritmo de superestabilización, al igual que cualquier otro algoritmo de autoestabilización, puede iniciarse en un estado arbitrario y eventualmente convergerá a un estado legítimo. Además, un algoritmo de superestabilización se recuperará rápidamente de un solo cambio en la topología de la red (agregar o eliminar un borde o nodo en la red).
Cualquier algoritmo de autoestabilización se recupera de un cambio en la topología de la red; la configuración del sistema después de un cambio de topología puede tratarse como cualquier otra configuración inicial arbitraria. Sin embargo, en un algoritmo de autoestabilización, la convergencia después de un solo cambio en la topología de la red puede ser tan lenta como la convergencia de un estado inicial arbitrario. En el estudio de los algoritmos de superestabilización, se presta especial atención al tiempo que lleva recuperarse de un solo cambio en la topología de la red.
Definiciones
El tiempo de estabilización de un algoritmo de superestabilización se define exactamente como en el caso del algoritmo de autoestabilización: cuánto tiempo lleva 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 sincrónica o en ciclos asincrónicos.
El tiempo de superestabilización es el momento de recuperarse de un único cambio de topología. Se supone que el sistema está inicialmente en una configuración legítima. Luego, se cambia la topología de la red; el tiempo de superestabilización es el tiempo máximo que tarda el sistema en volver a alcanzar una configuración legítima. De manera similar, la medida de ajuste es el número máximo de nodos que tienen que cambiar su estado después de tales cambios.
Las "configuraciones casi legítimas" que ocurren después de un cambio de topología pueden modelarse formalmente usando predicados de pasaje : un predicado de pasaje es un predicado que se mantiene después de un solo cambio en la topología de la red, y también durante la convergencia a una configuración legítima.
Referencias
- Dolev, Shlomi ; Herman, Ted (1997), "Protocolos de superestabilización para sistemas distribuidos dinámicos" , Chicago Journal of Theoretical Computer Science, artículo 4.
- Dolev, Shlomi (2000), autoestabilización , MIT Press , ISBN 0-262-04178-2, Sección 7.1.