Sistemas Distribuídos
Francisco Brasileiro
Aula 2: Modelos de Sistemas Distribuídos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o
consentimento dos mesmos.
Como aumentar a nossa intuição
para resolver problemas?
• Experimentação
– abordagem prática baseada no acúmulo de informação
– pode ser usada para construir coisas similares a outras
já construídas
• Modelagem e análise
– abordagem teórica baseada na simplificação do objeto
de estudo (“mundo real”) = criação do modelo
– seguida de análise - matemática ou lógica - para inferir
propriedades
• Modelagem e simulação
– criação do modelo
– simulação do modelo no computador
Trade-offs
• modelagem oferece mais “controle” sobre a
intuição adquirida
• modelagem só é útil se o modelo caracteriza o
objeto de estudo de forma apropriada
• simulação é mais poderosa e menos genérica que
análise
• experimentação é muito importante para validar
modelos
Simulação
• Alternativa à experimentação
– Mais próximo do sistema real, com um custo
muito menor que o sistema real
• Alternativa à analise
– Permite analisar situações que não podem ser
modeladas de forma tratável/representativa
• Precisa ser validada
– Testes automáticos são fundamentais para se
reduzir a chance de bugs
O que é um bom modelo?
• Preciso
– a análise do modelo deve levar a conclusões
verdadeiras sobre o objeto de estudo
• Tratável
– um modelo que não permite a execução de
uma análise ou simulação é inútil
– em um modelo tratável, as regras que
governam o comportamento dos atributos do
modelo são normalmente definidas através de
fórmulas matemáticas ou lógicas
Que respostas um bom modelo
pode dar?
• Viabilidade
– Que classes de problemas podem ser resolvidos
• Custo
– Para as classes que podem ser resolvidas, quão cara
(em termos de recursos, tempo de processamento, etc.)
uma solução precisa ser
• Perfomance
– Como uma solução se compara com outra
• As respostas têm valor prático e teórico
Modelos para sistemas
distribuídos: um exemplo
• O problema da coordenação
– Dois processos, A e B, se comunicam através
de troca de mensagens. Nenhum processo
falha, mas o canal de comunicação pode perder
mensagens. Construa um protocolo que
permita que ou a ação a ou a ação b possa
ocorrer, mas (i) A e B executam a mesma ação,
e (ii) nenhum executa ambas as ações.
Prova de impossibilidade
• suponha que existe um protocolo que resolve o problema
• tal protocolo envolve troca de mensagens entre A e B
• vamos escolher o protocolo que resolve o problema com o
número mínimo de trocas de mensagens (i.e. não existe
um protocolo que use menos mensagens) e, sem perda de
generalidade, assumir que m, a última mensagem enviada
no protocolo, foi enviada por A
• mas m poderia ter sido perdida!!!
• as ações tomadas por A e B não dependem de m, portanto
m é supérflua e é possível construir um protocolo com uma
mensagem a menos; uma contradição!
Vamos entender melhor o que
fizemos
• Nós concluímos que o Problema da Coordenação
não tem solução para o modelo definido usando
duas observações:
– todos os protocolos distribuídos entrem os dois
processos são equivalentes a uma série de trocas de
mensagens; e
– ações tomadas por um processo dependem apenas da
seqüência de mensagens recebidas.
• A partir desse modelo, nossa “intuição” sobre o
problema pode ser refinada
Quais são os atributos mais
importantes de um sistema
distribuído?
• Atrasos no escalonamento e na transmissão
de mensagens
– síncronos x assíncronos
• Semântica de falha dos componentes
– crash
– omissão
– desempenho
– valor
– arbitrária (Bizantina)
Sistemas distribuídos
assíncronos
• Nenhuma restrição em relação aos atrasos de
escalonamento e de transmissão de mensagens
• Falhas arbitrárias
• Resultado de impossibilidade de Fischer, Lynch e
Patterson (FLP, FLP85)
– Não há como obter acordo, mesmo que só um
processo falhe e mesmo que a semântica seja crash
– Esse modelo assíncrono serve para alguma coisa?
Modelo síncrono
• Características do modelo
– Atrasos máximos conhecidos para
escalonamento (s), para transmissão de
mensagens (d) e drift dos relógios locais (r)
• Sistemas construídos assumindo esse
modelo são:
– menos portáveis
– potencialmente menos seguros
Modelos parcialmente
assíncronos
• Assumem que há algum sincronismo no sistema
• Duas “escolas” principais
– Sincronismo no tempo
• Sistemas que não são sempre assíncronos
• Ex. timed asynchronous model (Fetzer&Cristian), quasesynchronous (Veríssimo&Almeida)
– Sincronismo no espaço
• Sistemas que não são completamente assíncronos
• Ex. timely computing base (Veríssimo&Casimiro&Fetzer),
GMDC (Fubica&Ely&Andrey), detectores de falha
(Chandra&Toueg)
Encapsulando Sincronismo:
Detectores de falhas
• Exatidão do detector: que erros podem acontecer
– Forte: Nenhum processo correto é considerado falho
– Fraca: Pelo menos um processo correto nunca é
considerado falho
• Abrangência do detector: que falhas são
detectadas
– Forte: Uma falha é detectada por todos os processos
– Fraca: Uma falha é detectada por pelo menos um
processo
• Eventualidade
– Condição só se aplica depois de um certo tempo
Classes de Detectores de Falha
• O detector perfeito só pode ser
implementado em um sistema síncrono!!
• Mas vários problemas podem ser resolvidos
se o sistema assíncrono for complementado
por detectores de falha imperfeitos!!
– Em particular S é de grande interesse prático
Como escolher um modelo?
• Características do ambiente de execução
– Tipos dos componentes
– Qualidade dos componentes
– Controle sobre o ambiente
• Requisitos da aplicação
– Aplicações críticas