Guia de Cursos

Queres conhecer a oferta de cursos da NOVA, nas áreas das licenciaturas, mestrados e doutoramentos?
No nosso Guia de Cursos encontras informação útil sobre Faculdades, Institutos e Escolas.
Podes ainda aceder a informações complementares necessárias a uma completa integração.

saber mais Guia de Cursos

Faculdade de Ciências e Tecnologia

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

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

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

Pré-requisitos

Apesar de não existirem requisitos adicionais para além daqueles impostos pela estrutura curricular do curso, os seguintes aspectos devem set tomados em consideração pelos alunos que pretendam frequentar a unidade curricular:

  • Frequência de sistemas distribuídos (fortemente recomendado).
  • Conhecimentos sólidos de redes de computadores (recomendado).
  • Conhecimentos sólidos de programação em Java (recomendado).
  • Conhecimentos relativos à operação de sistemas operativos baseados em Linux (fortemente benéfico).

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. Casos de Estudo.

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 avaliação

Método de avaliação dos alunos:

* Componentes da avaliação:
• Avaliação da frequência cujo peso na nota final é de 45%.
• Quatro trabalhos de casa individuais cujo peso na nota final é de 10%
• Dois testes ou um exame final cujo peso na nota final é de 45%. 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 consiste em:
• Realização de um trabalho prático por fases em grupos de três pessoas.
• Realização de uma discussão presencial no final do semestre, com uma classificação compreendida entre zero e um.
A nota de frequência é obtida da seguinte forma:
• Nota de frequência = Nota trabalho * nota da discussão
No enunciado do trabalho prático será descrita a forma como este está dividido em fases e o peso de cada fase.

Trabalhos de casa:
• Os trabalhos de casa, que seram 4 ao longo do semestre, seram apresentados no final de aulas teóricas e devem ser entregues, em mão, sob forma manuscrita, no ínicio da aula teórica seguinte (ou em caso de impedimento enviado por e-mail ao regente da disciplina antes do inicio da aula teórica onde estes devem ser entregues).
• Os trabalhos de casa são resolvidos de forma individual.

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. As notas relativas às componentes da frequência e dos trabalhos de não sofrem alterações após o exame de melhoria.

Cursos