* Este material está baseado no capítulo 4 do livro An Introduction to Distributed Algorithms,...
8
Tópicos em Sistemas Distribuídos Algoritmos Básicos* * Este material está baseado no capítulo 4 do livro “An Introduction to Distributed Algorithms”, Valmir C. Barbosa, MIT Press, 1996.
* Este material está baseado no capítulo 4 do livro An Introduction to Distributed Algorithms, Valmir C. Barbosa, MIT Press, 1996
* Este material est baseado no captulo 4 do livro An
Introduction to Distributed Algorithms, Valmir C. Barbosa, MIT
Press, 1996.
Slide 2
Propagao de Informao Suposies Topologia da rede representada
por um grafo G no dirigido inf a informao a ser disseminada em G n
o nmero de ns em G m o nmero de vrtices em G
Slide 3
Propagao de Informao Problema Difundir em G informao presente
em um nico n Dois casos tratados: Propagao de informao de um nico n
s para todos os outros ns em G. Propagation of Information ou,
simplesmente, PI Propagao de informao de um nico n s para todos os
outros ns em G com o requisito que ao final da execuo do algoritmo,
o n s tenha a confirmao do recebimento de inf por todos os outros
ns. Propagation of Information with Feedback ou, simplesmente,
PIF
Slide 4
Propagao de Informao Soluo para o problema PI baseada em Difuso
ou Onda de Propagao Sejam os conjuntos: No: conjunto de ns que
possuem inf inicialmente (apenas o ns s) No: conjunto de ns que NO
possuem inf inicialmente Princpio Fazer difuso atravs de inundao
(flooding)
Slide 5
Propagao de Informao Ideia No incio, o n s envia inf para todos
os seus vizinhos Cada n em No, ao receber inf pela primeira vez,
envia a mensagem para todos os seus vizinhos, incluindo a aresta de
onde foi recebida Um n recebe inf de todos os seus vizinhos A
mensagem inf propagada a partir do n s atravs de uma onda Cada n em
No recebe inf a partir do n s, da forma mais rpida possvel, apesar
de falhas que possam haver em G, que ainda geram um grafo conexo
Vrios algoritmos distribudos funcionam desta forma
Slide 6
Propagao de Informao Algoritmo PI
Slide 7
Propagao de Informao Problema Escreva o algoritmo que trata de
mltiplas instncias concorrentes do Algoritmo PI Escreva o algoritmo
que trata de mltiplas instncias concorrentes do Algoritmo PI Enviar
uma srie de mensagens inf 1, inf 2,...
Slide 8
Propagao de Informao com Realimentao - PIF Exerccio Difundir em
G a informao presente em um nico n s para todos os outros ns em G
com o requisito que ao final da execuo do algoritmo, o n s tenha a
confirmao do recebimento de inf por todos os outros ns Estratgia
para resoluo do problema PIF: Usando difuso (flooding)