Sistemas Distribuídos
Walfredo Cirne & Fubica Brasileiro
http://walfredo.dsc.ufcg.edu.br/cursos/2005/distsis20052
Aula 5: Modelos de Sistemas Distribuídos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o
consentimento dos mesmos.
Modelos para sistemas
distribuídos
• 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”);
• seguida de análise - matemática ou lógica - para inferir
propriedades.
Modelagem x experimentação
• modelagem oferece mais “controle” sobre a
intuição adquirida;
• modelagem só é útil se o modelo
caracteriza o objeto de estudo de forma
apropriada;
• experimentação é muito importante para
validar modelos.
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 é 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
Simulação
• Alternativa à experimentação
– Mais próximo do sistema real, com um custo
muito menor que o sistema real
• Alternativa à modelagem
– 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
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
• Ambas 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
algumas 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)
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
• Usar uma coleção de modelos
– Processadores com semântica de falha controlada
– Canais confiáveis