S I S T E M A S     D I S T R I B U Í D O S

Disciplina do Mestrado/Doutorado em Informática e Optativa do BCC/IBM

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

  Disciplina INFO7046 (Mestrado/Doutorado) e CI1088 (Optativa Bacharelado em Ciência da Computação)
  2o período de 2024: o Prof. Elias não está ministrando esta disciplina

Todos os AVISOS serão postados aqui.

Horário: terças e quintas, 13:30hs Sala:

Prova 1: de abril de 2025 (quinta-feira, na hora da aula, sala -)

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

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

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

  As Aulas - cada módulo pode cobrir várias aulas

Módulo 1   Módulo 2   Módulo 3   Módulo 4   Módulo 5 e 6   Módulo 7   Módulo 8   Módulo 9  
Módulo 10   Módulo 11   Módulo 12   Módulo 13   Módulo 14   Módulo 15   Módulo 16  

Na seção 7 deste artigo estão definidos os detectores de falhas vRing e vCube, além da força-bruta Vejam também os slides sobre vRing e vCube, além dos cadernos com anotações das aulas!

  O Trabalho Prático: a ser divulgado! Prazo de entrega 3 semanas, dia de de 2025 (quinta-feira)

Atenção: a data limite para disponibilizar o trabalho é de 2025 (não serão aceitos trabalhos fora do prazo!)

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

Alunos de pós-graduação devem fazer o trabalho individualmente, alunos de graduação podem fazer em dupla.

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.

Neste período 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. O Consenso e os Detectores de Falhas

  5. Algoritmos do Anel Virtual e Hipercubo Virtual: vRing & vCube

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

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

  8. Eleição de Líder em Sistemas Parcialmente Síncronos

  9. Replicação Máquina de Estados

  10. O Algoritmo de Consenso Paxos

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. Ordenação de Eventos e Relógios Lógicos

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

  7. Sincronização de Relógios

  8. CheckPointing & Rollback

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

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

Neste período vamos usar em 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.
  • Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process," Journal of the ACM (JACM), Vol. 32, No. 2, pp. 374-382, 1985.
  • Tushar D. Chandra, Sam Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems," Journal of the ACM (JACM), Vol. 43, No. 2, pp. 225-267, 1996.
  • Michel Raynal, "A Short Introduction to Failure Detectors for Asynchronous Distributed Systems," ACM SIGACT News, Vol. 36, No. 1, pp. 53-70, 2005.
  • Elias P. Duarte Jr., Luiz A. Rodrigues, Edson T. Camargo, Rogerio Turchetti, "A Distributed System-level Diagnosis Model for the Implementation of Unreliable Failure Detectors," CoRR abs/2210.02847, 2022. [arXiv link with pdf]
  • 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.
  • Elias P. Duarte Jr., Takashi Nanya, "A Hierarchical Adaptive Distributed System-Level Diagnosis Algorithm," IEEE Transactions on Computers, Vol. 47, No. 1, pp. 34-45, 1998.
  • Elias P. Duarte Jr., Luis C. E. Bona, Vinicius K. Ruoso, "VCube: A Provably Scalable Distributed Diagnosis Algorithm," Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA), at The Supercomputing Conference 2014 (SC'2014), pp. 1-8, New Orleans, USA, 2014.
  • 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.