Tolerância a Falhas
Prof. Alcides Calsavara
http://www.ppgia.pucpr.br/~alcides
Ariane 5
Lançado em 4/6/1996 pela European Space Agency
10 anos de projeto, ao custo de 7 bilhões de dólares
Foguete e sua carga avaliados em 500 milhões de dólares
Explodiu 40 segundos depois do lançamento
Motivo: conversão de um número de ponto flutuante de 64 bits
(correspondente à velocidade horizontal do foguete)
para um valor inteiro de 16 bits (ao reusar um módulo da Ariane 4)
Therac-25




Máquinas de aceleração linear utilizadas no
tratamento de câncer
East Texas Cancer Center, Tyler, entre 1985 e
1987
Quatro pessoas em tratamento médico de
câncer receberam doses letais de radiação
Motivo: falha de programação na coordenação
de tarefas concorrentes (condição de corrida).
Míssel Americano Patriot



Guerra do Golfo, fevereiro de 1991
O Patriot falhou em interceptar um míssel
Scud (lançado pelo inimigo), o qual matou 28
soldados americanos em suas barracas, em
Dahran, Arábia Saudita.
Motivo: erro no cálculo do tempo devido a um
arredondamento na representação do valor
1/10 usando um registrador de 24 bits. (O erro
final chegou a 34 décimos de segundo, tempo
suficiente para o Scud percorrer quase meio
quilômetro).
Airbus A320





Varsóvia, setembro de 1993
A aeronave, ao pousar, bateu num morro e
duas pessoas morreram.
Pilotos esperavam ter vento contra a aeronave
no momento do pouso, por isso aumentaram a
velocidade da aeronave.
Mas tiveram vento a favor, fazendo o avião
ganhar muita velocidade no pouso.
Por isso, os sensores nas rodas não
sinalizaram que a aeronave havia pousado,
impedindo que os freios fossem acionados.
Dragonair's A320




Hong-Kong, junho de 1994
Pouso complicado
Um forte vento impediu o movimento
dos flaps no momento do pouso.
Mas, o sistema acreditou que os flaps
estavam na posição correta, causando
sérios problemas na operação de pouso.
Boeing B757



Colômbia, dezembro de 1995
Aeronave bateu numa montanha, matando
160 pessoas
Motivo: sistema de gerenciamento de vôo
estava operando com uma base de dados de
navegação incorreta, fazendo com que a
tripulação recebesse informação errada sobre
a posição da aeronave.
Intel Pentium Processor






1995
Algoritmo de divisão utiliza uma tabela de busca com
1066 entradas.
Somente 1061 entradas foram carregadas na seção PLA
devido a um erro num loop.
Gravado em silício e nunca verificado.
Efeito: algumas divisões com ponto flutuante geram
resultados errados na quarta casa decimal.
Custo da substituição: mais de 400 milhões de dólares.
Polícia Francesa


Paris, 1989
41.000 motoristas com infração de
trânsito foram notificadas que haviam
cometido crimes como assassinato,
tráfico de drogas, extorsão e
prostituição, ao invés de suas violações
de trânsito.
Internet Worm




Novembro de 1988
6.000 computadores na Internet caíram em
poucas horas.
Semanas se passaram até que voltassem a
operar normalmente.
Motivo: um hacker (estudante de graduação)
criou um sistema que continha um erro de
programação e um erro matemático em seu
código, fazendo com que se replicasse muito
rapidamente.
Exemplos de Falhas

http://www5.in.tum.de/~huckle/bugse.html

http://www.cs.tau.ac.il/~nachumd/verify/horror.html
Referências Bibliográficas




Sistemas Distribuídos: princípios e paradigmas, 2a.
Edição. Andrew S. Tanenbaum, Maarten van Steen.
Pearson/Prentice Hall, 2007/2004.
Sistemas Distribuídos: conceitos e projeto, 4a. Edição.
G. Coulouris, J. Dollimore, T. Kindberg. AddisonWeley/Bookman, 2005/2007.
Basic Concepts and Taxonomy of Dependable and
Secure Computing. A. Avizienis, J-C Laprie, B. Randell,
C. Landwehr. IEEE Trans. Dependable and Secure
Computing, 1(1), pp. 11-33. January-March, 2004.
A Survey of Dependability Issues in Mobile Wireless
Networks. C. Basile, M-O Killijian, D. Powell. Technical
Report, LAAS CNRS Tolouse, France. 2003.
Referências Bibliográficas




Fault Tolerance in Distributed Systems.
Pankaj Jalot
Prentice Hall, 1994.
Building Secure and Reliable Network
Applications. Kennet P. Birman. Manning
Publications, 1996
Fault-Tolerant Computer System Design.
Dhiraj K. Pradhan. Prentice Hall, 1996
Dependable Computing Systems:
Paradigms, Performance Issues, and
Applications. Albert Y. Zomaya. Wiley, 2005.
Referências Complementares





Code Complete: A Practical Handbook of Software Construction by Steve
McConnell. A comprehensive overview of software-development techniques
that help produce robust and reliable code.
Computer-Related Risks by Peter G. Neumann. An excellent discussion of
why computer programs often fail. It is filled with anecdotes from Neumann's
tenure as the moderator of the Usenet Risks group.
Fatal Defect: Chasing Killer Computer Bugs by Ivars Peterson. A
comprehensive look at real-life cases when life-critical computer systems failed.
Safeware: System Safety and Computers by Nancy Leveson. A thorough
introduction to risk analysis and other techniques for building programs that can
endanger lives or cause a great deal of damage if they fail.
Wicked Problems, Righteous Solutions by Peter DeGrace and Leslie Hulet
Stahl. An irreverent look at software development models such as the waterfall
and the spiral. The book is seasoned with critical comments on how they work
in practice.
Referências Complementares

How Software Doesn't Work. Alan Joch. BYTE.
Dezembro, 1995.
http://www.byte.com/art/9512/sec6/sec6.htm
• Nine ways to make your code more
•
•
•
reliable
How to Build Reliable Code
Five Easy Steps Toward Disaster
Make Quality Job 1
Nove maneiras de tornar o seu
código mais confiável
1.
2.
3.
4.
5.
6.
7.
8.
9.
Planeje.
Gaste o seu suor sobre a especificação do projeto.
Isole as funções críticas.
Documente o processo de desenvolvimento.
Comente o seu código.
Teste exaustivamente todos os componentes individuais
e também todas as suas interações no sistema.
Valide o produto de forma independente.
Inclua sistemas de backup.
Coma os seus vegetais.
Cinco passos fáceis para o desastre
1.
2.
3.
4.
5.
Amontõe funcionalidades: cole novas funcionalidades em
qualquer lugar que seja possível, sem se preocupar se isso
poderá afetar a parte principal do sistema.
Objetive ambientes heterogêneos: empregue soluções não
documentadas e não siga as orientações sobre interfaces
padrão do sistema.
Teste inadequadamente: deixe para testar o sistema
somente depois que todo o código estiver pronto.
Documente pobremente: evite escrever documentação e
nunca reserve tempo para atualizá-la, especialmente no final
do projeto, quando os programadores ainda não esqueceram
o que fizeram (o que fatalmente ocorrerá quando iniciarem
novas tarefas).
Quando em dúvida, vacile: altere a especificação do projeto
sempre que houver alguma forma de pressão (tempo, custo).
Tolerância a Falhas em
Sistemas Distribuídos
Definição de Sistema Distribuído
"Um sistema distribuído é uma
coleção de computadores autônomos
conectados por uma rede e
equipados com um
sistema de software distribuído.“
[Coulouris]
Definição de Sistema Distribuído
"Um sistema distribuído é uma
coleção de computadores independentes
que aparenta ao usuário ser
um computador único."
[Tanenbaum]
Definição de Sistema Distribuído
"Você sabe que tem um sistema distribuído
quando a falha de um computador do qual
você nunca ouviu falar faz com que você
pare completamente de trabalhar.“
[Leslie Lamport]
Dependabilidade




Availability (disponibilidade)
Reliability (confiabilidade)
Safety (segurança no funcionamento)
Maintainability (capacidade de
manutenção)
Disponibilidade



Propriedade de um sistema estar pronto
para ser usado imediatamente.
Probabilidade de o sistema estar
funcionando corretamente em qualquer
momento determinado.
Um sistema de alta disponibilidade tem
alta probabilidade de estar funcionando
num dado momento.
Confiabilidade



Propriedade de um sistema poder
funcionar continuamente sem falha.
Definida em termos de um intervalo de
tempo.
Um sistema de alta confiabilidade
provavelmente continuará a funcionar
sem interrupção durante um período de
tempo relativamente longo.
Disponibilidade versus
Confiabilidade


Um computador que fica fora do ar por
um milissegundo a cada hora tem alta
disponibilidade (99,9999%), mas baixa
confiabilidade.
Um computador que nunca cai mas é
sempre desligado duas semanas por
ano tem alta confiabilidade, mas
somente 96% de disponibilidade.
Segurança no funcionamento


Se um sistema deixar de funcionar
corretamente durante um certo tempo,
nada de catastrófico acontecerá.
Exemplo: sistemas de controle de usinas
de energia nuclear.
Capacidade de manutenção

Facilidade com que um sistema que
falhou pode ser consertado.
• Modularização
• Documentação

Um sistema com grande capacidade de
manutenção tende a ter alta
disponibilidade.
Modelos de Falhas
Type of failure
Description
Crash failure
A server halts, but is working correctly until it halts
Omission failure
Receive omission
Send omission
A server fails to respond to incoming requests
A server fails to receive incoming messages
A server fails to send messages
Timing failure
A server's response lies outside the specified time interval
Response failure
Value failure
State transition failure
The server's response is incorrect
The value of the response is wrong
The server deviates from the correct flow of control
Arbitrary failure
A server may produce arbitrary responses at arbitrary times
Consenso na presença de falhas
The Byzantine generals problem for 3 loyal generals and1 traitor.
a)
The generals announce their troop strengths (in units of 1 kilosoldiers).
b)
The vectors that each general assembles based on (a)
c)
The vectors that each general receives in step 3.
Consenso na presença de falhas

The same as in previous slide, except now
with 2 loyal generals and one traitor.
Comunicação confiável
cliente-servidor
a)
b)
c)
Normal case
Crash after execution
Crash before execution
Comunicação confiável
cliente-servidor
Client
Server
Strategy M -> P
Strategy P -> M
Reissue strategy
MPC
MC(P) C(MP)
PMC
PC(M
)
C(PM)
Always
DUP
OK
OK
DUP
DUP
OK
Never
OK
ZERO
ZERO
OK
OK
ZERO
Only when ACKed
DUP
OK
ZERO
DUP
OK
ZERO
Only when not ACKed
OK
ZERO
OK
OK
DUP
OK
Material Complementar

Curso do Prof. Raul Ceretta Nunes, UFSM
http://www-usr.inf.ufsm.br/~ceretta/elc619/