Algoritmos Distribuídos

Prof.: Mario R.F. Benevides - IM - UFRJ

Pre-requisito: Org. Dados

Objetivos:

Estudar os conceitos e os principais algoritmos distribuídos. O curso será dividido em duas partes: Algoritmos Básicos e Problemas Avançados.

Ementa:

Primeira Parte

• Conceitos Basicos

• Motivação

• Sistemas de Troca de Mensagens

• Sistemas de Memoria Compartilhada

• Fluxo de Controle e Roteamento

• Programas Reativos

• Síncrono versos Assíncrono

• Complexidade

• Algoritmos Basicos Sincronos

• Um Algoritmo Basico

• Um Algoritmo com Complexidade de Comunicação O(n log n)

• Eleição de um Lider

• O Problema

• Um Algoritmo Simples

• Busca em Amplitude

  • O Problema

  • Um Algoritmo Basico

  • Aplicações

• Caminho mais Curto

• Árvore Geradora Minima

  • O Problema

  • Teoria Básica

  • Um algoritmo

• Algoritmos Basicos Assíncronos

• Eleição de um Líder em um Anel

• Eleição de um Lider em uma Rede Geral

• Construção de Árvore Geradora, Difisão e Convergência

• Busca em Amplitude

• Caminho mais Curto

Segunda Parte

Nesta segunda parte serão estudados tópicos relacionados com a

área de sistemas distibuidos tasi como:

• Problema dos Filosofos Jantando

• Problema dos Filosofos Bebendo

• Detecção de Dealock

• Concenso em Sistemas Distribuídos

• Connhecimento em Sistemas Distribuídos

Avaliação:

Na primeira parte do curso os alunos farão uma prova P1. Na segunda um trabalho

T1. A media ser'a (P1 + T1 ) / 2

Bibliografia:

• Valmir Barbosa, An Introduction to Distributed Algorithms, The MIT Press, Cambridge, 1996.

• Nancy Lynch, Distributed Algorithms, Morgan and Kaufmann, San Francisco, 1996.

• Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, Cambridge, 1994.

Para maiores informações entrar em contato com o professor Mario