Algoritmos Distribuídos
1ª Lista de Exercícios
Antonio Alfredo Ferreira Loureiro
[email protected]
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
1
Exercício 1

Suposições:




Rede P2P
Pelo menos quatro processos e um processo monitor PM
Cada processo tem uma cor, que é a resposta que deve ser
dada a uma requisição
Dois cenários:
 Sem falha
 Com falha bizantina

Como esse sistema funciona:


Cada processo gera uma solicitação para um outro
processo
Com probabilidade p esse processo responde e com
probabilidade 1 – p envia essa mesma solicitação a um dos
dois outros processos
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
2
Exercício 1

O que se pede para os dois casos:




Geração e exibição das observações pelo processo monitor
PM (você deve definir como isso será feito)
Cada processo pode enviar no máximo r requisições (este é
um parâmetro configurável mas deve ser pelo menos 3)
Avaliação do desempenho desse sistema variando a
probabilidade p (você deve definir que valores serão
usados, mas sugere-se pelo menos dois valores diferentes)
Avaliação de uma propriedade global sobre o reticulado que
representa as possíveis computações (você deve definir
essa propriedade global) e indicar se ela é satisfeita ou não
 Observe que há um problema combinatório do ponto de
vista de avaliação
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
3
Exercício 1

Para o caso sem falhas:


Avalie se o sistema entra em um estado de deadlock
(assuma que isso ocorre quando um processo qualquer
envia uma requisição ao processo que disparou inicialmente
esse pedido)
Para o caso com falha bizantina:


Defina a escolha do processo malicioso
Defina como será o comportamento desse processo ao
longo do tempo
 Observe novamente que há um problema combinatório do
ponto de vista de avaliação
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
4
Outros exercícios
 Avalie o custo no pior caso de troca de mensagens dos
diferentes cenários. Idealmente, identifique esse custo
em função da probabilidade p.
 É possível projetar esse sistema sem que ele entre num
estado de deadlock? Se sim, como? Se não, por que?
 Qual é o custo de espaço, no pior caso, para gerar o
reticulado pelo proceso monitor PM?
 Dê um exemplo de uma propriedade liveness que
poderia ser avaliada pelo proceso monitor PM.
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
5
Prazo e Entrega

Código desse sistema pode ser escrito em qualquer linguagem
disponível no ambiente computacional do DCC/UFMG

Gere:



Arquivo zip com todo o seu sistema e um arquivo leiame com
informações sobre a compilação desse sistema
Arquivo no formato pdf respondendo às questões apresentadas e
uma breve descrição de como o seu sistema pode ser executado
Envie esse arquivo até o dia 5/10/2009 às 00:01 para o
endereço eletrônico [email protected], com
assunto [AD-TP1] “seu nome”
UFMG/DCC  Algoritmos Distribuídos ― Lista de Exercícios 1
6