Unreliable Failure Detectors for
Reliable Distributed Systems
T. D. Chandra and S. Toueg
Journal of the ACM, vol 43, no 2, March 1996, pp.
225-267
Apresentado por Lívia Sampaio
[email protected]
Motivação

Necessidade de construir aplicações tolerante a falhas
(TF)
LSD/UFCG
24/03/2006
2
Motivação

Mecanismos de TF precisam de um serviço de
detecção de falhas
 Exemplo do serviço WEB replicado
Servidores web
Cliente
...
REQUISIÇÃO
RESPOSTA
?
LSD/UFCG
bc
Internet
24/03/2006
3
Motivação

Como resolver o problema da detecção de falhas?
 ambientes síncronos – trivial
 ambientes assíncronos – complicado!
DIFICULDADES ASSÍNCRONO
- impossível decidir se um processo falhou ou está lento
- FLP85
FACILIDADES - ASSÍNCRONO
- semântica simples
- aplicações portáveis
- facilidade de programação
LSD/UFCG
24/03/2006
4
Motivação

Modelo assíncrono com detectores de falhas não
confiáveis (DFNC)
 Alternativa para “amenizar” FLP85
 Introdução de detectores de falhas que podem cometer
erros
LSD/UFCG
24/03/2006
5
Conteúdo

Modelo assíncrono
 Definição de DFNC
 Projeto de DFNC
 Especificação
 Implementação
 Aplicação
LSD/UFCG
24/03/2006
6
Modelo assíncrono

N processos
 Comunicação por troca de mensagens através de uma
rede confiável
 Processos falham por parada
 Incertezas nos atrasos para comunicação e
processamento
 Processos têm acesso a um relógio local
 Introdução de detectores de falhas não confiáveis
LSD/UFCG
24/03/2006
7
Entendendo DFNC

Definição
 DFNC são oráculos que respondem sobre a situação de
falhas do sistema; podem cometer erros.
p
DFp
qr
Lista de suspeitos
rede
q
r
LSD/UFCG
24/03/2006
8
Entendendo DFNC

Projeto
 Serviço distribuído
 “caixa-preta” que encapsula requisitos de sincronismo do
sistema ; interface bem definida
 Modularização
 Separação de conceitos
LSD/UFCG
24/03/2006
9
Entendendo DFNC

Especificação de DFNC
 Em termos de 2 propriedades:
 Abrangência – quantidade de falhas detectadas
 Exatidão – quantidade de falsas suspeições cometidas
 Aplicações são definidas em função da especificação dos
DFNC e não de uma implementação em particular
 Detectores de falhas perfeitos (semântica mais forte)
 Abrangência forte – em algum momento, todo processo falho será considerado
suspeito, permanentemente, por qualquer processo correto;
 Exatidão forte – nenhum processo correto será suspeitado por outro
processo correto.
Propriedades muito restritivas!!!
LSD/UFCG
24/03/2006
10
Entendendo DFNC

Enfraquecendo a semântica de DFNC
EM TERMOS DE
ABRANGÊNCIA:
 Abrangência fraca – em
algum momento, todo processo
falho será considerado suspeito,
permanentemente, por algum
processo correto;
EM TERMOS DE
EXATIDÃO:
 Exatidão fraca – algum processo
correto nunca é suspeitado;
 Exatidão forte eventual – em algum
momento, o detector garante a
exatidão forte;
 Exatidão fraca eventual – em algum
momento, o detector garante a
exatidão fraca.
LSD/UFCG
24/03/2006
11
Entendendo DFNC

Classificação
 Em termos de semântica: forte -> fraca
 São oito classes (= 2 abrangência * 4 exatidão)

Comparando as classes de DFNC
Exatidão “em atraso”
Enfraquecendo a abrangência
Enfraquecendo a exatidão
LSD/UFCG
24/03/2006
12
Entendendo DFNC

Equivalência de Classes
 Considere a seguinte relação entre duas classes D e D’:
D  D’

D  D’
 Conceito de redutibilidade
 Um algoritmo de redução é aquele capaz de transformar um
detector de falhas D em outro D’, tal que D  D’
LSD/UFCG
24/03/2006
13
Entendendo DFNC

Equivalência de classes
 Aplicando o conceito de redutibilidade às classes de DFNC
P
Q
P

Q
S

W
S
W
 A relação inversa também é verdade
PQ, S  W, P  Q, S  W
Redução acontece sobre a propriedade de abrangência,
então: 8 classes podem ser reduzidas a quatro
LSD/UFCG
24/03/2006
14
Implementação de DFNC

Independência de implementação
 Implementações normalmente são baseadas em
timeouts
 Modelo push
p
q
rede
DFp
r
“Q“Q
está
está
vivo”
? vivo”
q
Lista de suspeitos
 Esse exemplo não implementa S !
 Timeouts mal configurados podem violar exatidão
 É preciso usar timeouts dinâmicos
LSD/UFCG
24/03/2006
15
Aplicação para DFNC

O problema do consenso
 N processos, dentre os quais no máximo f<N podem falhar
por parada, propõem um valor e tentam decidir sobre um
dos valores propostos.

Formalmente:
 Validade
 Acordo
 Terminação
O consenso deve garantir segurança e exatidão!
LSD/UFCG
24/03/2006
16
Aplicação para DFNC

O protocolo de consenso CT96
 Paradigma do coordenador rotativo
 Utiliza ◊S (N  2F+1)
 Rodadas assíncronas
 Cada rodada tem um coordenador conhecido a priori
 O consenso termina quando existir um coordenador que
não seja suspeitado por um número suficiente de
participantes
LSD/UFCG
24/03/2006
17
Rodada de CT96 sem falhas
Fase 1
Fase 2
Fase 3
Fase 4
p1
p2
p3
estimativas
proposta
ack ou nack
decisão
difusão confiável
LSD/UFCG
24/03/2006
18
Rodada de CT96 com falhas
Fase 1
Fase 2
Fase 3
Fase 4
p1
p2
p3
estimativas
LSD/UFCG
proposta
ack ou nack
24/03/2006
19
Difusão atômica

O problema da difusão atômica
 Dado um conjunto de N processos, estes irão entregar as
mesmas mensagens e na mesma ordem.

Formalmente
 Validade
 Acordo
 Ordenação total
LSD/UFCG
24/03/2006
20
Consenso e Difusão atômica

Aplica-se o conceito de redutibilidade
 Problemas são equivalentes

Consenso com difusão atômica
 Difusão atômica com consenso
LSD/UFCG
24/03/2006
21
Referências sobre detectores de falhas

[SBO03] Detectores de falhas em sistemas
assíncronos (tutorial)
 [OBB03] Projeto e Implementação de um Serviço de
Detecção de Falhas com Semântica Perfeita.
 [COB05] Engineering a Failure Detection Service for
Widely Distributed Systems
 [DUHK05] Definition and Specification of Accrual
Failure Detectors
 [LFA00] Optimal Implementation of the Weakest
Failure Detector for Solving Consensus
LSD/UFCG
24/03/2006
22
Referências sobre detectores de falhas

[NJ-P04] QoS of Timeout-based Self-Tuned Failure
Detectors: the Effects of the Communication Delay
Predictor and the Safety Margin.
 [CHT96] The Weakest Failure Detector for Solving
Consensus
 [CTA00] On the Quality of Service of Failure
Detectors
 [SB05] Adaptive Indulgent Consensus
LSD/UFCG
24/03/2006
23
Obrigada!!!
Mais questionamentos????
LSD/UFCG
24/03/2006
24