Disciplina do Mestrado/Doutorado em Informática e Optativa do Bacharelado em Ciência da Computação

Prof. Elias P. Duarte Jr.     Departamento de Informática     UFPR

Disciplina CI721 (Mestrado/Doutorado) e CI088 (Optativa Bacharelado em Ciência da Computação)

Segundo semestre de 2011: disciplina oferecida como optativa do Bacharelado em Ciência da Computação.

Horário: Terças 19:00, Sextas, 19:00, sala PC01

Prova 1: 22 de novembro de 2011 (na hora da aula, na sala de aula)

Prova 2: 20 de dezembro de 2011 (na hora da aula, na sala de aula)
(Os alunos estão convidados a ver as provas corrigidas na semana de estudos que antecede as finais.)

Avaliação: 2 provas de 40 pontos cada; 1 trabalho prático de 20 pontos.

O Trabalho Prático: Implementação de um Algoritmo Distribuído Utilizando Simulação

Os trabalhos serão corrigidos a partir de 21/10/2011

Implemente o algoritmo Adaptive-DSD. Ao invés de utilizar o vetor Tested-UP[], use um vetor State[0..N-1]: uma entrada State[i] deste vetor é -1 se o estado do nodo i é desconhecido; 0 se o nodo i é sem-falha; 1 se o nodo i é falho. Um nodo que inicializa desconhece o estado de todos os outros, menos o seu próprio estado. Na medida em que testes são executados todos os nodos descobrem o estado dos demais.

Simule a execução de um evento: um nodo sem-falha fica falho, ou vice-versa. Repita para diversos tamanhos de sistema e eventos diferentes. Em cada caso mostre: (a) a latência, isto é tempo desde a ocorrência do evento até todos os nodos completarem seu diagnóstico; (b) o número de testes executados por todos os nodos durante o intervalo da latência.

Acrescente às páginas do TP os programas de simulação elaborados a partir das tarefas da aula prática de simulação que ocorreram na aula de laboratório.

ATENÇÃO: Na página do trabalho devem se colocados os códigos (não precisa de resultados etc, quero ver só o código destas etapas intermediárias das 3 tarefas da aula prática:

1. Tarefa 1: Cada nodo sem-falha testa o seguinte no anel.
2. Tarefa 2: Cada nodo sem-falha executa testes sequencialmente até encontrar outro nodo sem-falha.
3. Tarefa 3: Cada nodo mantém localmente o vetor State[0..N-1], e atualiza as entradas correspondentes ao testar.
4. Tarefa 4: Cada nodo sem-falha que testa outro nodo sem-falha obtém informação sobre todos os demais nodos, exceto aqueles que testou. (é o próprio Adative-DSD)

Deve ser feita uma página Web, que contém:

1. Relatório HTML explicando como o trabalho foi feito (use desenhos, palavras, o que você quiser): o objetivo é detalhar as suas decisões para implementar seu trabalho.

2. Código fonte dos programas, comentados. ATENÇÃO: acrescente a todo programa a terminação ".txt" para que possa ser diretamente aberto em um browser. Exemplos: cliente.py.txt ou servidor.c.txt

3. Log dos testes executados: mostre explicitamente diversos casos testados, lembre-se é a partir desta listagem de testes que o professor vai medir até que ponto o trabalho está funcionando.

Mestrado em Informática: o pré-requisito para a disciplina do Mestrado, Sistemas Distribuídos (CI721), é o aluno ter domínio de Programação de Computadores, com as linguagens C, C++ ou Java.

Bacharelado em Ciência da Computação: A disciplina Redes de Computadores II (CI061) é Pré-Requisito obrigatório para o aluno poder se matricular em Tópicos em Sistemas Distribuídos (CI088).

Programa

Esta é uma disciplina com ênfase em algoritmos distribuídos clássicos & tolerância a falhas. Os tópicos cobertos em cada semestre incluem: