Este Material está baseado no material Algoritmos Distribuídos – Modelo Computacional, Antonio...
21
Tópicos em Sistemas Distribuídos Modelo Computacional Este Material está baseado no material “Algoritmos Distribuídos – Modelo Computacional”, Antonio A. F. Loureiro – 2012.
Este Material está baseado no material Algoritmos Distribuídos – Modelo Computacional, Antonio A. F. Loureiro – 2012
Este Material est baseado no material Algoritmos Distribudos
Modelo Computacional, Antonio A. F. Loureiro 2012.
Slide 2
Modelo Computacional Modelo Esquema que possibilita a
representao de uma entidade. No modelo, s se deve incluir o que for
relevante para a modelagem do objeto em questo. Computacional
Relativo ao processamento. Definio (nosso contexto): Esquema que
descreve como o modelo abstrato do processamento de algoritmos.
Importncia Um algoritmo no existe, ou seja, no possvel escrev-lo,
se antes no for definido o modelo computacional onde ser executado.
Conceito bsico no projeto de qualquer algoritmo.
Slide 3
Modelo Computacional Que modelos existem? Literalmente dezenas
deles. Se no estiver satisfeito, invente o seu! O mais popular
(usado) de todos: RAM Random Access Machine. Mundo distribudo:
Normalmente ns que seguem o modelo RAM interconectados entre si
atravs de troca de mensagens. No existe compartilhamento de memria.
Elementos desse modelo N computacional representado pelo modelo
RAM. Canal normalmente representado pelo modelo FIFO.
Slide 4
Modelo RAM Elementos do modelo Um nico processador Memria
Observaes: Podemos ignorar os dispositivos de entrada e sada
(teclado, monitor, etc) assumindo que a codificao do algoritmo e os
dados j esto armazenados na memria. Em geral, no relevante para a
modelagem do problema saber como o algoritmo e os dados foram
codificados e armazenados na memria.
Slide 5
Modelo RAM Computao nesse modelo: Processador busca
instruo/dado na memria. Uma nica instruo executada de cada vez.
Cada instruo executada sequencialmente. Cada operao executada pelo
processador, incluindo clculos aritmticos, lgicos e acesso a
memria, implica num custo de tempo: Funo de complexidade de tempo.
Cada operao e dado armazenado na memria, implica num custo de
espao: Funo de complexidade de espao.
Slide 6
Modelos Computacionais para o Mundo Distribudo Espao de Modelos
Computacionais no sequenciais Um espectro bastante largo! Pergunta
importante: Todo algoritmo distribudo pode ser implementado em
qualquer modelo computacional? Definitivamente NO!
Slide 7
Problema dos Dois Exrcitos Na Grcia antiga, lugares
maravilhosos como este...... Podiam se transformar em cenrios de
guerra. Vale perto de Almfiklia, Grcia quando algum filosofo prope
o Problema dos dois exrcitos
Slide 8
Problema dos Dois Exrcitos Cenrio Inicial Exrcito Alfa est em
maior nmero que o exrcito Gama mas est dividido em duas metades,
cada uma numa lateral do vale. Cada metade do exrcito Alfa est em
menor nmero que o exrcito Gama. Objetivo do exrcito Alfa: coordenar
um ataque ao exrcito Gama para ganhar a guerra.
Slide 9
Problema dos Dois Exrcitos O Problema da Coordenao 1.General do
exrcito Alfa, do lado esquerdo do vale, chama o seu melhor soldado
para levar uma mensagem para o general do exrcito Alfa do lado
direito: Vamos atacar conjuntamente amanh s 06:00? Observaes: A
nica possibilidade de comunicao entre os dois generais atravs de um
mensageiro Os dois generais tm um relgio perfeitamente
sincronizado, ou seja, eles sabem pela posio do sol quando
06:00h.
Slide 10
Problema dos Dois Exrcitos O Problema da Coordenao 2.O soldado
do exrcito Alfa atravessa as linhas inimigas e leva a mensagem at o
general do outro lado.
Slide 11
Problema dos Dois Exrcitos O Problema da Coordenao 3.O general
do exrcito Alfa do lado direito concorda em atacar o exrcito Gama
no dia seguinte s 06:00h.
Slide 12
Problema dos Dois Exrcitos O Problema da Coordenao 4.O soldado
do exrcito Alfa atravessa novamente as linhas inimigas e confirma
com o seu general o ataque para o dia seguinte.
Slide 13
Problema dos Dois Exrcitos O Problema da Coordenao Aps esses
quatros passos terem sido realizados, vai haver ataque amanh s
06:00h?
Slide 14
Problema dos Dois Robos Imagine dois ou mais robs que vo
carregar uma mesa de tal forma que um ficar de frente para outro.
Problema: Projete um algoritmo para coordenar a velocidade e direo
do movimento de cada rob para que a mesa no caia. Os robs s podem
comunicar entre si atravs de um canal de comunicao sem fio.
Variante do problema anterior!
Slide 15
Problema dos Dois Robos Considerando o modelo computacional
proposto, possvel projetar um algoritmo distribudo para esse
problema? NO! No existe um algoritmo distribudo para o problema de
coordenao considerando o modelo computacional proposto!
Slide 16
Alguns comentrios sobre algoritmos distribudos So a base do
mundo distribudo, ou seja, de sistemas distribudos. Sistemas
distribudos podem ser: Tempo real ou no; Reativos ou no. Sistemas
distribudos podem ser especificados tomando-se como base: tempo;
eventos.
Slide 17
Projeto de algoritmos distribudos: Modelo de falhas Descreve as
suposies sobre o comportamento funcional dos elementos do modelo
computacional ao longo do tempo: n computacional; canal. Para cada
um destes elementos possvel fazer diferentes consideraes. Modelo de
falhas associado a um n computacional (dois extremos): Falha e pra;
Bizantino. Modelo de falhas associado ao canal: Mensagens so
perdidas, duplicadas, corrompidas, entregues fora de ordem. Qual a
importncia do modelo de falhas no projeto de algoritmos
distribudos?
Slide 18
Projeto de algoritmos distribudos: Canal de Comunicao Mecanismo
atravs do qual mensagens so trocadas entre os ns computacionais.
Aspectos a considerar: Modelo de falhas; Sentido da comunicao:
simplex, half-duplex, full-duplex; Sincronismo: assncrono, sncrono;
Tipo de comunicao: unicast, multicast, broadcast, anycast. Qual a
importncia do canal de comunicao no projeto de algoritmos
distribudos?
Slide 19
Projeto de algoritmos distribudos: Topologia Define como os ns
so interconectados entre si atravs dos canais de comunicao. Existem
diferentes possibilidades: Anel; Hipercubo; rvore; Uma outra
especfica. Qual a importncia da topologia no projeto de algoritmos
distribudos?
Slide 20
Aspecto tpico de algoritmo distribudo: No determinismo No
possvel especificar a priori qual ser a ordem exata de uma computao
distribuda. possvel ter no determinismo devido : Concorrncia entre
os ns; Especificao (simplificao do nmero de estados); No
observabilidade (falta de acesso aos estados internos dos ns). No
possvel evitar
Slide 21
Aspecto tpico de algoritmo distribudo: Sincronizao Deve-se
definir como ser feita. necessrio ter sincronizao devido : Competio
entre recursos (excluso mtua); Coordenao distribuda.