Geração de Spanning Tree Mínima Algoritmo GHS Algoritmos Distribuídos - Lynch Vicente Carvalho

Geração de Spanning Tree Geração de Spanning Tree MínimaMínima

Algoritmo GHSAlgoritmo GHS

Algoritmos Distribuídos - LynchAlgoritmos Distribuídos - Lynch

Vicente Carvalho


Criado por Gallager, Humblet, e Spira.

Um dos algoritmos mais conhecidos da teoria da computação distribuída. (Lyinch)

Motivação◦Minimiza o custo de comunicação

entre um processo fonte e todos os demais processos em uma rede. (broadcast)

◦Evita laços indesejados e permite redundância entre nós de uma rede.


Definições◦Grafo G = (V, E) ◦Conectado◦Não direcionado (bidirecional)◦Arcos com peso associado◦Processos com UID◦Peso do arco é conhecido por seus

dois vértices◦Assume-se que os pesos dos arcos

são únicos, não há repetição


Definições (continuação)◦Processos inicialmente quiescentes,

nenhuma ação de controle local está ativa em seu estado inicial. Cada processo tem uma ação de entrada wakeup na qual o ambiente sinaliza para iniciar a execução do algoritmo.


Descrição do funcionamento◦Processos se agrupam em componentes◦Componentes se agrupam e formam

componentes maiores◦Cada componente tem um nó líder, e

uma spanning tree que é um subgrafo da spanning tree mínima(MST)

◦Dentro de cada componente os processos cooperam para encontrar o minimum weight outside edge (MWOE), arco de menor peso que faz fronteira com um outro componente


Descrição do funcionamento (continuação)◦Depois de descoberto o MWOE uma

mensagem é enviada através desse arco para o componente vizinho

◦Os componentes podem se unir e formar um novo componente maior.

◦O processo se repete para o novo componente

◦A cada união (merge) feita entre componentes o novo componente cresce um nível, iniciando pelo nível 0


Descrição do funcionamento (continuação)


Como encontrar MWOE dentro de um componente?◦O nó líder do componente envia uma

mensagem broadcast através de sua spanning tree solicitando a informção

◦Cada nó sabe o peso dos arcos incidentes

◦Através de covercast o líder recebe a informação de qual nó está ligado à MWOE


Dificuldades◦1) Por ser um algoritmo assíncrono,

pode acontecer dos componentes crescerem de forma desbalanceada, fazendo com que um grande componente se una a um nó simples. Com isso o número de mensagens aumentaria significativamente. Antes de cada união o componente precisa encontrar a MWOE, que dependendo do tamanho do componente pode ter a necessidade de um grande número de mensagens.


Merge e Absorb◦Merge – União de dois componentes de

mesmo nível k, originando um novo componente maior de nível k+1 com novo líder.

◦Absorb – União de um componente de nível menor a um componente de nível maior, resultando na absorção do componente de nível menor pelo o de nível maior. O líder e o nível do componente resultante permanecem o mesmo do componente de nível maior.


Merge e Absorb


Como escolher o nó líder do componente?◦Só há troca de líder em caso de merge◦Para componentes com nível 1 ou maior é

identificado o arco principal (core edge)◦O arco principal é o MWOE que originou a

união dos componentes◦O arco principal (peso) + o nível do

componente é utilizado como identificador do componente

◦A extremidade do arco principal que possui o maior UID é eleito o novo líder do componente


Dificuldades◦2) Um processo adjacente j com um

identificador de componente diferente está na verdade no mesmo componente que o processo solicitante i, mas não sabe disso pois ocorreu um atraso na comunicação.


Solução dificuldade 2◦Caso 1:

nó i(solicitante), nó j(solicitado) Possuem diferentes identificadores de componente Nível de j é no mínimo tão alto quanto o nível de ii e j não podem estar no mesmo

componente, pois: Um nó possui apenas um identificador de

componente para cada nível Como o nó i está fazendo a solicitação significa

que ele está atualizado O nível do nó j é igual ou maior do que o nó i


Solução dificuldade 2◦Caso 2:

nó i(solicitante), nó j(solicitado) Possuem diferentes identificadores de

componente Nível de j é menor que o nível de i

j aguarda até estar no mesmo nível que i para responder.


Dificuldades◦3)O nível de avanço (quantidade de

uniões) de cada componente pode ser diferente. Não está claro que tipo de interferência isso pode causar em uma busca concorrente por MWOE.

◦Componente C é absorvido pelo componente C’ enquanto C’ está envolvido em descobrir seu MWOE

◦MWOE de C conecta o nó i(C) ao nó j de C’


Caso 1O nó j ainda não determinou o

MWOE

Neste caso, o algoritmo de procura por MWOE que está rodando em C’ irá fazer a busca no componente C.


Caso 2O nó j já determinou o MWOE

O mwoe(j) != mwoe(j,i) pois o nível de C é inferior ao nível de C’

O MWOE de C’ é menor que mwoe(j,i) pois caso contrário aconteceria um merge (o nó i aguardaria até seu nível se igualar ao do componente C’)

Se mwoe(i,j) é o MWOE de C e o MWOE de C’ é menor que mwoe(i,j) então o MWOE do novo componente (C+C’) não pode estar em C.


Mensagens utilizadas pelo algoritmoInitiate – Disparada pelo líder

(broadcast) para os processos iniciarem a busca pelo mwoe, contém o identificador do componente.

Report – Retorna a informação (convergecast) de arco mínimo ao líder do componente.

Test – Um processo envia uma mensagem test a outro processo para saber se está no mesmo componente.


Mensagens utilizadas pelo algoritmoAccept e Reject – Resposta a mensagem

test, caso esteja em um componente diferente, accept, caso esteja no mesmo, reject.

Changeroot – É disparada pelo líder para os processos adjacentes ao MWOE do componente, depois do MWOE ter sido encontrado.

Connect – Enviada através do MWOE para realizar uma união entre componentes.


Mensagens utilizadas pelo algoritmoPara se manter a complexidade de

comunicação baixa foi necessário criar o seguinte mecanismo para o protocolo test/accept/reject:Cada processo possui uma lista dos arcos

incidentes com seus respectivos pesos em ordem crescente.

Cada arco é classificado como branch, rejected ou basic.


Mensagens utilizadas pelo algoritmoProtocolo test/accept/reject:

Branch – Aqueles que fazem parte da MST.Rejected – Aqueles que não fazem parte da MST.Basic – Processos que ainda não foram classificados.

Inicialmente todos os arcos são classificados como basic.

Ao enviar a mensagem test, o processo o faz sequencialmente, por ordem crescente de peso, somente para os arcos basic. A mensagem contém o identificador do componente.


Comparação Tel◦Nós não possuem UID◦Componente (fragmento) possui um

core edge e 2 nós líderes◦No fim da busca pelo MWOE do

fragmento os nós líderes trocam mensagens entre si

◦O nó que possuir o MWOE dispara o reinício do processo

◦Se não houver MWOE o algoritmo chegou ao final


Complexidade comunicação (Lynch)◦ Cada arco pode ser rejeitado no máximo uma

vez, para isso são necessárias duas mensagens (test+reject). Complexidade |E|.

◦ As mensagens test-accept, initiate-report, changeroot-connect para um componente podem ser associadas de modo que possa ter no máximo uma dessas mensagens associadas a cada nó. Complexidade N.

◦ Calculando para cada nível temos a complexidade: N logN + |E|


Complexidade comunicação (Tel)◦ Cada arco pode ser rejeitado no máximo

uma vez, para isso são necessárias duas mensagens (test+reject). Complexidade 2|E|.

◦ Em qualquer nível um nó recebe no máximo: 1 initiate 1 accept

◦ Em qualquer nível um nó envia no máximo: 1 report 1 changeroot ou connect 1 test que não leva a rejeição

◦ Complexidade resultante: 2|E| + 5NlogN


Algoritmo de Prim (variante)◦Inicia-se no nó Vo e prosegue em fases(p)

sincronizadas adicionando um novo nó a MST por fase.

◦Fases são inicializadas por uma mensagem pulso (broadcast) enviada pelo nó raiz (Vo).

◦Cada nó conhece seu pai e seus filhos(se houver).

◦Cada nó sabe quais vizinhos já pertencem a MST.


Algoritmo de Prim (variante) ...continuação◦A cada fase(p) a procura pelo MWOE é

feita por broadcast/convergecast.◦Cada fase necessita p mensagens◦Complexidade O(n²)


Conclusão◦É uma versão distribuída do

algoritmo de Kruskal.◦É mais adequado a ambientes

distribuídos do que o algoritmo de Prim (distribuído).

◦Visão do Tel mais realista e de mais fácil entendimento.


Bibliografia◦ Lynch, N. Distributed Algorithms, Morgan

Kaufmann Publishers, Inc., San Francisco, CA, 1996

◦ Tel, G. Introduction to Distributed Algorithms, Cambridge University Press; 2nd Edition, 2000

◦ Peleg, D. Distributed Computing: A Locality-Sensitive Approach, Society for Industrial Mathematics, 1987

◦ Cormen ,Thomas H. ; Rivest , Ronald L.; Leiserson, Charles E. Introduction to algorithms, The MIT Press; 2nd edition, 2001


Documents

Geração de Spanning Tree Mínima Algoritmo GHS Algoritmos Distribuídos - Lynch Vicente Carvalho