Tolerância a falhas
Módulo 5
[C11,C15,T4.5] (65 p.)
1
Conteúdo
 Falhas



tipos
tempo médio até falhar
em processadores
 Uso de redundância



tipos
replicação ativa
replicação primary backup
 Consenso na presença de falhas
2
Falhas
 Um sistema falha quando não funciona de acordo com sua
especificação.
 Falhas típicas:
 hardware: processador, memória, dispositivo de E/S,
cabo, ...
 software: erros de programação, erros de operação,
situações não previstas, ...
 Objetivo de tolerância a falhas: garantir que um sistema
continue a funcionar corretamente na presença de defeitos.
 Tolerância a falhas é necessária principalmente em
aplicações que requerem alta disponibilidade.
3
Tipos de falhas
 Falha transiente: ocorre apenas uma vez; se a
operação é repetida, a falha desaparece. Exemplo:
falha numa transmissão usando micro-ondas
porque algum objeto obstrui temporariamente.
 Falha intermitente: ocorre de maneira aleatória
e imprevisível. Exemplo: um conector com mau
contato.
 Falha permanente: ocorre sempre até que o
componente seja substituído. Exemplo: um chip
queimado, erros em software.
4
Tempo médio até falhar
 Exemplo:
 Um componente tem uma probabilidade p de falhar em
um segundo.
 A probabilidade desse componente não falhar em k
segundos consecutivos é

O tempo estimado até esse componente falhe (mean
time to failure) é

Assim, se p = 0.001 então MTF = 1000 segundos.
5
Falhas em processadores
 Tipos:


Fail-silent fault (ou Fail-stop fault): um
processador com falha pára e não responde a
subsequentes requisições ou produz qualquer
resultado.
Byzantine fault: um processador com falha
continua a operar, emitindo resultados errados,
possivelmente em acordo com outros
processadores com falha, causando a impressão
de que estão todos funcionando normalmente. 6
Uso de redundância
 Tipos de redundância:



Redundância de informação: bits extras são
adicionados para se recuperar de bits errados.
Redundância de tempo: uma ação é executada
e, se necessário, é executada novamente. (Útil
para falhas transientes e intermitentes.)
Redundância física: equipamento extra é
adicionado para que o sistema como um todo
tolere a falha de um ou outro componente.
Exemplo: múltiplos processadores.
7
Uso de replicação ativa
 Todos os processadores são usados o tempo todo como
servidores (em paralelo) a fim de ocultar falhas
completamente.
 TMR: Triple Modular Redundancy
 Sistema tolerante a falhas no nível k: satisfaz sua
especificação mesmo se até k componenetes falharem
simultaneamente:
 fail-silent fault: requer k+1 componenetes
 byzantine fault: requer 2k+1 componentes
 Requisito: todas as requisições chegam nos servidores
numa mesma ordem (atomic broadcast problem).
8
Uso de primary backup
 Apenas um processador (primary) é o servidor a cada
instante. Se este falhar, um outro processador (backup) é
ativado para operar em seu lugar.
 A substituição de um processador por outro não deve ser
notada pelas aplicações; somente o sistema operacional do
cliente deve notar.
 Vantagens:
 Mais simples: mensagens do cliente vão para apenas
um servidor (não é necessário ordenar mensagens).
 Na prática, requer menos máquinas.
 Desvantagem: não funciona se para Byzantine faults.
9
Consenso na presença de falhas
 Exemplos: eleição de um coordenador, decisão quanto a
fazer ou não commit de uma transação, divisão de tarefas.
 Primeiro caso: processadores confiáveis, mas possíveis
falhas de comunicação. Exemplo: two-army problem.
Consenso é impossível sem comunicação confiável!
 Segundo caso: comunicação confiável, mas possíveis
falhas de processadores. Exemplo: Byzantine generals
problem.
Consenso é possível quando há m processadores confiáveis
somente se houver 2m+1 processadores confiáveis.
10