Instituto de Computação - UFF Sincronizadores Algoritmos Distribuídos Professora: Lúcia Drummond

Instituto de Computação - UFF

Sincronizadores

Algoritmos DistribuídosProfessora: Lúcia Drummond

Instituto de Computação - UFF 2

Sincronizadores

Objetivo

Transmitir a todo nó a cada pulso a informação de que todos os vizinhos dos nós estão seguros em relação aquele pulso.


Sincronizadores

Sincronizador Alpha

A informação de que todos os vizinhos dos nós estão seguros com relação ao pulso s ≥ 0 é transmitida diretamente pelos próprios vizinhos através de uma mensagem safe(s).


Sincronizadores

Sincronizador Alpha

Um nó pode prosseguir para o pulso s+1 quando receber uma mensagem safe(s) de todos os seus vizinhos.

Como não é assumido que os canais sejam FIFO, as mensagens de computação e acks enviadas em conexão com o pulso s são enviadas como comp_msg(s) e acks(s).


Sincronizadores

Sincronizador Alpha

Uma variável expected(s), inicialmente igual a zero, grava para todo s o número de acks esperados.

Esta variável é incrementada sempre que são enviadas mensagens de computação.


Sincronizadores

Sincronizador Alpha

A mensagem startup é enviada pelos nós em N para todos os seus vizinhos quando eles iniciam a computação.

Esta mensagem ao atingir um nó que não está em N0 pela primeira vez o acorda e então é propagada por este para todos os outros nós.


Sincronizadores

Sincronizador Alpha

Todos os nós somente executam o pulso s=0 da computação síncrona ao receber um startup de todos os vizinhos (controlado pela variável go).


Algoritmo A_Alg(Alpha)

Variáveis

si:=0;

msgi(s):=0 para todo s;

initiadedi:=false;

goij:=false;

expectedi(s):=0 para todo s;

safeij(s):=false para todo nj viz e para todo s;



Algoritmo

Input:msgi=nil;

Ação:initiatedi:=true;

Envie startup para todo nj viz;



Algoritmo

Input:msgi=startup tal que origemi(msgi)=nj;

Ação:if not initiatedi then

begininitiatedi:=true;

Envie startup para todo nk viz;

end



Algoritmo

goij:=true;

if goij para todo nj viz then

beginExecute alguma computação;Envie comp_msg(si) em cada aresta de

um subconjunto de viz;if expected(si)=0 then

Envie safe(si) para todo nk viz;

end



Algoritmo

Input:msgi=comp_msg(s) tal que origemi(msgi)=nj;

Ação:MSGi(s+1):=MSGi(s+1) {msgi};

Envie ack(s) para nj;



Algoritmo

Input:msgi=ack(s);

Ação:expectedi(s):=expectedi(s)-1;

if expectedi(s)=0 then

Envie safe(s) para todo nj viz;



Algoritmo

Input:msgi=safe(s) tal que origemi(msgi)=nj;

Ação:safei

j(s)=true;

if safeij(si) para todo nk viz then

beginsi:=si +1;

Execute alguma computação;Envie uma comp_msg(si) em cada aresta

do subconjunto de viz;



Algoritmo

if expectedi(si)=0 then

envie safe(si) para todo nk viz;

end


Sincronizadores

Sincronizador Beta

O sincronizador Beta exige uma spanning tree já estabelecida em G.

A função do líder do sincronizador Beta é reunir de todos os outros nós a informação de segurança necessária para prosseguir para futuros pulsos e então propagar esta informação para todos eles.


Sincronizador Beta

Os detalhes deste procedimento são os seguintes: Quando um nó que não é um líder

se torna seguro com relação a um certo pulso, e

recebe uma mensagem de safe de todos exceto de um do seus vizinhos na árvore,

Então este envia uma mensagem de safe para o

único vizinho do qual ele não recebeu uma mensagem de safe (aresta da árvore conectando a este vizinho leva ao líder).


Sincronizador Beta

O líder ao receber mensagens safe sobre todas as arestas da árvore que são incidentes a ele, e estando seguro com relação ao pulso, propaga um mensagem sobre a árvore, indicando que a computação de um novo pulso pode ser executada.

Esta mensagem pode ser também uma mensagem de safe, e então a regra para um nó prosseguir para o próximo pulso é ter recebido uma mensagem de safe de todas as arestas incidentes a ele.


Sincronizador Beta




Sincronizador Beta




Sincronizador Beta




Sincronizador Beta




Sincronizadores

Sincronizador Gama

O sincronizador Gama é uma combinação dos outros dois sincronizadores.

Dentro dos clusters, o sincronizador Gama opera como sincronizador Alpha.

Os nós são agrupados em clusters.

Entre os clusters, como sincronizador Beta.

Documents

Instituto de Computação - UFF Sincronizadores Algoritmos Distribuídos Professora: Lúcia Drummond