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)
  Primeiro Semestre de 2018: o Prof. Elias está ministrando a disciplina para a graduação e a pós-graduação

Atenção: data de entrega do TP2 adiada para o dia 24 de maio de 2018

Atenção: não haverá aula nos dias 8 e 10 de maio de 2018

Atenção: o Trabalho Prático Fase 2 foi divulgado! Prazo 1 mês: 10 de abril de 2018 é a entrega!

Atenção: não haverá aula nos dias 17 e 19 de abril de 2018.

Atenção: o Trabalho Prático Fase 1 foi divulgado! Prazo 2 semanas: 29 de março de 2018 é a entrega!

Atenção: aula de 15 de março de 2015 será no Laboratório 2!

Atenção: não haverá aula nos dias 27/fevereiro/2018 (terça) nem 01/março/2018 (quinta)

Atenção: a disciplina começa na primeira aula do semestre, terça-feira dia 19/fevereiro/2018

Todos os AVISOS serão postados aqui.

Horário: Terças & Quintas, 13:30 -> 15:00hs Sala: PC05

Prova 1: 12 de abril de 2018 (quinta-feira, na hora da aula, na sala de aula) Resultado
Os alunos estão convidados a ver as correções a partir do dia 25 de abril de 2018.

Prova 2: 21 de junho de 2018 (quinta-feira, na hora da aula, na sala de aula)

Prova Final: 3 de julho de 2018 (terça-feira, na hora da aula, na sala de aula)

Avaliação: 2 provas de 35 pontos cada; trabalho prático em fases valendo no total 30 pontos.

O atendimento a dúvidas é feito ao término da aula, o professor conta com a compreensão dos alunos para evitarem consultas por e-mail. Sempre há tempo depois de cada aula! Se detectarmos então a necessidade, podemos também agendar um horário para atendê-lo na minha sala.

  O Trabalho Prático

O trabalho deve ser feito individualmente!
Atenção: Data para disponibilizar o trabalho: 29 de março de 2018 (quinta-feira) O prazo para fazer o trabalho é de quase 3 semanas, este prazo não será prorrogado!

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP* SISDIS 2018-1"

FASE 2

Especificação: Implemente o algoritmo VCube no ambiente de simulação SMPL, e mostre resultados para diversos valores de N e diversos eventos - um evento de cada vez, um evento só ocorre depois do evento anterior ser diagnosticado. Para cada evento mostre claramente o número de testes executados e a latência para completar o diagnóstico do evento. Cada nodo mantém o vetor STATE[0..N-1] de contadores de eventos, inicializado em -1 (estado unknown). Assume-se que os nodos são inicializados sem-falha, a entrada correspondente ao nodo no vetor STATE[] do testador é setada para zero. Ao descobrir um novo evento em um nodo testado, o testador incrementa a entrada correspondente no vetor STATE[].

Para a transferência de informações de diagnóstico lembre-se da estratégia do VCube: quando um nodo sem-falha testa outro nodo sem-falha obtém informações sobre "novidades". Basta comparar os vetores STATE para saber se o testado tem alguma novidade.

Importante: em cada intervalo de testes todos os testadores executam todos os testes assinalados.

Atenção: Data para disponibilizar o trabalho: 10 de maio de 2018 (quinta-feira) O prazo para fazer o trabalho é de 1 mês, este prazo não será prorrogado!

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.
    Veja este programa exemplo para ilustrar a criação de um bom log.

FASE 1

Especificação: Implemente o algoritmo Adaptive DSD no ambiente de simulação SMPL, e mostre resultados para diversos valores de N e diversos eventos - um evento de cada vez, um evento só ocorre depois do evento anterior ser diagnosticado. Para cada evento mostre claramente o número de testes executados e a latência para completar o diagnóstico do evento. Cada nodo mantém o vetor STATE[0..N-1] de contadores de eventos, inicilizado em -1 (estado unknown). Assume-se que os nodos são inicializados sem-falha representado por 0; o estado falho é representado por 1.

Disponibilize no site, além do programa SMPL que implementa o Adaptive-DSD como definido acima, os programas que implementam as Tarefas 0 a 4 feitas em laboratório.

Atenção: Data para disponibilizar o trabalho: 29 de março de 2018 (quinta-feira) O prazo para fazer o trabalho é de apenas 2 semanas, este prazo não será prorrogado!

  Informações sobre a Disciplina Sistemas Distribuídos
  Pré-Requisitos

Mestrado e Doutorado em Informática: é pré-requisito para a disciplina do Mestrado, Sistemas Distribuídos (CI721), o aluno ter domínio de Programação de Computadores com a linguagem C em ambiente Unix (Linux).

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 os seguintes.

No 1o semestre de 2018 os tópicos serão os seguintes:

  1. Introdução aos Sistemas Distribuídos

  2. Modelos Temporais: Sistemas Síncronos, Assíncronos e Parcialmente Síncronos

  3. Confiança no Funcionamento de Sistemas (Dependability) e Modelos de Falhas

  4. Diagnóstico em Nível de Sistema

  5. Ordenação de Eventos e Relógios Lógicos

  6. Difusão Confiável, FIFO, Causal e Atômica

  7. Detectores de Falhas

  8. Eleição de Líder

  9. Consenso

Em outros semestres os tópicos já incluiram:

  1. Exclusão Mútua Distribuída

  2. O Problema dos Generais Bizantinos

  3. Transações Atômicas Distribuídas

  4. Replicação Distribuída

  5. Comunicação em Grupo (Group Membership)

  6. Sincronização de Relógios

  7. CheckPointing & Rollback

  8. Particionamento & Recuperação de Redes de Topologia Arbitrária

  9. Simulação de Sistemas Distribuídos

  10. Segurança no Contexto de Sistemas Distribuídos

  Biblioteca SMPL
  Simulation Programming Language - Biblioteca C, C++ para Simulação baseada em Eventos Discretos

smpl.c         smpl.h         rand.c         makefile


hipercubo.c         cisj.c

  Referências

Não há um único livro texto para esta disciplina. Alguns dos tópicos aparecem em livros, outros em artigos. Uma lista de livros sugeridos segue abaixo:

  • A. D. Kshemkalyani, M. Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge U. Press, 2008.
  • C. Cachin, R. Guerraoui, L. Rodrigues, Introduction to Reliable and Secure Distributed Programming, Springer, 2011.
  • S. Mullender (Editor), Distributed Systems, 2nd Edition, ACM Press, 1993.
  • P. Jalote, Fault Tolerance in Distributed Systems, Prentice-Hall, 1994.
  • D. K. Pradhan (Editor), Fault-Tolerant Computer System Design, Prentice-Hall, 1996.
  • B. Charron-Bost, F. Pedone, A. Schipper (Editors) Replication: Theory and Practice, Springer, 2010.

No primeiro semestre de 2018 vamos usar na segunda parte da disciplina o livro "Introduction to Reliable Distributed Programming" que está disponível em versão digital na Biblioteca da UFPR. Para acessar o pdf faça:

  1. Acesse o Portal da UFPR
  2. No campo "Busca Integrada ao Acervo UFPR", digite: "Introduction to Reliable Distributed Programming"
  3. Verifique se o seletor está selecionado "Todo o Conteúdo"
  4. Pressione o botão "Pesquisar"
  5. Na nova guia que abrir, selecione o primeiro item da resultante da busca
  6. Role a página um pouco até encontrar o campo "Acesso online:"
  7. Clique no link ao lado deste campo recém encontrado
  8. Uma nova aba abrirá, nesta clique no botão Download Book(PDF, 2432 KB)

Alguns dos artigos importantes neste semestre são:

  • Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, Carl E. Landwehr, "Basic Concepts and Taxonomy of Dependable and Secure Computing," IEEE Transations on Dependable and Secure Computing, pp. 11-33, Vol. 1, No. 1, 2004.
  • Ronald P. Bianchini Jr., Richard W. Buskens, "Implementation of On-Line Distributed System-Level Diagnosis Theory," IEEE Transactions on Computers, pp. 616-626, Vol. 41, No. 5, 1992.
  • Fred B. Schneider, "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial," ACM Computing Surveys, pp. 299-319, Vol. 22, No. 4, 1990.


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