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 sem a
necessidade de arcar com o custo de construílo
• Alternativa à modelagem
– Permite analisar situações que não podem ser
modeladas de forma tratável/representativa
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
• A prova é por contradição
– se existir um tal protocolo deve envolver 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
– 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, construindo um modelo simples
e informal, 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
– E se o canal fosse fair-lossy?
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
– parada (failstop), crash, omissão
– desempenho
– valor
– arbitrária (Bizantina)
• restrições obtidas através de autenticação
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
– 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)
Detectores de falhas não confiáveis
• Uma outra abordagem é definir o
sincronismo extra necessário em termos de
propriedades que precisam ser satisfeitas
– Classes de detectores
• Abrangência: que falhas são detectadas
• Exatidão: que erros podem acontecer
– Sincronismo no tempo
• Global Stabilization Time
– Sincronismo no espaço
• Wormholes
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