Algoritmos e Sistemas Distribuídos
Código
10644
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Rodrigo Seromenho Miragaia Rodrigues
Horas semanais
4
Total de horas
56
Língua de ensino
Português
Objectivos
A unidade curricular (UC) visa consolidar e desenvolver os conhecimentos na área de Sistemas Distribuídos para a compreensão e conceção de sistemas descentralizados complexos. Procura-se um bom domínio das ideias fundamentais que estão na base 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 põem em prática os conceitos fundamentais que são nela ensinados.
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:
• Conceçã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.
Conteúdo
1. Modelos de computação distribuída
1.1. Modelos de processos, falhas, primitivas criptográficas e comunicação.
1.2. Modelo síncrono, assíncrono, e parcialmente síncrono.
2. Replicação e tolerância a faltas, e respectivas abstracções fundamentais
2.1. Comunicação em difusão (broadcast)
2.2. Estudo das abstracções de suporte à replicação: consenso e variantes
2.3. Protocolos de replicação com quóruns. Replicação Bizantina.
2.4. Especificação dos sistemas de replicação: diferentes modelos de consistência
3. Escalabilidade
3.1. Sistemas peer-to-peer
3.2. Outras técnicas para a construção de sistemas escaláveis. Caso de estudo do HDFS.
4. Transacções distribuídas
4.1. Two-phase commit
4.2. Three-phase commit
4.3. Técnicas de logging para tolerância a faltas
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 selecionado.
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 avaliação
Método de avaliação dos alunos
Componentes da avaliação
- Avaliação da frequência cujo peso na nota final é de 50%.
- Dois testes ou um exame final cujo peso na nota final é de 50%. Os testes têm ambos igual peso.
- A nota final é aproximada ao valor, as notas intermédias à décima de valor.
Avaliação da frequência
A avaliação de frequência tem duas componentes obrigatórias:
- Realização de um trabalho prático por fases em grupos de três pessoas.
- Realização de um teste prático individual, também faseado, focado no trabalho prático, a realizar ao longo de um sub-conjunto das aulas práticas, com nota de zero a um.
A nota de frequência é obtida da seguinte forma:
- Nota de frequência = Nota trabalho * nota teste
No enunciado do trabalho prático será descrita a forma como este está dividido em fases e o peso de cada fase.
Condições de aprovação na cadeira
1. Avaliação de frequência superior ou igual a 8,5 valores;
2. Avaliação da média dos testes ou do exame final superior ou igual a 8,5 valores, e
3. Nota final superior ou igual a 9,5 valores.
Melhoria de nota
Através de um exame para melhoria de nota, os alunos poderão fazer uma melhoria da componente de testes/exame com o peso de 50% da nota final. A nota da frequência mantem-se inalterada após o exame de melhoria.