ad3-TecnicasBasicas

Prévia do material em texto

Algoritmos Distribuídos
Técnicas Básicas
Antonio Alfredo Ferreira Loureiro
loureiro@dcc.ufmg.br
http://www.dcc.ufmg.br/~loureiro
UFMG/ICEx/DCC 1
loureiro@dcc.ufmg.br
http://www.dcc.ufmg.br/~loureiro
Eleição de Líder
UFMG/ICEx/DCC 2
Eleição de Líder
• Líder:
– Nó ni ∈ N
– ∀nk ∈ N, k 6= i, nk reconhece que ni executa uma tarefa especial
– ni pode ser qualquer nó de N , ou seja, qualquer nó candidato pode as-
sumir o papel de líder
• Problema de eleição de líder:
– Escolher um líder de um conjunto de nós candidatos
UFMG/ICEx/DCC 3
Eleição de líder: Suposições
• Nó ni só conhece sua própria identificação id i
• Não faz sentido no contexto de sistemas anônimos
• Cada identificador é único em G e existe uma ordem total < entre os identifi-
cadores
• Cada identificador pode ser expresso em dlogne bits
• G é um grafo não dirigido
UFMG/ICEx/DCC 4
Eleição de líder: Observações
• Conseqüências de existir uma ordem total < entre os identificadores:
– Permite definir uma estratégia onde o candidato escolhido é aquele com o
menor/maior identificador
– É possível definir uma forma de desempate se outro critério é usado
– Se não houvesse identificadores únicos, poderia haver um deadlock em
função do critério escolhido
UFMG/ICEx/DCC 5
Eleição de líder: Motivação
• Deve haver algum tipo de coordenação centralizada em G e:
– não existe uma solução distribuída, ou
– a solução centralizada tem um desempenho melhor
• Exemplos onde não há uma solução distribuída:
– Processo de recuperação de um sistema depois que G sofre uma falha
(representada genericamente por uma mudança topológica)
– Papel do líder: coordena as funções de alocação e roteamento
• Exemplo onde a solução centralizada tem um desempenho melhor:
– Problemas em grafo como árvore geradora mínima e fluxo máximo em re-
des
UFMG/ICEx/DCC 6
Árvore geradora × Eleição de líder
• Problemas relacionados
• Suposições:
– líder é o nó com o maior identificador
– canais são FIFO
UFMG/ICEx/DCC 7
Árvore geradora × Eleição de líder
• Se existe uma árvore geradora em G, um líder pode ser eleito da seguinte
forma
– Cada nó executa o algoritmo PIF
– se o nó é candidato
então propaga seu identificador
senão propaga uma “msg nula”
– Antes de propagar uma informação de qualquer outro nó, propaga a sua
própria informação
– Um nó, ao receber a realimentação de seus vizinhos, escolhe o líder
• Complexidade:
– Mensagem: O(n2) ou O(n2 logn) bits
– Tempo: O(n)
UFMG/ICEx/DCC 8
Algoritmo baseado em árvore geradora (PIF)
• É possível um nó ni receber inf i de todos os seus vizinhos e não ter recebido
ainda a identificação de um nó candidato?
– Não. Prova por contradição.
– Suponha que exista um nó ni que tenha recebido a confirmação de todos
os seus vizinhos e ainda exista pelo menos uma identificação idk do nó
candidato nk que não foi recebida.
– Para ni ter recebido a realimentação de seus vizinhos, uma onda de propa-
gação para ni deve ter sido iniciada em nk (ou porque nk é um nó folha ou
porque nk recebeu a realimentação de todos os seus vizinhos).
– Não é possível ni ter recebido inf i sem ter recebido infk já que pelo princí-
pio do algoritmo, nk envia primeiro infk antes de enviar inf i.
– Como os canais são FIFO, o nó ni irá receber primeiro infk.
– Logo, não existe um nó nk tal que ni não tenha recebido a sua infk.
UFMG/ICEx/DCC 9
Comentários sobre o algoritmo
• Permite eleger um líder num grafo genérico com arestas FIFO
• Este é o algoritmo A Test Connectivity, onde N0 = {conjunto de nós can-
didatos} e inf i é o idi ou uma mensagem nula, dependendo se o nó é can-
didato ou não, respectivamente
• Complexidade:
– Mensagem: O(nm)
– Tempo: O(n)
UFMG/ICEx/DCC 10
Comentários sobre o algoritmo
• O que acontece se somente os nós candidatos executam o algoritmo PIF?
– Todos os nós candidatos irão saber quem é o líder, pois ao final da exe-
cução, todos os identificadores dos líderes serão conhecidos
– Os nós não candidatos, por sua vez, não sabem se existe algum identifi-
cador não recebido ainda, já que não participam do PIF
– Logo, eles não poderão decidir, com certeza, o líder baseado nos identifi-
cadores recebidos até o momento
Ü Na versão proposta, cada nó, ao final da execução, sabe quem é o líder
Ü A execução, por cada nó, cria uma “barreira de sincronização”
UFMG/ICEx/DCC 11
Comentários sobre o algoritmo
• Como ficam estas complexidades se G tem uma topologia específica?
• Caso 1: G é um Anel
Complexidade:
– Mensagem: O(n2)
UFMG/ICEx/DCC 12
Comentários sobre o algoritmo
• Como ficam estas complexidades se G tem uma topologia específica?
• Caso 2: G é um grafo completo
Complexidade:
– Mensagem: O(n3)
UFMG/ICEx/DCC 13
Estratégia para eleger um líder num grafo completo
• Algoritmo síncrono:
– s = 0, todo nó candidato envia sua identificação para todos os outros nós
– s = 1, cada nó recebe a identificação dos nós candidatos e pode decidir
quem é o líder
• Complexidade:
– Mensagem: O(n2)
– Tempo: O(1) + O(n) (custo para fazer uma pesquisa seqüencial)
• É possível melhorar? Sim
Complexidade:
– Mensagem: O(n logn)
– Tempo: O(logn)
UFMG/ICEx/DCC 14
Estratégia para eleger um líder num grafo completo
• Pulsos pares:
– Um nó candidato tenta “capturar” seus vizinhos enviando uma mensagem
de captura
– A quantidade de mensagens de captura é dependente do pulso
• Pulsos ímpares:
– Nós que receberam mensagens de captura decidem se vão ser capturados
ou não
• A mensagem de captura contém o identificador do nó candidato
UFMG/ICEx/DCC 15
Estratégia para eleger um líder num grafo completo
Número de mensagens envi-
adas em pulsos pares:
Nós (n) 0 2 4 6
2 1
3 1 1
4 1 2
5 1 2 1
6 1 2 2
7 1 2 3
8 1 2 4
9 1 2 4 1
10 1 2 4 2
...
• Por exemplo, numa rede com 10 nós,
um candidato envia primeiro 1, depois
2, depois 4, e finalmente 2 msgs
• O nó candidato só continua enviando
mensagens de captura caso não seja
capturado
UFMG/ICEx/DCC 16
Estratégia para eleger um líder num grafo completo
Número de mensagens envi-
adas em pulsos pares:
Nós (n) 0 2 4 6
2 1
3 1 1
4 1 2
5 1 2 1
6 1 2 2
7 1 2 3
8 1 2 4
9 1 2 4 1
10 1 2 4 2
...
• O último pulso ímpar é 2dlogne − 1,
onde os nós que receberam msgs (do
pulso anterior) enviam ou não acks
• O último pulso par é 2dlogne, onde os
acks são contabilizados, mas
nenhuma outra msg é enviada
• Exemplo: n = 10
– dlog 10e = 4
– Último pulso ímpar = 7
– Último pulso par = 8
UFMG/ICEx/DCC 17
Algoritmo S Elect Leader C
. Variables:
candidatei = false; {Indica se o nó é candidato ou não}
tried ji = false ∀nj ∈ Neigi; {Nó nj que já tentou capturar}
owner id i = nil. {Líder corrente}
. Input:
{No pulso s = 0, apenas os nós candidatos executam estes comandos}
s = 0, MSGi(0) = ∅.
Action if ni ∈ N0: (1)
candidatei ← true; {Marca que o nó ni é candidato}
owner id i ← idi; {O líder de ni até o momento é o próprio nó}
Let nj be a node ∈ Neigi; {Escolhe um nó nj dentre os n− 1 para tentar capturar}
tried ji ← true; {Marca que tentou capturar o nó nj}
Send capture(id i) to nj. {Envia msg de captura para o nó nj}
UFMG/ICEx/DCC 18
Algoritmo S Elect Leader C
. Input:
s odd | 0 < s ≤ 2dlogne − 1, {Pulso é ímpar e condição de parada é satisfeita}
MSGi(s) | origini(capture(id i)) = (ni, nj) for capture(id j) ∈ MSGi(s).
Action: (2)
{Seja nk o maior identificador recebido dentre as msgs de captura}
Let nk ∈ Neigi be | idk ≥ id j ∀ capture(id j) ∈ MSGi(s);
{Se o identificador do líder corrente é menor que nk então o líder deve mudar}
{Caso contrário, ni continua sendo o líder}
if owner id i < idk
then begin
if candidatei {Se ni é candidato então deixa de ser}
then candidatei ← false;
owner id i ← idk; {Marca nk como novo líder}
Send ack to nk {Envia ack para nk, o novo líder}
end.
UFMG/ICEx/DCC 19
Algoritmo S Elect Leader C
. Input:
s even | 0 < s ≤ 2dlogne, {Pulso é par e condição de parada é satisfeita}
MSGi(s).
Action: (3)
{Para um nó continuar a ser candidato a líder, ele deve receber um ack para cada msg
enviada no último pulso par (s − 2). Essaquantidade é dada pelo menor valor entre
2(s−2)/2 e n − 2(s−2)/2 já que no último pulso podem haver menos msgs enviadas (veja
tabela).}
if candidatei
then if |MSGi(s)| < min(2(s−2)/2, n− 2(s−2)/2) {acks em s = msgs env. em (s− 2)?}
then candidatei ← false {Não, nó deixa de ser candidato}
else if s < 2dlogne {Sim e ainda há pulsos a serem executados?}
then begin
{S é o conjunto de nós que tentarão ser capturados neste pulso.}
Let S ⊂ Neigi be | |S| = min(2s/2, n− 2s/2) ∧ tried ji = false ∀nj ∈ S;
{Marca que tentou capturar o nó nj}
tried ji = true ∀nj ∈ S;
{Envia msg de captura para o nó nj}
Send capture(id i) ∀nj ∈ S
end.
UFMG/ICEx/DCC 20
Comentários sobre o algoritmo S Elect Leader C
• Nó candidato ni tem oportunidade para capturar os nós no pulso s = 0 (1) e
nos outros pulsos pares (3)
• A captura de mais nós em (3) depende se um ack foi recebido para cada msg
enviada no pulso par anterior:
– Essa quantidade é dada pelo menor valor entre 2(s−2)/2 e n − 2(s−2)/2
já que no último pulso podem haver menos msgs enviadas (veja tabela)
– Para n = 10, o nó candidato que vai se tornar líder, envia/recebe a
seguinte quantidade de mensagens/acks em cada pulso par:
Msgs enviadas Acks recebidos
Pulso (s) 2s/2 n− 2s/2 Min 2(s−2)/2 n− 2(s−2)/2 Min
0 – – 1 – – –
2 2 8 2 1 9 1
4 4 6 4 2 8 2
6 8 2 2 4 6 4
8 – – – 8 2 2
UFMG/ICEx/DCC 21
Comentários sobre o algoritmo S Elect Leader C
• Em (2), o nó decide se muda o seu owner id ou não
• Informações sobre os pulsos, sendo n = 10:
– dlog 10e = 4
– Último pulso ímpar = 2dlogne − 1 = 7
– Último pulso par = 2dlogne = 8
• Complexidade de Tempo: O(logn)
UFMG/ICEx/DCC 22
Algoritmo S Elect Leader C:
Complexidade de mensagem
Para 1 ≤ k ≤ dlogne − 1, o número máximo de nós a chegar no pulso s = 2k
como candidato é:
# Max de Msgs Acks
k s = 2k candidatos enviadas enviados
b n
2k−1
c
1 2 10
Para n = 10, temos 1 ≤ k ≤ dlog 10e − 1, ou seja, 1 ≤ k ≤ 3:
Max de Msgs Acks
k s = 2k No pulso Total candidatos enviadas enviados
0 0 0 10 10 0
1 2 0 0 10 10 0
UFMG/ICEx/DCC 23
Snapshot Distribuído
UFMG/ICEx/DCC 24
Evento
• Computação distribuída:
– Conjunto de eventos, representado por Ξ
• Um evento ξ é uma 6-tupla:
ξ = 〈ni, t, ϕ, σ, σ′,Φ〉
onde,
– ni é o nó no qual o evento ocorre
– t é o instante do tempo, de acordo com o relógio local de ni, em que o
evento ocorreu
– ϕ é a mensagem, se existir, que disparou o evento, quando de sua re-
cepção, em ni
– σ é o estado de ni antes da ocorrência do evento
– σ′ é o estado de ni depois da ocorrência do evento
– Φ é o conjunto de mensagens, se existir, enviado por ni como conseqüên-
cia da ocorrência do evento
UFMG/ICEx/DCC 25
Evento
-ni
tempo
σ σ′
t
Parte da CEFSM executada pelo nó ni
e e-
σ σ′
+ϕ|ei
−Φ|ai
onde
– ei é um evento interno
– ai é uma ação interna
UFMG/ICEx/DCC 26
Estado × Evento
-
-
. . .
ni
σ0i σ
1
i . . .
nj
Σi
Σj
σ2i
σ0j σ
1
j σ
2
j
...
 Ξ
Ü Os dois conceitos são duais
UFMG/ICEx/DCC 27
Estado global
• Estado global consistente ou snapshot :
– Estado que pode estar presente no Diagrama de Hasse correspondente à
execução dessa computação
Exemplo: figura 3.3, página 78 do livro texto
UFMG/ICEx/DCC 28
Snapshot Distribuído
• Técnica para registrar estados globais durante a execução de um algoritmo
assíncrono
– Informação registrada fica espalhada pelos nós de G
• A partir desses estados, propriedades globais podem ser analisadas
• Aplicações:
– Verificação de propriedades estáveis
– Questões relacionadas com o tempo durante uma simulação distribuída
UFMG/ICEx/DCC 29
Snapshot Distribuído
• Existem casos (e.g., simulação distribuída) em que é desejável o registro do
estado global com alguma propriedade específica
– Pode ser mais eficiente usar um líder para fazer o registro do estado global
de forma centralizada
• G é um grafo dirigido mas solução pode ser estendida para o caso do grafo
não ser dirigido
UFMG/ICEx/DCC 30
Snapshot Distribuído
• Existem duas computações distribuídas:
– Substrato: computação que se deseja registrar o estado global
– Superimposição: computação responsável por registrar o estado global
!!
!!
!
!!
!!
!
!!
!!
!
!!
!!
!
A
AAK
!!
!!
!
!!
!!
!
!! !! !! !! !! !!?? ?
!! !!
......
......
.....
......
......
.....
......
......
.....!! !!!! !!
�
���...
...
Algoritmo de
Algoritmo
Distribuído
Plano de Superimposição
Plano do Substrato
Snapshot Distribuído
UFMG/ICEx/DCC 31
Snapshot Distribuído
• Os dois algoritmos executam em G
• Cada nó é responsável por executar cada computação
• As duas computações são totalmente independentes:
– Não existe relações de causalidade entre elas
• Interação entre as duas computações:
– Superimposição é capaz de “observar”as variáveis e mensagens com a
finalidade de registrar o estado global
• A execução das duas computações ocorre de forma interleaved (“intercalada”
ou “entrelaçada”)
• Registrar um estado global do substrato é tirar um instantâneo (snapshot) do
nó sem ter que pará-lo
UFMG/ICEx/DCC 32
Snapshot Distribuído:
Algoritmo Síncrono
• Suposição:
– Mensagens enviadas no pulso s− 1 chegam ao seu destino no pulso s
• Princípio:
– Em cada pulso s ≥ 0, os estados de todos os nós e as mensagens envi-
adas no pulso s− 1 (s > 0) constituem um estado global
• Estado global pode ser armazenado em G de forma distribuída
• Nó armazena seu próprio estado e o estado de todas as arestas em que
recebe mensagens
UFMG/ICEx/DCC 33
Snapshot Distribuído:
Algoritmo Assíncrono
• Nós trocam uma mensagem especial chamada marker
• Nó ni ∈ N0, que participa do algoritmo A Record Global State (superim-
posição), registra o estado local do substrato σi
• Mensagem de marker é enviada em todos os canais de saída de ni
s s s -
A
A
A
A
AU
A
A
A
A
AU
-
6
Superimposição
ni
. . .
Substrato
enviadas neste período
Msgs do substrado não podem ser
t
t
σ
UFMG/ICEx/DCC 34
Snapshot Distribuído:
Algoritmo Assíncrono
s
s��
�
�
�
�
���
s
s��
�
�
�
�
���
s
s��
�
�
�
�
���
sAAAU
-
- t
t
ni
nj
marker
Φji
. . .
(1a vez)
Marker de njMsgs do
Substrato
• Conjunto Φji:
– Estado da aresta nj → ni
• Estado da aresta na qual marker foi recebido pela primeira vez =
Ü Registro está completo quando o nó recebe marker em todas as suas
arestas de entrada
– Similar ao algoritmo de PI
UFMG/ICEx/DCC 35
Snapshot Distribuído:
Algoritmo Assíncrono
• G é um grafo dirigido:
– Podem haver nós que nunca irão receber a mensagem de marker
• Não é o caso de G é fortemente conectado:
– Existe um caminho entre um par qualquer de vértices
• Complexidades:
– Mensagem: O(m), já que em cada aresta passa uma msg de marker
– Tempo: O(n), para uma msg de marker alcançar um nó que não esteja em
N0
UFMG/ICEx/DCC 36
Algoritmo A Record Global State
. Variables:
node statei = nil; {Estado local do substrato}
edge stateji = ∀ nj ∈ Neigi; {Estado da aresta (nj → ni)}
recorded i = false; {Indica se o estado local já foi registrado}
received ji = false ∀ nj ∈ I Neigi. {Indica se marker já foi recebido de nj}
. Input:
msgi = nil.
Action if ni ∈ N0: (1)
{Estado do substrato é registrado}
node statei ← σi
{Marca que registrou o estado local}
recorded i ← true;
{Envia marker, com o estado local, em todas as arestas de saída}
Send marker to all nj ∈ O Neigi.
UFMG/ICEx/DCC 37
Algoritmo A Record Global State
. Input:
msgi = marker | origini(msgi) = (nj → nj).
Action: (2)
{Indica que recebeu marker de nj}
received ji → true;
{Faz o registro do estado local como descrito na ação (1), se ainda não fez}
if not recorded i
then begin
node statei ← σi
recorded i ← true;
Send marker to all nk ∈ O Neigi.
end
UFMG/ICEx/DCC 38
Algoritmo A Record Global State
. Input:
msgi = sub msg | origini(msgi) = (ni → nj).
Action: (3)
{O susbtrato recebeu uma msg de nj que deve ser registrada na variável edge stateji .
Essa msg não é “consumida” pelo algoritmo de Superimposição.}
if recorded i
then if not received ji
then edge stateji ← edge state
j
i
⋃
{msgi}.
UFMG/ICEx/DCC39
Observações sobre o
algoritmo A Record Global State
• As ações executadas pelo algoritmo são atômicas
– Isto evita que o nó execute a computação do substrato entre o registro do
estado local e o envio de markers pelo algoritmo de superimposição (ações
1 e 2 no algoritmo)
• A ação 3 indica apenas a observação de uma msg que deve ser tratada pelo
substrato
– Essa msg não é consumida pelo algoritmo de superimposição nem implica
em qualquer relação de causalidade entre as duas computações
• Se G é fortemente conectado e todas as arestas são FIFO, então o algoritmo
A Record Global State registra um estado global
UFMG/ICEx/DCC 40
Coleta de estados globais de forma centralizada:
Caso 1
• Seja um estado global definido pela união de cada k-ésimo estado local na
seqüência Σi de cada nó ni participante da computação do substrato
• Neste cenário, seja uma função f(k) que deve ser aplicada ao estado global
coletado em k com o valor obtido em k − 1 para k > 1
– Neste caso, o estado das arestas não é importante, ou seja, não estamos
interessados se existem mensagens em trânsito nas arestas
– Exemplo: simulação dirigida pelo tempo (seção 10.2)
• Solução simples:
– Cada nó ni envia o seu estado local para um líder
– O líder calcula a função assim que tem o estado de todos os nós
UFMG/ICEx/DCC 41
Coleta de estados globais de forma centralizada:
Caso 2
• Seja um estado global a ser registrado onde o estado de cada aresta deve
ser o conjunto vazio
• Solução centralizada pode verificar facilmente se o estado de cada aresta é
vazio ou não
– Cada nó envia para o líder o seu estado local com o número de mensagens
recebidas e enviadas até o momento em cada aresta Ini e Outi respectiva-
mente
– Líder verifica para cada aresta e se o número de mensagens enviadas em
e é igual ao número de mensagens recebidas por e
– Neste caso, um estado do sistema onde todas as arestas têm um conjunto
vazio é um estado global
UFMG/ICEx/DCC 42