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

Caros alunos: não haverá aula na quinta-feira dia 7/maio/2026, o professor estará em missão de projeto na UNIOESTE em Cascavel. Aproveite para começar a fazer o Trabalho Prático, abaixo!

Segue o link da nossa sala virtual: https://bbb.c3sl.ufpr.br/rooms/2hc-dif-q88-qpb/join

Caros alunos: teremos aula virtual dia 02/abril/2026, quinta-feira às 20hs: vamos estudar a biblioteca de simulação SMPL. Esteja em um computador no qual vc consegue executar programas C. Recomendo Linux. A sala será divulgada aqui um pouco antes da aula começar.

Caros alunos: não teremos aula dia 26/março/26, o Prof. Elias estará em uma conferência

Caros alunos: temos ainda mais uma nova versão do Capítulo 5, 19/março/2026.

Caros alunos: temos nova versão do Capítulo 5, 17/março/2026.

Caros alunos: fiz upload de uma nova versão do Capítulo 4 às 21hs do dia 12/março/2026

Caros alunos: temos uma nova versão do Capítulo 4, sobre detectores de falhas.

Todos os AVISOS serão postados aqui.

Horário: terças e quintas, 15:30 às 17hs Sala: PH-01

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

Prova 2: 16 de junho de 2026 (terça-feira, na hora da aula, na sala de aula)

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

Avaliação: 2 provas de 35 (ou 40, a definir) pontos cada; trabalho prático em 1 ou 2 etapas (a definir!) valendo 20 ou 30 pontos no total (respectivamente).

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  

Capítulo 1: Introdução aos Sistemas Distribuídos Capítulo 2: Tolerância a Falhas ou Dependabilidade Capítulo 3: Os Canais de Comunicação Capítulo 4: Os Detectores de Falhas Capítulo 5: Eleição de Líder

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!

TRABALHO PRÁTICO 1: Dois Algoritmos para Eleição Distribuída de Líder em Anel

Atenção: a data limite para disponibilizar o trabalho é 31 de maio de 2026 (não serão aceitos trabalhos fora do prazo!) Atenção: são mais de 3 semanas, mas organize-se pois o tempo é curto para fazer todo o necessário

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

Os trabalhos de alunos de graduação devem ser feitos em dupla, alunos do PPGInf: trabalhos individuais.

ALGORITMO 1: Implemente o algoritmo de eleição de líder com candidatos baseado em Chang-Roberts no anel (VRing). Neste algoritmo inicialmente são definidos quais processos (com identificador 0..N-1) são candidatos a líder. Todo processo mantém uma variável local Lider na qual armazenda o id do processo que considera líder. Se o processo é candidato, já assinala seu próprio id para Lider na inicialização. Um não candidato assinala o valor -1 na inicialização. Um processo que é candidato manda uma mensagem para o seguinte informando seu id e que é candidato. Vamos usar como critério para a eleição o maior identificador. Assim, se um processo recebe uma mensagem de um candidato com id maior que aquele indicado pela variável Lider, modifica o valor e repassa para frente no anel a mensagem recebida. Quando um processo recebe de volta sua própria mensagem informando que é candidato, sabe que é o líder e todos o processos do anel já receberam sua mensagem. O processo pode então descartar a mensagem e executar procedimento de lider. Mostre no log execuções do algoritmo para 1 único candidato, vários candidatos selecionados aleatoriamente e todos os N processos inicialmente candidatos. Destaque para cada execução quem é o líder eleito. Conte quantas mensagens foram necessárias em cada caso e também quanto tempo (do SMPL) foi necessário para executar a eleição.

ALGORITMO 2: Implemente o algoritmo aleatorizado para eleição de líder (Randomized Leader Election Algorithm) baseado no anel (VRing). Neste algoritmo cada processo sorteia, em cada rodada um bit aleatório. O algoritmo funciona em rodadas. Na primeira rodada todos os N processos sorteiam um valor aleatório para o seu bit. Os processos com bit = 1 são candidatos, os demais processos (i.e. com seu bit = 0) não são candidatos. Cada processo deve enviar uma mensagem que roda todo o anel informando seu id e seu bit da rodada. Na rodada seguinte, apenas os processos com bit = 1 sorteiam novo valor aleatório para o bit. Esses processos então comunicam novamente no anel o valor dos seus bits. Novas rodadas vão acontecendo até que 1 processo se transforme em líder. Execute o algoritmo para diferentes valores de N. Destaque para cada execução quem é o líder eleito. Conte quantas mensagens foram necessárias em cada caso e também quanto tempo (do SMPL) foi necessário para executar a eleição.

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

1. Relatório HTML explicando o algoritmo proposto, e descrevendo todos os itens solicitados acima (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.

TRABALHO PRÁTICO 0: Roteiro de Aprendizado Prático de Simulação

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]. A entrada do vetor State[j] indica o estado do processo j. O estado de cada processo pode ser: -1 (unknown), 0 (correto) ou 1 (falho). Inicialize (para todos os processos) 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 em um processo j, o testador atualiza a entrada correspondente no vetor State[j]. 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 do estado dos demais processos do sistema, processos do sistema exceto aqueles que testou nesta rodada, além do próprio testador.

Na página Web do Trabalho Prático, por favor incluam links para as 5 tarefas acima.

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

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.