Autoestabilização - Self-stabilization

Autoestabilização é um conceito de tolerância a falhas em sistemas distribuídos . Dado qualquer estado inicial, um sistema distribuído autoestabilizado terminará em um estado correto em um número finito de etapas de execução .

À primeira vista, a garantia de autoestabilização pode parecer menos promissora do que a dos algoritmos de tolerância a falhas mais tradicionais, que visam garantir que o sistema sempre permaneça em um estado correto sob certos tipos de transições de estado. No entanto, essa tolerância a falhas tradicional nem sempre pode ser alcançada. Por exemplo, não pode ser alcançado quando o sistema é iniciado em um estado incorreto ou corrompido por um intruso. Além disso, devido à sua complexidade, é muito difícil depurar e analisar sistemas distribuídos. Conseqüentemente, é muito difícil evitar que um sistema distribuído atinja um estado incorreto. De fato, algumas formas de autoestabilização são incorporadas em muitas redes modernas de computadores e telecomunicações , uma vez que lhes dá a capacidade de lidar com falhas que não foram previstas no projeto do algoritmo.

Muitos anos depois que o papel seminal de Edsger Dijkstra em 1974, este conceito continua a ser importante, uma vez que apresenta uma base importante para sistemas de computador auto-gestão e sistemas tolerantes a falhas . Como resultado, o artigo de Dijkstra recebeu o Prêmio ACM PODC Influential-Paper de 2002 , um dos maiores reconhecimentos na comunidade de computação distribuída. Além disso, após a morte de Dijkstra, o prêmio foi renomeado e agora é chamado de Prêmio Dijkstra.

História

EW Dijkstra em 1974 apresentou o conceito de autoestabilização, o que levou a pesquisas adicionais nesta área. Sua demonstração envolveu a apresentação de algoritmos de exclusão mútua auto-estabilizantes . Ele também mostrou os primeiros algoritmos de autoestabilização que não dependiam de suposições fortes sobre o sistema. Alguns protocolos anteriores usados ​​na prática realmente se estabilizaram, mas apenas assumindo a existência de um relógio que era global para o sistema e assumindo um limite superior conhecido na duração de cada transição do sistema. Foi apenas dez anos depois, quando Leslie Lamport apontou a importância do trabalho de Dijkstra em uma conferência de 1983 chamada Simpósio sobre Princípios de Computação Distribuída, que os pesquisadores voltaram sua atenção para este elegante conceito de tolerância a falhas. Em sua palestra, Lamport afirmou:

Considero este o trabalho mais brilhante de Dijkstra - pelo menos, seu artigo publicado mais brilhante. É quase completamente desconhecido. Considero isso um marco no trabalho sobre tolerância a falhas ... Considero a autoestabilização um conceito muito importante em tolerância a falhas e um campo muito fértil para pesquisa.

Posteriormente, o trabalho de Dijkstra foi premiado com o influente prêmio de papel ACM-POPDC, que então se tornou o Prêmio Dijkstra de Computação Distribuída da ACM (a Association for computing Machinery) dado no simpósio anual ACM-POPDC.

Visão geral

Um algoritmo distribuído é autoestabilizado se, partindo de um estado arbitrário, ele convergirá para um estado legítimo e permanecerá em um conjunto legítimo de estados daí em diante. Um estado é legítimo se, a partir desse estado, o algoritmo satisfaz sua especificação. A propriedade de autoestabilização permite que um algoritmo distribuído se recupere de uma falha transitória, independentemente de sua natureza. Além disso, um algoritmo de autoestabilização não precisa ser inicializado, pois eventualmente começa a se comportar corretamente, independentemente de seu estado inicial.

O artigo de Dijkstra, que introduz o conceito de autoestabilização, apresenta um exemplo no contexto de um "token ring" - uma rede de computadores ordenados em um círculo. Aqui, cada computador ou processador pode "ver" todo o estado de um processador que o precede imediatamente e que esse estado pode implicar que o processador "tem um token" ou "não tem um token". Um dos requisitos é que exatamente um deles deve "manter um token" a qualquer momento. O segundo requisito prescreve que cada nó "passe o token" para o computador / processador que o sucede, de modo que o token eventualmente circule no anel.

• Não reter um token é um estado correto para cada computador nesta rede, uma vez que o token pode ser mantido por outro computador. No entanto, se todos os computadores estiverem no estado "não segurando um token", a rede não está em um estado correto.
• Da mesma forma, se mais de um computador "mantém um token", então este não é um estado correto para a rede, embora não possa ser considerado incorreto visualizando qualquer computador individualmente. Como cada computador pode "observar" apenas os estados de seus dois vizinhos, é difícil para os computadores decidir se a rede está em um estado correto.

Os primeiros algoritmos de autoestabilização não detectavam erros explicitamente para repará-los posteriormente. Em vez disso, eles empurraram constantemente o sistema para um estado legítimo. Como os métodos tradicionais de detecção de erros costumavam ser muito difíceis e demorados, esse comportamento era considerado desejável. (O método descrito no artigo citado acima coleta uma grande quantidade de informações de toda a rede para um lugar; depois disso, ele tenta determinar se o estado global coletado está correto; mesmo essa determinação sozinha pode ser uma tarefa difícil).

Melhorias de eficiência

Mais recentemente, os pesquisadores apresentaram métodos mais novos para detecção de erros leves para sistemas auto-estabilizantes usando verificação local. e para tarefas gerais.

O termo local se refere a uma parte de uma rede de computadores. Quando a detecção local é usada, um computador em uma rede não precisa se comunicar com toda a rede para detectar um erro - o erro pode ser detectado fazendo com que cada computador se comunique apenas com seus vizinhos mais próximos. Esses métodos de detecção local simplificaram consideravelmente a tarefa de projetar algoritmos de autoestabilização. Isso ocorre porque o mecanismo de detecção de erros e o mecanismo de recuperação podem ser projetados separadamente. Algoritmos mais novos baseados nesses métodos de detecção também se mostraram muito mais eficientes. Além disso, esses artigos sugeriram transformadores gerais bastante eficientes para transformar algoritmos não auto-estabilizantes para se tornarem auto-estabilizantes. A ideia é,

1. Execute o protocolo de não auto-estabilização, ao mesmo tempo,
2. detectar falhas (durante a execução de determinado protocolo) usando os métodos de detecção mencionados acima,
3. em seguida, aplique um protocolo de "reinicialização" (auto-estabilizante) para retornar o sistema a algum estado inicial predeterminado e, finalmente,
4. reinicie o protocolo fornecido (não auto-estabilizante).

A combinação dessas 4 partes é auto-estabilizante (contanto que não haja gatilho de falha durante as fases de correção de falha, por exemplo,). Protocolos iniciais de auto-estabilização também foram apresentados nos artigos acima. Protocolos de redefinição mais eficientes foram apresentados posteriormente, por exemplo

Eficiência adicional foi introduzida com a noção de protocolos adaptativos ao tempo. A ideia por trás disso é que, quando ocorre apenas um pequeno número de erros, o tempo de recuperação pode (e deve) ser reduzido. Os algoritmos de autoestabilização originais de Dijkstra não têm essa propriedade.

Uma propriedade útil dos algoritmos de autoestabilização é que eles podem ser compostos de camadas se as camadas não exibirem nenhuma dependência circular . O tempo de estabilização da composição é então limitado pela soma dos tempos de estabilização individuais de cada camada.

Novas abordagens para o trabalho de Dijkstra surgiram mais tarde, como o caso da proposição de Krzysztof Apt e Ehsan Shoja, que demonstrou como a autoestabilização pode ser formulada naturalmente usando os conceitos padrão de jogos estratégicos, particularmente o conceito de um caminho de melhoria. Este trabalho em particular buscou demonstrar a ligação entre a autoestabilização e a teoria dos jogos.

Complexidade de tempo

A complexidade de tempo de um algoritmo de autoestabilização é medida em rodadas ou ciclos (assíncronos).

• Uma rodada é o menor traço de execução em que cada processador executa pelo menos uma etapa.
• Da mesma forma, um ciclo é o rastreamento de execução mais curto no qual cada processador executa pelo menos uma iteração completa de sua lista de comandos executada repetidamente.

Para medir o tempo de estabilização da saída, um subconjunto das variáveis ​​de estado é definido para ser visível externamente (a saída ). Certos estados de saídas são definidos como corretos (legítimos). Diz-se que o conjunto das saídas de todos os componentes do sistema se estabilizou no momento em que começa a estar correto, desde que permaneça correto indefinidamente, a menos que ocorram falhas adicionais. O tempo de estabilização da saída é o tempo (o número de rodadas (assíncronas) ) até que a saída estabilize.

Definição

Um sistema se auto-estabiliza se e somente se:

1. Partindo de qualquer estado, é garantido que o sistema acabará por atingir um estado correto ( convergência ).
2. Dado que o sistema se encontra em bom estado, é garantido que se mantém em bom estado, desde que não ocorra nenhuma avaria ( encerramento ).

Diz-se que um sistema se autoestabiliza aleatoriamente se e somente se ele se autoestabiliza e o número esperado de rodadas necessárias para atingir um estado correto é limitado por alguma constante . ${\ displaystyle k}$

O projeto de auto-estabilização no sentido acima mencionado é bem conhecido por ser uma tarefa difícil. Na verdade, uma classe de algoritmos distribuídos não tem a propriedade de verificação local: a legitimidade do estado da rede não pode ser avaliada por um único processo. O caso mais óbvio é o token-ring de Dijkstra definido acima: nenhum processo pode detectar se o estado da rede é legítimo ou não no caso em que mais de um token está presente em processos não vizinhos. Isso sugere que a autoestabilização de um sistema distribuído é uma espécie de inteligência coletiva onde cada componente está realizando ações locais, com base em seu conhecimento local, mas eventualmente isso garante a convergência global no final.

Para ajudar a superar a dificuldade de projetar a autoestabilização conforme definido acima, outros tipos de estabilização foram concebidos. Por exemplo, estabilização fraca é a propriedade de que um sistema distribuído tem a possibilidade de atingir seu comportamento legítimo a partir de todos os estados possíveis. A estabilização fraca é mais fácil de projetar, pois apenas garante a possibilidade de convergência para algumas execuções do sistema distribuído, em vez de convergência para cada execução.

Um algoritmo de autoestabilização é silencioso se, e somente se, convergir para um estado global onde os valores dos registros de comunicação usados ​​pelo algoritmo permanecem fixos.

Trabalho relatado

Uma extensão do conceito de autoestabilização é a superestabilização . A intenção aqui é lidar com sistemas distribuídos dinâmicos que passam por mudanças topológicas. Na teoria clássica de autoestabilização, mudanças arbitrárias são vistas como erros em que nenhuma garantia é dada até que o sistema se estabilize novamente. Com sistemas superestabilizadores, existe um predicado de passagem que é sempre satisfeito enquanto a topologia do sistema é reconfigurada.

Referências

links externos

• libcircle - Uma implementação de auto-estabilização usando passagem de token para finalização.