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 CI1088 (Optativa Bacharelado em Ciência da Computação)
  Período Especial ERE2 On-Line

Atenção pessoal: o artigo e a apresentação do Prof. Luiz A. Rodrigues estão acrescentados abaixo, bem como a aula de 2/março/21 em que "refatoramos" o algoritmo de Difusão de Melhor Esforço Baseada no VCube que deve ser implementada no 3o e último TP.

Atenção pessoal: TP3 divulgado! Hoje (2/março/21) vamos "refatorar" o algoritmo de Difusão de Melhor Esforço sobre o VCube que vcs vão implementar.

Dia 25 de fevereiro de 2021: vamos ter aula do algoritmo de Best-Effort Broadcast sobre o VCube ministrada pelo autor do algoritmo, Prof. Luiz Antonio Rodrigues (UNIOESTE) - que honra! Vamos tentar o BBB do DInf, se estiver lento mudamos para o Meet: https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

Atenção pessoal: vamos tentar aula de 23/fev/21 no DInf, se estiver lento mudamos para o Meet: https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

Pessoal: aula de 18/fevereiro na sala https://meet.google.com/ity-utep-avp

Pessoal: aula de 18/fevereiro/21 confirmadíssima! Vamos estudar um algoritmo de DMutex baseado em quorums, aguardo vcs!

Atenção pessoal: nossa sala agora é permanente: https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

Pessoal: aula de 11/fevereiro na sala https://meet.google.com/ity-utep-avp

Pessoal: Aula 9 atualizada e Aula 10 incluída (10 fevereiro 21)

Caros alunos: tive uma emergência odontológica e meu dentista só vai conseguir me atender no final da tarde hoje. Peço desculpas a todos, vamos pular hoje, próxima aula quinta ou divulgo vídeo OK?

Pessoal, quinta dia 11/2/21 a aula vai ter que ser às 19:30hs, se tivermos difculdade on line será gravada.

A 1a aula de DMutex bem como os slides pdf estão disponibilizados abaixo.

Atenção pessoal: nesta quinta-feira vamos continuar a verificação das correções, com isso o TP2 só vai ser corrigido a partir de terça da semana que vem.

Alunos que já viram as correções na terça estão liberados na quinta (28/jan/21)

Atenção pessoal: notas divulgadas, todos poderão ver correções com o professor ainda esta semana

Atenção pessoal: aulas retornam dia 19/janeiro/2021, terça-feira.

Pessoal: em 14 de dezembro de 2020 atualizei os pdfs Aula 6 e Aula 7 abaixo!

Pessoal, nossa aula de 10/11/2020 vai ser na sala seguinte, por favor entrem com os nomes certinhos:
https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

A aula de 05/11/2020 vai ser uma atividade: palestra internacional sobre sistemas distribuídos da conferência AICCSA'2020. O link para a palestra às 9:30 da manhã é: https://arizona.zoom.us/j/87913675743

Pessoal, nossa aula de 03/11/2020 vai ser na sala seguinte, por favor entrem com os nomes certinhos:
https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

Atenção pessoal: as aulas começam efetivamente amanhã, dia 3/novembro/2020. Antes das 19:30hs (horário que começa a aula) eu vou colocar aqui nesta página o link da sala onde nos encontraremos. Abraços a todos!

Atenção pessoal: em brevíssimo vou colocar aqui mais informações sobre nossa disciplina remota, que vai começar dia 3/novembro/2020 às 19:30. Estou empolgadíssimo e aguardo vocês para esta aventura no mundo dos Sistemas Distribuídos!

Todos os AVISOS serão postados aqui.
Atenção pessoal, seguem as aulas em pdf (lembrando que cada unidade não corresponde exatamente a uma aula, em alguns casos ficamos mais de um dia na mesma unidade):     Aula 1     Atividade 1: Keynote AICCSA'2020     Aula 2     Atividade 1: Keynote AICCSA'2020     Aula 2         Aula 3         Aula 4         Aula 5         Aula 6         Aula 7         Aula 8         Resolução do Exercício 1 de Relógios Lógicos         Aula 9: pdf         Aula 9: video         Aula 10         Aula 11         Aula 12         Aula 13         Artigo Broadcast VCube (SBRC'2014)         Apresentação Prof. Luiz A. Rodrigues sobre Broadcast VCube    

Atenção pessoal, realizando um sonho de mais de 30 anos, começo a disponibilizar uma apostila de Sistemas Distribuídos. Por enquanto, apenas o Capítulo 1: Introdução aos Sistemas Distribuídos

Horário: Terças & Quintas, 19:30 -> 21:00hs Sala: https://bbb.c3sl.ufpr.br/b/eli-vho-ods-73z

Prova 1: 17 de dezembro de 2020 (quinta-feira, na hora da aula, on-line com o professor) Resultado
Os alunos estão convidados a ver as correções da prova e trabalho com o professor.

Prova 2: de fevereiro de 2021 (quinta-feira, na hora da aula, on-line)

Prova Final: de fevereiro de 2021 (terça-feira, na hora da aula, on-line)

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


  O Trabalho Prático

TRABALHO PRÁTICO 0

Tarefas para aprender a usar nossa ferramenta de simulação, o SMPL.

Tarefa 0: digitar, compilar e executar o programa exemplo, tempo.c

Tarefa 1: Fazer cada um dos processos testar o seguinte no anel. Implemente o teste com a função status() do SMPL e imprimir (printf) o resultado de cada teste executado. Por exemplo: “O processo i testou o processo j correto no tempo tal.”

Tarefa 2: Cada processo correto executa testes até achar outro processo correto. Lembre-se de tratar o caso em que todos os demais processos estão falhos. Imprimir os testes e resultados.

Tarefa 3: Cada processo mantém localmente o vetor State[N]. Inicializa o State[N] com -1 (indicando estado “unknown”) para todos os demais processos e 0 para o próprio processo. Nesta tarefa ao executar um teste, o processo atualiza a entrada correspondente no vetor State[N]. Em cada intervalo de testes, mostre o vetor State[N].

Tarefa 4: Quando um processo correto testa outro processo correto obtém as informações de diagnóstico do processo testado sobre todos os processos do sistema exceto aqueles que testou nesta rodada, além do próprio testador.

Na página Web do Trabalho Prático 1, por favor incluam links para as 5 Tarefas indicadas na aula de laboratório (tempo.c mais 4 seguintes). Para cada uma das Tarefas inclua um pequeno log, mostrando que a Tarefa executou corretamente.

TRABALHO PRÁTICO 1

Especificação: Implemente o algoritmo VRing no ambiente de simulação SMPL, e mostre resultados para diversos valores de N e diversos eventos - um evento em um processo 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 processos são inicializados sem-falha, a entrada correspondente ao próprio processo 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 VRing: quando um processo sem-falha testa outro processo sem-falha obtém informações sobre os estados de todos os processos que não testou no intervalo de testes corrente. É importante comparar as entradas correspondentes dos vetores STATE (testador e testado) para saber se o testado tem alguma novidade. Se o valor da entrada for maior no vetor STATE do processo testado, então copia a informação.

Atenção: Data para disponibilizar o trabalho: 15 de dezembro de 2020 (terça-feira)

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP1 SISDIS 2020-ERE2"

TRABALHO PRÁTICO 2

Especificação: implemente as duas versões do VCube usando SMPL. Lembre-se: na versão 1, em cada intervalo de testes, cada processo correto executa testes em 1 cluster sequencialmente até encontrar um processo correto, ou testar todos os processos falhos. Tendo testado um processo correto, obtém informações sobre os processos restantes do cluster (aqueles que não testou) a partir do processo correto testado. Na versão 2, são definidos de antemão com o uso da função C(i,s) executada por e para todos os processos quem são os testadores de quais processos. Esta estratégia garante NlogN testes a cada logN rodadas de testes. Na versão 2, ao testar um processo correto, o testador obtém informações sobre qualquer “novidade” que o processo testado tenha. Sugestão para implementar na simulação (em um sistema real não seria boa ideia): simplesmente compare os vetores State do testador com o testado procurando entradas com maior valor.

Vamos manter a mesma definição de rodada para as duas versões: todos os processos corretos executaram testes em 1 de seus clusters.

Mostre resultados para diversos valores de N e diversos eventos - um evento em um processo 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 processos são inicializados sem-falha, a entrada correspondente ao próprio processo no vetor STATE[] do testador é setada para zero. Ao descobrir um novo evento em um processo testado, o testador incrementa a entrada correspondente no vetor STATE[].

Atenção: Data para disponibilizar o trabalho: 26 de janeiro de 2021 (terça-feira) (está sendo especificado 15 de dezembro de 2020)

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP2 SISDIS 2020-ERE2"

TRABALHO PRÁTICO 3

Especificação: implemente o algoritmo de Best-Effort Broadcast sobre o VCube. O programa deve receber como entradas: o processo fonte do broadcast, o número de nodos do sistema e uma lista de nodos para falhar durante a execução. Deve ser possível tanto definir processos que estarão falhos durante toda a execução, como processos que falham em momentos específicos.

Além disso, deve ser possível fazer uma execução com escalonamento de falhas definidas aleatoriamente. Em outras palavras: quando vc executa o algoritmo usando esta abordagem, processos escolhidos aleatoriamente vão falhar entre o início e o fim do broadcast.

No relatório, explique cuidadosamente como vc implementou cada função e o algoritmo como um todo. Mostre os logs com cuidado, de forma que seja possível ver com clareza o progresso do broadcast, inclusive após a ocorrência de falhas. Um caso que deve estar nos logs é o seguinte: um processo aguarda o ACK de outro processo. Em seguida (antes de receber o ACK) o processo que deveria mandar o ACK falha. Agora o processo que aguardava o ACK deve mandar uma nova mensagem para outro processo do cluster do processo que falhou. Deve ser fácil visualizar toda esta situação no seu log!

Atenção: Data para disponibilizar o trabalho: 18 de março de 2021 (quinta-feira)

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP3 SISDIS 2020-ERE2"

O trabalho deve ser feito individualmente!

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.
  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 2020 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. VRing: Um Algoritmo Distribuído em Anel

  5. VCube: Um Algoritmo Distribuído Hierárquico

  6. Relógios Lógicos e Causalidade

  7. Exclusão Mútua Distribuída

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

  9. Detectores de Falhas

  10. Eleição de Líder

  11. Consenso

  12. Difusão Atômica Baseada em Consenso

Em outros semestres os tópicos já incluiram:

  1. O Problema dos Generais Bizantinos

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

  3. Replicação Distribuída

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

  5. Sincronização de Relógios

  6. CheckPointing & Rollback

  7. Diagnóstico em Nível de Sistema

  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

VCube
Interface para o VISUAL VCUBE

  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 2020 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.