Sistemas Distribuídos Aula 24

Sistemas Distribuídos
Aula 24
Aula passada
Reliability e
Availability
Modelo de falhas
Falhas na prática
Redundância
Aula de hoje
Triple Module
Redundancy
Tipos de falha
Falhas Bizantinas
Grupos redundantes
Protocolo de acordo
bizantino
Figueiredo – 2016
Organizando Componentes
Três módulos em sequência (A,B,C)
resultado enviado do anterior enviado ao próximo
Entrada
A
B
C
Saída
Como organizar a redundância?
Ideia 0: replicar componentes de forma
independente
ex. três linhas em paralelo
Operacional apenas quando não há falhas
em alguma linha
Figueiredo – 2016
Triple Modular Redundancy (TMR)
Organizar componentes de forma não-independente
Votador: circuito simples, se duas ou mais entradas
são iguais, repassa entrada, caso contrário nada
O que ocorre se A1, B2 e C3 falham?
Funciona mesmo com uma falha em todas as linhas
Figueiredo – 2016
Triple Modular Redundancy (TMR)
Por que temos tres votadores por nível?
um seria suficiente para corretude
Votadores podem falhar!
Precisamos de redundância
O que ocorre se V1 e A1 falhar?
O que ocorre de V1 e V2 falharem?
Figueiredo – 2016
Tipos de Falhas
Sistemas podem falhar por muitas razões
dependência entre as partes
Classificação dos tipos de falha para ataca-las
Mais difícil de lidar!
Figueiredo – 2016
Falhas Bizantinas
Outro nome para “Arbitrary Failures”
nome vem de histórias de traições e corrupção no
Império Bizantino
Modelo mais geral de falha, que também
inclui comportamento malicioso
“qualquer coisa pode acontecer”
Respostas podem ser incorretas, inclusive de
forma proposital (maliciosa)
ex. advesário que deseja parar o sistema
Veremos em breve como lidar com estas falhas!
Figueiredo – 2016
Grupos Redundantes
Como lidar com falhas em
processos (ou subsistemas)?
Redundância!
Ideia: grupo de processos redundantes que
se comunicam, executam a mesma função
“computadores” distintos, que podem responder
um pelo outro (redundância)
ex. grupo de discos, grupo de SGBDs, etc
Outros processos interagem com o grupo
(sem saber que é um grupo)
transparente para outros processos
Figueiredo – 2016
Falha em Grupos Redundantes
Quantos processos podem falhar
e grupo continuar operacional?
Depende do tipo de falha!
Crash failure: basta 1 operacional no grupo com k,
sistema tolera k-1 falhas
Bizantine failure: precisamos garantir que os
processos em falha não vão atrapalhar o grupo
ideia: usar consenso no grupo (maioria decide)
maioria = k+1, falhas =k → grupo = 2k + 1
sistema tolera k falhas bizantinas em grupo de
tamanho 2k+1
Figueiredo – 2016
Acordos em Sistemas Distrib.
Processos em sistemas distribuídos precisam
chegar a acordos
ex. definição de um coordenador, definição de
uma transação (commit/abort), etc
Problema relativamente fácil, ignorando falhas
ou considerando alguns tipos de falha
ex. 2PC tolera alguns tipos de falha
E falhas bizantinas?
É possível chegar a um acordo
neste caso?
Figueiredo – 2016
Acordos com Falhas Bizantinas
Problema: conjunto de processos podem chegar a
um consenso em tempo finito na presença de outros
processos em falha bizantina?
inicialmente estudado por Lamport et al. em 82
Resposta depende das premissas sobre processos,
tipo de comunicação e atrasos
Não é possível
chegar a um
consenso!
Figueiredo – 2016
Protocolo de Acordo Bizantino
Assumir comunicação síncrona, comunicação
unicast, com FIFO e atraso limitado
Problema: N processos, cada um com um valor vi
todo processo operacional deve conhecer vi de
cada processo operacional
Algoritmo proposto por Lamport et al. em 82
1) Cada processo envia a cada outro seu número
2) Cada processo transmite os números recebidos
(vetor de números)
3) Usando vetores recebidos, processo verifica para
cada componente se valor é maioria
Figueiredo – 2016
Exemplo – Fase 1
N=4, 1 processo em falha bizantina (processo 3)
vi = identificador do processo
Fase 1: cada processo
envia seu número a cada
outro processo
Processo 3 envia qualquer
valor aos outros
Todos recebem antes de
iniciar Fase 2 (síncrono, em
ordem e retardo máximo)
Figueiredo – 2016
Exemplo – Fase 2
Valores recebidos
(em ordem)
P1 : (1,2,x,4)
P2 : (1,2,y,4)
P3 : (1,2,3,4)
P4 : (1,2,z,4)
Fase 2: cada processo
envia vetor e números
recebido a cada processo
Processo 3 pode enviar
qualquer coisa a qualquer
processo (inconsistente
com o que de fato recebeu)
Por que precisamos da
fase 2? Por que P1 não
conclui com os valores que
recebeu?
Figueiredo – 2016
Exemplo – Fase 3
Vetores recebidos
P1
P2 : (1,2,y,4)
P3 : (a,b,c,d)
P4 : (1,2,z,4)
P2
P1 : (1,2,x,4)
P3 : (e,f,g,h)
P4 : (1,2,z,4)
P4
P1 : (1,2,x,4)
P2 : (1,2,y,4)
P3 : (i,j,k,l)
Fase 3: usando os vetores recebidos, cada processo
verifica se há uma maioria posição do vetor
Caso positivo, utiliza este número para o processo i,
caso negativo, indefinido
Vetores construídos
P1 : (1,2,-,4)
P2 : (1,2,-,4)
P4 : (1,2,-,4)
Todos os três concordam nos
valores!
Funciona independente dos
valores reportados por P3!
Figueiredo – 2016
Propriedades
Neste caso funcionou, N=4, F=1
Mas quando acordo pode ser obtido?
Se k estão em falha bizantina, precisamos de
2k+1 operacional
de 3k+1 processos apenas k podem estar em
falha bizantina (regra dos 2/3)
Não é possível, caso contrário
ex. N=3, F=1 não é possível chegar a um acordo!
Consensus Protocols foi e ainda é tema de
estudo na academia
problema difícil, mais ainda com premissas
menos rigorosas
Figueiredo – 2016