DMCC – MATA25 – Seminários Científicos III – Algoritmos Distribuídos – 2008.1 – Fabíola Greve
1
Self-Stabilization Systems
Concepts and Algorithms
Romildo Martins da Silva Bezerra, Student Member, IEEE
Resumo — O conceito de auto-estabilização em sistemas
distribuídos foi inicialmente introduzido em 1974 [1]. Em um
sistema de auto-estabilizável, independentemente do estado
inicial do sistema, o sistema automaticamente converge para um
estado desejável num conjunto finito de passos. O conjunto de
estados globais pode ser dividido em duas categorias, legal e
ilegal, onde a propriedade de “legitimidade” induz a uma
alteração do estado de um dos processos. Este artigo fornece
uma visão geral de sistemas auto-estabilizáveis apresentando
conceito, classificação, modelos e alguns algoritmos.
Palavras chave — Auto-estabilização,
Algoritmos adaptativos.
Self-Stabilization,
I. INTRODUÇÃO
Conceito de self-stabilization (auto-estabilização) é uma
linha de pesquisa promissora na área de sistemas
distribuídos, mas precisamente no contexto de tolerância a
falhas onde pode ser utilizados algoritmos robustos protegidos
contra qualquer eventual falha ou um conjunto possível de
falhas em estados transitórios. Neste último caso, são
utilizados algoritmos de auto-estabilização que pode passar
por estados globais falhos, mas consegue atingir um estado
desejável num conjunto finito de passos. Ou seja, um
algoritmo auto-estabilizável não precisam saber nada sobre as
falhas (tipo, duração, ocorrência), pois a única exigência na
sua construção é que o seu insucesso não é permanente.
Um algoritmo auto-estabilizável é construído de tal forma
que um determinado processo irá executar as mesmas
operações em estados falhos ou não, visando atingir ume stado
correto em um número finito de passos. Tal algoritmo também
não requer uma inicialização correta, pode se recuperar de
qualquer falha transiente a qualquer momento o que torna a
auto-estabilização uma solução interessante para um grande
número de aplicações como em grafos, comunicação de
protocolos e exclusão mútua [3].
Esta “incerteza” do tempo de convergência e a instabilidade
dos estabos parciais deste tipo de algoritmo requer uma
preocupação com a sua complexidade. A complexidade de um
tempo algoritmo auto-estabilizável é medido em rounds ou
ciclos (assíncronos).
O
Artigo escrito em 15 de junho de 2008. Disponível em:
http://www.romildo.net/dmcc.html. Este artigo corresponde a um requisito
parcial da disciplina Algoritmos Distribuídos (MATA25). Professora: Fabíola
Greve.
Desde a sua primeira apresentação vista em [1], os
progressos realizados neste novo paradigma revelou que é um
dos temas mais importantes e promissores em tolerância a
falhas [2].
Neste trabalho serão apresentadas a definição e
classificação de auto-estabilização (Seção 2), o algoritmo
proposto em 1974 por Dijkstra para resolução da exclusão
mútua (Seção 3), reflexões na construção do algoritmo em
relação ao ambiente e ao paradigma de programação utilizado
(Seção 4) e por fim considerações finais com vantagens,
utilizações e exemplos na última seção.
II. DEFINIÇÃO E CLASSIFICAÇÃO
Antes da definição de auto-estabilização é necessário
especificar o ambiente no qual um sistema auto-estabilizável
está inserido.
Um sistema é composto por dois tipos de componentes:
processos e interligações entre processos (utilizando
paradigmas como memória compartilhada distribuída ou
passagem de mensagens). A topologia é vista como um grafo
dirigido onde os nós correspondem aos processos e as arestas
com a passagem de informações de acordo com o paradigma
de comunicação utilizado. A visão de estado global de um
sistema , corresponde ao conjunto das visões locais de seus
componentes. Com isso definimos como o “comportamento”
(behaviour) como o conjunto dos estados, transições e o
critério definido na relação de transição.
Um sistema auto-estabilizável S em relação a um predicado
P, dentre o seu conjunto de estados globais (legítimo ou não),
onde P leva o sistema S a um estado correto. Se S é autoestabilizável, o predicado P deve preencher duas propriedades:
• Closure – O é fechado para a execução de S, ou seja,
uma vez que P estabiliza S, S não pode ter sua
estabilização perdida.
• Convergence – A partir de um estado global arbitrário
Q1, a convergência de S é garantida a partir de um
número finito de passos em P.
A aplicação de um predicado P sobre um nó do sistema S
deve ser feita apenas se tal nó possui o privilégio para alterar
seu estado corrente de acordo com o predicado P. Quando um
nó possui tal privilégio, seu estado é alterado e consideramos
1
Q é um estado arbitrário dentro de um conjunto possível de estados que
garante a convergência em uma seqüência finita de passos.
DMCC – MATA25 – Seminários Científicos III – Algoritmos Distribuídos – 2008.1 – Fabíola Greve
neste caso que o comportamento de S foi alterado. um sistema
auto-estabilizável, a definição d eum estado legal deve
satisfazer as seguintes propriedades:
1. Existe pelo menos um processo com privilégio no
sistema (garante a inexistência de deadlocks).
2. Todo movimento de um estado legal, deve levar a
um novo estado legal (closure).
3. Durante a uma execução infinita, cada processo
pode receber o privilério um número infinito de vezes
(garante a inexistência de starvation).
4. Dados dois estados legais S1 e S2, existe um
conjunto de movimentos com a utilização do
predicado P que permite S1 → S2 (garante a
acessibilidade dos estados).
O modelo de falhas é um ponto muito importante a ser
discutido em sistemas auto-estabilizáveis. Nota-se que ao
suportar estados globais falhos, uma falha transiente é
suportada por um sistema auto-estabilizável pois este tipo de
falha pode mudar o estado de um sistema, mas não o seu
comportamento. A propriedade de auto-estabilização na
recuperação de falhas transientes conta com a suposição de
que eles não continuem a ocorrer infinitamente, pois
corresponde
a uma adversário que não permitirá a
convergência do sistema.
Ainda em relação ao modelo de falhas, um ataque malicioso
pode ser visto também como um adversário que dificulta a
convergência do algoritmo. O que torna este tipo de ataque
mais preocupante é que pode não ser possível a um sistema de
"saber" que está sendo atacado. Para ser auto-estabilizável, um
sistema deve ter a capacidade de se recuperar de tais ataques
maliciosos assumindo que eles não podem ocorrer
repetidamente, e que um subconjunto funcional do sistema
será deixado intacto. Esta última parte é crucial, uma vez que
um verdadeiro atentado poderia destruir um sistema alterando
para um estado não previsto a partir do estado inicial ou
alterando a topologia esperada da rede.
Nota-se a dificuldade de alcançar auto-estabilização em
sistemas dinâmicos onde os seguintes pontos, em relação ao
modelos de falhas, devem ser considerados:
• Inicialização Inconsistente – Os processos podem
inicializar com valores locais que não permitam a
convergência de S0.
• Erros de transmissão – A perda, corrupção ou a
ordenação das mensagens pode gerar uma inconsistência
da visão global de um ou mais processos.
• Falha no processo e recovery – Se um processo volta a
executar após uma queda, o seu estado local deve estar
inconsistente com os outros processos.
2
• Crash de memória – Um crash de memória tornará
inconsistente o comportamento geral do sistema.
• Alteração de funciomaneto (mode change) - Ao alterar
o modo de funcionamento é impossível que todos os
processos de mudança para o efeito, ao mesmo tempo. O
programa é obrigado a chegar a um estado global em que
alguns processos foram alterados, enquanto outros não
foram.
Além da preocupação com o modelo de falhas, a concepção
topológica do modelo na construção de um algoritmo autoestabilizável é de suam importância, uma vez que o estado
local pode se basear em um ou mais estados de outros
processos. No estudo de caso da próxima seção, veremos que
o algoritmo só guncionará para redes Token Ring.
Uma extensão do conceito de auto-estabilização é o da
superstabilization [8], onde o objetivo é tornar um algoritmo
auto-estabilizável susteptível a mudanças topológicas. Na
teoria clássica de auto-estabilização, mudanças arbitrárias são
vistas como erros, dificultando o processo de convergência.
Com superstabilizing, existe uma passagem de predicado que
é sempre satisfeita, enquanto a topologia é reconfigurada.
Maiores detalhes quanto a importância da topologia podem ser
vistos em [3].
Tipos e Classes de Sistemas Auto-Estabilizáveis
Os sistemas auto-estabilizáveis podem ser classificados de
acordo com as propriedades de convergence e closure [3]:
1.
2.
3.
4.
Strong convergence to strong closure;
Strong convergence to weak closure;
Weak convergence to weak closure;
Weak convergence to strong closure;
Estas quatro classes podem ser organizadas (Figura 01)
especificando três tipos de auto-estabilização:
Deterministic
Stabilization
1
2
4
1
3
0
Probabilist
Stabilization
Pseudo‐ Stabilization
Figura. 01. Relação entre classes e tipos de auto-estabilização [3]
Somente a estabilização determinística oferece um limitado
tempo de estabilização partindo de um estado não legítimo,
mas a pseudo-estabilização e a estabilização probabilística
pode ser mais fácil de alcançar ou ser mais eficiente [3].
DMCC – MATA25 – Seminários Científicos III – Algoritmos Distribuídos – 2008.1 – Fabíola Greve
III. ALGORITMO DE AUTO-ESTABILIZAÇÃO PROPOSTO POR
DIJKSTRA PARA O PROBLEMA DE EXCLUSÃO MÚTUA
Em 1974, Dijkstra apresentou o conceito de autoestabilização em sistemas distribuídos [1]. O modelo proposto
consiste num conjunto de n processos (machines) de estados
finitos conectados através de uma topologia em anel. Neste
caso, cada processo apenas conhece dois vizinhos,
denominados Left e Right. O conceito de privilégio de um
processo é a habilidade em poder modificar seu estado atual.
Tal habilidade é baseada em um predicado booleano P que
utiliza o estado corrente de seus vizinhos (Left e Right). O
algoritmo apresentado por Dijkstra (Figura 02) segue as
quatro propriedades especificadas nesta seção.
O algoritmo considera um estado legítimo no qual
exatamente um processo goza de um privilégio. Isso
corresponde a uma forma de exclusão mútua pois o privilégio
pode ser associado a entrada em uma região crítica.
Existe um processo especial P0 no anel, onde ele possui
diferentes regras em relação aos outros processos do anel. O
estado atual de cada procsso é representado por l . o algoritmo
assume um modelo de comunicação entre processos, como por
exemplo, variáveis compartilhadas.
3
l0 = 2
2→0
P0
P0
Estado Inicial
k=3 e n=3
Passo 01
P2
P1
l2 = 2
l1 = 0
P2
P1
2→0
0→2
2→0→1
2→0→1
P0
P0
Passo 02
Passo 03
P1
P2
2→0→2
0→2→0
P2
P1
2→0→2→0 0→2→0→1
0 →2→2→1
P0
Para P0,
if lo = ln-1 then l0:=(l0+1) mod k e P0 tem o privilégio
Passo 04
Para Pi,
if li ≠ li-1 then li:=(li-1) mod k e Pi tem o privilégio
P2
P1
2→0→2→0→1
Estabilização
Atingida
0→2→0→1
Figura. 02. Algoritmo de Dijkstra
Figura. 03. Execução do Dijkstra’s Mutual Exclusion Algorithm [2]
Na figura 03, é mostrada a execução do algoritmo para três
processos que podem assumir um conjunto de três valores
{0,1,2}. Observe que o processo de execução é simultâneo,
necessitando assim de uma variável para verificação do round
e seu respectivo valor.
No passo 01, P0 executa o respectivo predicado P e altera
seu valor para 0 (l0:=(2+1) mod 3) e recebe o privilégio. Para
P1 e P2 , os valores são alterados para 2 e 0, respectivamente.
Após cinco passos o algoritmo converge para os valores
iniciais [2,0,2]. A prova de closure e convergence pode sem
vistas em [6]. A quantidade de passos para convergência deste
algoritmo é O(n2) [4].
IV. CONSIDERAÇÕES FINAIS
Um algoritmo distribuído é dito auto-estabilizável se, a
partir de um estado arbitrário, é garantida a convergência para
um estado legítimo e a consecutiva permanência em um
conjunto de estados legítimos subseqüente.
A convergência de um algoritmo auto-estabilizável implica
três importantes propriedades de auto-estabilização:
• Convergência com tolerância a falhas arbitrárias
embutida no sistema
• Não “legalidade” do estado inicial
• A adaptabilidade a mudanças de configuração do
sistema (como exemplo, a topologia muda e pode ser
vista como uma falha transiente)
• Podem ser utilizados para ambientes não autoestabilizáveis, mas com o objetivo de “migrar” o estado
atual para um novo estado desejado, como por
exemplo, a atualização de software
Em contrapartida, eles apresentam como problemas:
DMCC – MATA25 – Seminários Científicos III – Algoritmos Distribuídos – 2008.1 – Fabíola Greve
• A não tolerância a falhas não permanentes
• A eventual não compatibilidade de estados
transitórios até a convergência
• Geralmente é mais complexo e difícil de construir.
Embora ainda existam muitos problemas que não têm
qualquer solução auto-estabilizável, o futuro ainda requer
melhor pesquisa na: redução do número necessário de estados,
redução de convergência de tempo, a flexibilização das
hipóteses utilizadas, ou melhor, uniformidade correção
automática métodos de verificação, dentre outros.
Recentemente, a auto-estabilização tornou-se uma questão
interessante também em sistemas de tempo real e este parece
ser mais um importante rumo de pesquisa.
Uma possibilidade interessante é a combinação de conceitos
clássicos de sistemas distribuídos com este paradigma
apresentado. Um bom exemplo disto consiste na combinação
de detectores de falhas e superstabilization.
Algoritmos auto estabilizáveis tem uma gama muito grande
de aplicações [3]: Communication protocols, Graph theory
problems, Termination detection, Clock synchronization,
Fault containment.
Recomendo a leitura da referência [2] que aborda pontos
importantes não discutidos aqui como a utilização do modelo
de passagem de mensagens e memória compartilhada
distribuída no processo de comunicação, além da discussão
sobre o custo da auto-estabilização.
BIBLIOGRAFIA
[1]
[2]
[3]
[4]
[5]
[6]
E.W. Dijkstra: Self-stabilizing systems in spite of distributed control.
Communications. ACM 17 (1974), 11: 643-644.
Schneider, M. 1993. Self-stabilization. ACM Comput. Surv. 25, 1 (Mar.
1993), 45-67.
J. Brzezinski, and M. Szychowiak, Self-Stabilization in Distributed
Systems - a Short Survey, Foundations of Computing and Decision
Sciences, 25(1), 2000.
M. Flatebo, A. K. Datta, and S. Ghosh, "Self-stabilization in distributed
systems," in Readings in Distruted Computers. Systems. T. L. Casavant
and M. Singhal Eds. New York: IEEE Computer Society Press, 1994,
pp. 100-114.
Dolev, S. 2000 Self-Stabilization. MIT Press.
Vijay K. Garg, Ph.D., Elements of distributed computing, John Wiley &
Sons, Inc., New York, NY, 2002
APÊNDICE – ALGORITMO PARA ELEIÇÃO DE LÍDER
4
Romildo Martins da Silva Bezerra received a B.S. degree in Computer
Science from Universidade Federal da Bahia (UFBA) in 2002, and M.S.
degree in Computer Networks in 2005 from Universidade Salvador
(UNIFACS). He is now a teacher at Centro Federal de Educação Tecnológica
da Bahia (CEFET/BA) and doctor student in Computer Science at Doutorado
MultiInstitucional em Ciência da Computação (UFBA/UNIFACS/UEFS),
since 2007. His research interests include quality of service, autonomic
networks and computer network management.