Algoritmos e Sistemas Distribuídos
Objetivos
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
Inglê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.
Método de avaliação
2 testes teóriocos (ou exame que substitui os dois testes): 45%
projecto (em três fases, realizado em grupos de 3 alunos): 45%
Trabalhos para casa (indicados nas aulas teóricas e entregues em mão nas aulas teóricas): 10%
As componentes são arrendondadas às centésimas, a nota final é arredondada às unidades.
Conteúdo
1. Modelos de Computação Distribuída:
1. Modelação de processos, falhas, primitivas criptográficas.
2. Modelos temporais: Sincrono, Assíncrono and Sincronia Eventual.
3. Primitivas de Comunicação: (melhor-esforço, exactamente uma vez, broadcast).
2. Sistemas entre-pares (P2P):
1. Redes sobrepostas não estruturadas.
2. Protocolos epidémicos.
3. Redes sobrepostas estruturadas.
4. Hashing consistente e encaminhamento ao nível aplicacional.
5. Casos de Estudo.
3. Acordo:
1. Consensus em sistemas síncronos.
2. Consensus em sistemas assíncronos & FLP.
3. Paxos e algumas variantes.
4. Replicação e Tolerância a Falhas:
1. Especificação de sistemas replicados.
2. Replicação activa e Replicação passiva.
2. Consistência forte: Replicação de máquina de estados.
3. Consistência fraca: Teorema de CAP, consistência eventual, consistência causal.
4. Casos de Estudo.
5. Transações Distribuídas:
1. Commit em duas fases.
2. Commit em três fases.