Gestão de Réplicas
usando a aproximação
da Máquina de Estados
(Replication Management using the State-Machine Approach,
Fred Schneider, 1990)
Apresentação (Grupo 2):
Nuno Pimentel
Simão Onofre
1999.04.30
TFD - Réplicas em máquinas de
estados
1
Máquinas de estados

Características:
– Variáveis de estado
• codificam o estado
– Comandos
• são executados a pedido dos clientes
• transformam o estado e produzem resultados
– Resultados são enviados para:
• actuador,
• dispositivo periférico
• ou cliente que solicitou o pedido
1999.04.30
TFD - Réplicas em máquinas de
estados
2
Máquinas de estados (cont.)

Requisitos
– comandos concretizados por programas determinísticos
– a execução de cada comando é atómica com respeito aos
outros comandos

Caracterização semântica
– Os resultados (output) de uma máquina de estados são
completamente determinados pela sequência de pedidos por
ela processados, independentemente do tempo e de qualquer
outra actividade no sistema.
1999.04.30
TFD - Réplicas em máquinas de
estados
3
Máquinas de estados (cont.)

Pedidos processados, um de cada vez, numa ordem
potencialmente causal
– Clientes podem assumir:
• O1: Pedidos R(C, M) e R’(C, M) são processados pela
máquina de estados M pela ordem em que foram solicitados.
• O2: Se R’(C’, M) puder ter sido causado por R(C, M) então M
processa R antes de R’.
1999.04.30
TFD - Réplicas em máquinas de
estados
4
Coordenação de réplicas

Replicação - tipos
– activa: aproximação da máquina de estados
– passiva: primário-secundário

Aproximação da máquina de estados
– Todas as réplicas recebem e processam a mesma sequência
de pedidos
• Acordo
– Todas as réplicas não faltosas recebem todos os pedidos
• Ordem
– Todas as réplicas não faltosas processam os pedidos que recebem
na mesma ordem relativa
1999.04.30
TFD - Réplicas em máquinas de
estados
5
Acordo

Transmissor
– processador que dissemina valor pelos outros processadores

Protocolo deve garantir:
– IC1: Todos os processadores não faltosos acordam no
mesmo valor
– IC2: Se um transmissor é não faltoso então todos os
processadores não faltosos usam o valor do transmissor
como o valor acordado
1999.04.30
TFD - Réplicas em máquinas de
estados
6
Acordo (cont.)

Falha do transmissor
– Falhas bizantinas
• Strong and Dolev [1983]
– Falhas por paragem
• Gries and Schlichting [1984]

Perda ou corrupção do pedido
– Cliente é transmissor
• é irrelevante
– Cliente não é transmissor
• monitorizar difusão do pedido
1999.04.30
TFD - Réplicas em máquinas de
estados
7
Ordem e Estabilidade
A cada pedido é atribuido um identificador único (uid)
 Réplicas ordenam pedidos seguindo uma relação de
ordem total entre os uid
 Um pedido é estável se não puder ser recebido nenhum
outro pedido (de um cliente correcto) com um uid menor


Uma réplica processa de seguida o pedido estável com o
menor uid (Concretização da Ordem)
1999.04.30
TFD - Réplicas em máquinas de
estados
8
Utilização de Relógios Lógicos

Sistemas em que processos/mensagens podem sofrer
atrasos arbitrários, sem se poder assumir a sua falha:
– Falhas bizantinas
• está provado que é impossível estabelecer o acordo
• possibilidade de definir teste de estabilidade e ordem é
irrelevante
– Falhas por paragem
• garantir canal FIFO entre cada par de processadores
• pode assumir-se que um processador P apenas detecta a falha
de um proc. P’ após ter recebido a ultima msg que lhe foi
enviada por este
1999.04.30
TFD - Réplicas em máquinas de
estados
9
Utilização de Relógios Lógicos

Teste de estabilidade com tolerância a falhas por paragem:
– Cada cliente Ci efectua periodicamente algum pedido
(eventualmente nulo) à máquina de estados M
– Um pedido P é estável na réplica Mj se já foi recebido um
pedido com timestamp superior de cada cliente executado
num processador não faltoso
1999.04.30
TFD - Réplicas em máquinas de
estados
10
Utilização de Relógios Físicos
uids formados por Tp(e)+<id_processador>
 Para garantir O1 e O2:

– O1 - cada cliente não pode fazer mais do que um pedido
entre dois ticks sucessivos do relógio do respectivo
processador
– O2 - o grau de sincronização dos relógios tem de ser melhor
do que o tempo mínimo de entrega de mensagens

Testes de estabilidade
– Um pedido (R) é considerado estável numa réplica Mi a ser
executada no processador P se
• I) o relógio local em P ler T e uid(R) < (T - ) ou
• II) já foi recebido um pedido com uid superior de cada cliente
1999.04.30
TFD - Réplicas em máquinas de
estados
11
Identif. gerados pelas réplicas

Fases
– 1ª: cada réplica Mi propõe identificador candidato
cuid(Mi,R)
– 2ª: é seleccionado um dos cuid(Mi,R) que passa a uid(R)

Vantagens
– a única comunicação necessária é entre o processador que
executa o cliente e os processadores que executam as
réplicas
1999.04.30
TFD - Réplicas em máquinas de
estados
12
Identif. gerados pelas réplicas (cont.)

Definições
– Visto(Mi, R): réplica Mi recebeu pedido R e propôs
cuid(Mi,R)
– Aceite(Mi, R): réplica Mi conhece a decisão uid(R)

Restrições
– UID1: uid(R)  cuid(Mi,R)
– UID2: Se Visto (Mi, R’) depois de Aceite (Mi, R) então
cuid(Mi, R’) > uid(R)
1999.04.30
TFD - Réplicas em máquinas de
estados
13
Identif. gerados pelas réplicas (cont.)

Teste de estabilidade
– Aceite(Mi, R) é estável desde que não exista R’ tal que:
• Visto(Mi, R’)
• não esteja Aceite(Mi, R’)
• e cuid(Mi, R’)  uid(R)

Para assegurar O1 e O2:
– O cliente só efectua novamente comunicações quando cada
réplica tiver recebido o pedido
1999.04.30
TFD - Réplicas em máquinas de
estados
14
Identif. gerados pelas réplicas (cont.)

Protocolos de geração de uids e cuids devem assegurar:
– UID1 e UID2
– Se R  R’ então uid(R)  uid(R’)
– Todo Visto(M, R) eventualmente passa a Aceite(M, R)

Cada réplica Mi mantém duas variáveis:
– VISTOi - maior cuid(Mi, R) atribuído a qualquer pedido R
até ao momento visto por Mi
– ACEITEi - maior uid(R) atribuído a qualquer pedido R até
ao momento aceite por Mi
1999.04.30
TFD - Réplicas em máquinas de
estados
15
Identif. gerados pelas réplicas (cont.)

Falhas por paragem
– Ao receber um pedido R, cada réplica:
•
•
•
•
•
calcula cuid(Mi, R) = max (VISTOi, ACEITEi) +1 +I
dissemina cuid(Mi, R)
aguarda recepção cuid(Mj, R) das réplicas não faltosas (NF)
calcula uid(R) = maxMjNF ( cuid(Mj, R) )
e Aceita(Mi, R)
– Optimizações
• ISIS ABCAST
– cuids enviados para cliente, que calcula uid
– réplica única substitui cliente faltoso
1999.04.30
TFD - Réplicas em máquinas de
estados
16
Identif. gerados pelas réplicas (cont.)

Falhas bizantinas
– Necessário garantir sincronização de relógios físicos
– Detecção de falhas
• cada réplica utiliza timeouts para evitar ficar eternamente à
espera de réplicas eventualmente faltosas
• quando réplica Mi suspeita da falha de Mj, envia a todas as
réplicas a msg ‘Mj timeout’
• NF - conjunto de todas as réplicas excepto aquelas que tenham
sido assinaladas como ‘Mj timeout’ por t+1 ou mais réplicas
• Eventual corrupção de cuids não tem implicações
1999.04.30
TFD - Réplicas em máquinas de
estados
17
Faltas de dispositivos de saída

Resultados usados fora do sistema
– Falhas de votador e/ou dispositivo de saída
• Replicação de votadores e dispositivos de saída
– falhas bizantinas - 2t+1 pares votador/dispositivo
– falhas por paragem - t+1 pares votador/dispositivo
• Votador crítico é externo ao sistema
– flap com actuadores hidráulicos
– humano utilizador de écran de computador
1999.04.30
TFD - Réplicas em máquinas de
estados
18
Faltas de dispositivos de saída

Resultados usados dentro do sistema
– Dispositivo de saída no cliente
• votador está no cliente
• falha do votador
– cliente tambem falha
• falha no envio de mensagens
– falhas bizantinas - aguardar t+1 respostas iguais
– falhas por paragem - aguardar primeira resposta que aparece
– Cliente numa réplica
• optimizações na quantidade de mensagens
1999.04.30
TFD - Réplicas em máquinas de
estados
19
Faltas de Clientes

Replicar cliente
– Votador na máquina de estados
• testar e ordenar
– pedidos iguais com uids diferentes
– pedidos supostamente iguais com contextos diferentes

Programação defensiva
– Efectuar testes sintácticos e semânticos nos comandos
• evitar corrupção da máquina de estados
– Estabelecer mecanismos de timeout
• não receber um pedido pode ser tão prejudicial como receber
um errado
1999.04.30
TFD - Réplicas em máquinas de
estados
20
Utilização do tempo para efectuar
pedidos implícitos

Vantagem
– diminuição do nº de mensagens

Desvantagem
– não permite passagem de parâmetros

Exemplos
– release automático, voto por defeito
1999.04.30
TFD - Réplicas em máquinas de
estados
21
Reconfiguração

Possíveis falhas bizantinas
– Condição de combinação
• Proc(t) - Falt(t) > Proc(t)/2
– Em situação de falha
• Problema: Falt(t) aumenta, diminuindo Proc(t) - Falt(t)
• Solução: retirar processadores faltosos antes da condição ser
violada

Apenas falhas por paragem
– Condição de combinação:
• Proc(t) - Falt(t) > 0
– Em situação de falha
• Problema: Falt(t) aumenta, diminuindo Proc(t) - Falt(t)
• Solução: reparar ou substituir processadores faltosos antes da
condição ser violada
1999.04.30
TFD - Réplicas em máquinas de
estados
22
Gestão da configuração

Detecção de faltas
– Um configurador por componente
– Requisitos de um configurador não faltoso
• C1: Apenas é removido da configuração um elemento faltoso
• C2: Apenas é adicionado à configuração um elemento não
faltoso
– Exemplo: monitorização comparativa de comportamentos
– Condição de Combinação:
• configNF(elemF) + configF(elemNF)  t
1999.04.30
TFD - Réplicas em máquinas de
estados
23
Reintegração de Objectos

Consistência com estado do sistema
– e[Ri] - estado da componente e depois de processar pedidos
R0 a Ri
– elemento a reintegrar tem de adquirir estado e[Rjoin] antes
de poder participar no sistema

Elementos auto-estabilizadores
– estado definido pelos últimos k inputs
1999.04.30
TFD - Réplicas em máquinas de
estados
24
Reintegração de Objectos

Elementos não auto-estabilizadores, assumindo falhas por
paragem e usando relógios lógicos
– Se Cliente ou Dispositivo de saída:
• Mi envia as variáveis de estado relevantes antes de enviar
resultados de pedidos com uid(R) > uid(Rjoin)
– Se Réplica Mnew da Maquina de estados:
• Mi envia variáveis de estado e pedidos pendentes a Mnew
• e faz o relay de todas os pedidos subsequentes recebidos de
cada cliente tal que uid(R) < uid(Rc), representando Rc o
primeiro pedido recebido por Mnew directamente do cliente
1999.04.30
TFD - Réplicas em máquinas de
estados
25
Comunicação em grupo ISIS

ABCAST - (Atomic Broadcast)
– Mantém a ordem de entrega dos pedidos, em todas as
réplicas, mesmo que essa ordem não seja premeditada
– Protocolo síncrono

CBCAST - (Casual Multicast)
– Mais fraco que o ABCAST em sincronização distribuída
– Mantém a ordem causal dos pedidos na entrega
– 3 a 5 vezes mais rapido que o ABCAST mas está sujeita a
atrasos
– Protocolo Síncrono ou Assíncrono

ABCAST+CBCAST = Casual Atomic Multicast
– Sincronia virtual
1999.04.30
TFD - Réplicas em máquinas de
estados
26
Trabalho associado

Trabalhos de
– Lamport [1978a] e [1978b]
– Schneider [1982] e [1985]

ISIS Toolkit
– ABCAST
– CBCAST

outros
1999.04.30
TFD - Réplicas em máquinas de
estados
27
Conclusões

Aproximação da Máquina de estados
– Método para concretizar um serviço tolerante a faltas,
através da:
• replicação de servidores
• execução das réplicas em processadores que falhem
individualmente
• coordenação interacções dos clientes com as réplicas
– Bancada de trabalho adequada para compreender e definir
protocolos de gestão de réplicas

«We have not yet encountered an application that could
not be programmed cleanly in terms of state machines and
clients»
1999.04.30
TFD - Réplicas em máquinas de
estados
28
Referências
“Replication Management using the State-Machine
Approach” - Fred B. Schneider (1990)
 RFC 992 - Kenneth Birman, T. A. Joseph (1986)
 “The ISIS project: Real experience with a fault tolerant
programming system”, Kenneth Birman, Robert Cooper

1999.04.30
TFD - Réplicas em máquinas de
estados
29