Autoestabilização
Autoestabilização é uma propriedade de sistemas distribuídos em que, a partir dum estado qualquer, sempre se chega num estado correto com um número finito de passos de execução. Essa abordagem contrasta com a visão típica dum algoritmo tolerante a falhas, que garante que o sistema nunca sairá dum estado correto. A capacidade de se recuperar sem intervenção externa é bastante desejável em redes de computadores ou de telecomunicações, pois as permite reparar erros e retornar ao estado normal de operação por conta própria. Computadores e redes podem ser feitos tolerantes a falhas.
Apesar de deixar claro que a convergência a um estado correto ocorre numa quantidade finita de passos, a auto-estabilização não define em quanto tempo isso ocorre, o que acarreta preocupações com a complexidade da convergência. A complexidade em tempo dum algoritmo auto-estabilizável é mensurada em rodadas (ciclos), o menor caminho de execução em que cada processador executa pelo menos um passo. Os primeiro algoritmos auto-estabilizáveis não detectavam erros explicitamente para então repará-los; eles tentavam constantemente levar o sistema a um estado legítimo.
Edsger Dijkstra apresentou em 1974 o primeiro algoritmo auto-estabilizável,[1] promovendo pesquisas posteriores nessa área. O conceito está presente na fundação de sistemas auto-gerenciáveis.