Algoritmos e Sistemas Distribuídos

Objectivos

A unidade curricular (UC) visa consolidar e desenvolver os conhecimentos na área de Sistemas Distribuídos para a compreensão e construção de sistemas distribuídos e descentralizados complexos. Procura-­se um bom domínio dos problemas e ideias fundamentais que estão na base do desenho de sistemas atuais, de uso corrente, e das técnicas que potencialmente serão importantes para os sistemas a desenvolver no futuro.

A UC tem uma forte componente algorítmica, mas é também acompanhada de projetos de programação que coloca em prática os conceitos fundamentais que são nela ensinados, permitindo aos alunos tomarem consciência sobre algumas subtilezas relacionadas com a implementação de algoritmos aprendidos na UC.

Saber:

• Conceitos de base para a análise e síntese de algoritmos distribuídos.

• Abstrações fundamentais para a construção de sistemas distribuídos e a sua realização algorítmica.

• Técnicas para melhorar a fiabilidade e a escalabilidade dos sistemas distribuídos.

Saber Fazer:

• Construção de algoritmos distribuídos e a sua aplicação no desenvolvimento de sistemas distribuídos.

• Análise de algoritmos distribuídos.

• Programação de sistemas distribuídos.

Caracterização geral

Código

10644

Créditos

6.0

Professor responsável

João Carlos Antunes Leitão, Nuno Manuel Ribeiro Preguiça

Horas

Semanais - 4

Totais - 56

Idioma de ensino

Português

Pré-requisitos

Conhecimentos fundamentais de sistemas distríbuidos e programação em Java.

Bibliografia

Bibliografia de base:

• N. Lynch. Distributed Algorithms Morgan Kauffman, 1996.

• C. Cachin, R. Guerraoui, L. Rodrigues "Introduction to Reliable and Secure Distributed Programming", 2nd edition, Springer, 2011.

Conjunto de artigos selecionados.

Bibliografia complementar:

• H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Ed.) . Wiley 2004.

• S. Mullender (editor) Distributed Systems, Second Edition, ACM Press, Addison-­Wesley, MA, 1994.

• A.S. Tanenbaum and M. van Steen. Distributed Systems. Principles and Paradigms. (2nd Ed.) Prentice Hall, 2007.

• Rodrigo Rodrigues, Peter Druschel. Peer-­to-­Peer Systems. Communications of the ACM. Vol. 53 No. 10, Pages 72-­82.

Método de ensino

Aulas teóricas com exposição de conteudos e solução de problemas/construção de algorithmos colaborativa.

Aulas laboratoriais dedicadas a casos de estudo e mecanismos de programação e desenvolvimento de algorithmos e sistemas distríbuidos com enfase num projeto em grupo.

Trabalhos de casa individuais.

(Todas as atividades letivas vão decorrer on-line devido à pandemia COVID-19)

Método de avaliação

2 testes teóricos (ou exame que substitui os dois testes): 45%

  - cada teste tem o mesmo peso nesta componente.

  - os testes seram presenciais no caso de existirem condições para tal.

  - sendo presenciais os alunos tem direito a consulta de duas páginas A4 manuscritas em cada teste com qualquer conteudo que o aluno entenda. Estas páginas devem ser identificadas com nome e número e tem de ser entregues no final do teste.

projecto (em duas fases, realizado em grupos de 3 alunos): 45%

  - a primeira fase tem um peso de 40% nesta componente e a segunda um peso de 60%.

Trabalhos para casa individuais  (indicados nas aulas teóricas e entregues antes da aula teóricas seguinte): 10%

  - cada trabalho de casa tem o mesmo peso nesta componente.

As componentes são arrendondadas às centésimas, a nota final é arredondada às unidades.

A unidade curricular tem Frequência obrigatória. Frequência requer uma classificação >= 8.5 no projeto.

Conteúdo

1. Modelos de Computação Distribuída:

    1.1. Modelação de processos, falhas, primitivas criptográficas.

    1.2. Modelos temporais: Sincrono, Assíncrono and Sincronia Eventual.

    1.3. Primitivas de Comunicação: (melhor-esforço, exactamente uma vez, broadcast).

2. Sistemas entre-pares (P2P):

    2.1. Redes sobrepostas não estruturadas.

    2.2. Protocolos epidémicos.

    2.3. Redes sobrepostas estruturadas.

    2.4. Hashing consistente e encaminhamento ao nível aplicacional.

    2.5. Casos de Estudo.

3. Acordo:

    3.1. Consensus em sistemas síncronos.

    3.2. Consensus em sistemas assíncronos & FLP.

    3.3. Paxos e algumas variantes.

4. Replicação e Tolerância a Falhas:

    4.1. Especificação de sistemas replicados.

    4.2. Replicação activa e Replicação passiva.

    4.3. Consistência forte: Replicação de máquina de estados.

    4.4. Consistência fraca: Teorema de CAP, consistência eventual, consistência causal.

    4.5. Casos de Estudo.

5. Transações Distribuídas:

    5.1. Commit em duas fases.

    5.2. Commit em três fases.

Cursos

Cursos onde a unidade curricular é leccionada: