1 of 34

Algoritmos Distribuídos

MAC0219/5742

Alfredo Goldman

2 of 34

Algoritmos Distribuídos

Sem memória compartilhada → Troca de mensagens

Suposições:

  • Cada nó pode enviar e receber mensagens de todos os outros
  • Os canais de comunicação enviam mensagens corretas, mas não necessariamente na ordem
  • O tempo de comunicação é arbitrário, mas finito
  • Cada nó tem seu ID

3 of 34

Primitivas

  • send( MessageType, Destination [, parameters])
  • receive(MessageType [, parameters])
    • Bloqueante

Mas, na prática em comunicação baseada em TCP

  • Tem que conhecer a topologia
  • Heterogênea
  • Padrões como MPI e RPC

4 of 34

Bakery distribuído

Implementação com dois processos por nó:

int myNum = 0

set of deferred nodes ← empty set

5 of 34

Bakery (Main)

loop forever� non critical section� myNum = choose a number� for all other nodes N� send( request, N, myID, myNum)� await replies from all other nodes� critical section� for all nodes N in deferred� remove N from deferred� send( reply, N, myID)�

6 of 34

Bakery (receive)

int source, requestedNum�loop forever� receive( request, source, requestNum)� if (requestNum < myNum)� send( reply, source, myID)� else� add source to deferred

7 of 34

Problemas

  • Números iguais
    • Solução usar um desempate
  • Escolha dos números
    • Cada nó deve escolher um número maior do que todos que conhece
    • myNum = highestNum + 1
  • Nós fora da seção crítica podem ter
    • myNum = 0
    • Solução: Variável adicional requestCS

8 of 34

Bakery distribuído (Ricart-Agrawala)

int myNum = 0

set of deferred nodes ← empty set

int highestNum = 0

boolean requestCS = false

9 of 34

Ricart-Agrawala (Main)

loop forever� non critical section� requestCS = true� myNum = highestNum + 1� for all other nodes N� send( request, N, myID, myNum)� await replies from all other nodes� critical section� for all nodes N in deferred� remove N from deferred� send( reply, N, myID)�

10 of 34

Ricart - Agrawala (receive)

int source, requestedNum�loop forever� receive( request, source, requestNum)� if (!requestedCS or requestNum < myNum)� send( reply, source, myID)� else� add source to deferred

11 of 34

Limitações

Pode ser ineficiente com um grande número de nós

Não se beneficia da ausência de contenção

Proposta alternativa:

Usar um token

exclusão mútua é automática

como evitar deadlock e starvation?

Vetores distribuídos: requested e granted

12 of 34

Token

boolean haveToken = true no nó 0, false nos outros

int array[NODES] requested = [0,..., 0]

int array[NODES] granted = [0,...,0]

int myNum = 0

boolean inCS = false

(três processos)

13 of 34

sendToken

if exists N such that requested[N] > granted[N]

for some such N

send( token, N, granted)

haveToken = false

14 of 34

Main

loop forever� non-critical section� if !haveToken � myNum = myNum + 1� for all other nodes N� send(request, N, myID, myNum)� receive( token, granted)� haveToken = true� inCS = true� critical section� granted[myID] = myNum� inCS = false� sendToken

15 of 34

Receive

int source, reqNum

loop forever� receive(request, source, reqNum)� requested[source] = max( requested[ source], reqNum)� if haveToken and !inCS� sendToken�

16 of 34

Propriedades Globais em Sistemas Distribuídos

Não há a possibilidade de tirar uma foto instantânea

Mensagens levam um tempo > 0

Mas, dá para garantir consistência

Primeiro problema

Finalização distribuída

Simples com memória compartilhada

Fácil com um coordenador

17 of 34

Para complicar vamos imaginar que há uma topologia

Ok, ela é conexa :)

Motivação um nó começa mandando mensagens para os seus vizinhos

Processo recursivo

Quando receber a confirmação de todos que acabou, acabou :)

​

Nó 1

Nó 2

Nó 3

Nó 4

18 of 34

algoritmo preliminar

inDeficit i[E] - número de mensagens recebidas menos respondidas pelo nó i na aresta E

outDeficit i - diferença entre o número de mensagens enviadas nas arestas e respondidas

Algoritmo termina quando

outDeficit da origem chegar a 0

19 of 34

Nó origem

int outDeficit = 0�Computação� for all outgoing edge E� send(message, E, myID)� increment outDeficit� await outDeficit = 0� announce system termination

Receive Signal� receive(signal, source)� decrement outDeficit��

20 of 34

Outros nós

int array[incoming] inDeficit = [0,...,0]�int inDeficit = 0�int outDeficit = 0�send message� send(message, destination, myID)� increment outDeficit

Receive message� receive(message, source)� increment inDeficit[source] and inDeficit��

21 of 34

Outros nós

send signal� when inDeficit > 1 or (inDeficit == 1 and isTerminated and outDeficit == 0)� E = some edge E with inDeficit[E] != 0� send(signal, E, myID)� decrement inDeficit[E] and inDeficit

receive signal� receive(signal, ...)� decrement outDeficit

Pode dar problema… solução árvore geradora

Para evitar estouros, pode se usar números reais e mandar um pedaço��

22 of 34

Snapshots

Como tirar uma foto do sistema?

Onde podem estar as mensagens?

  • enviadas e em trânsito
  • recebidas

Algoritmo Chandy&Lamport (assume canais FIFO)

​

Nó 1

Nó 2

m4, m3, m2

23 of 34

ideia: marcadores

Os receptores registram as mensagens em trânsito

24 of 34

Consenso

Fácil se não há falhas

Cada nó manda informações para todos os outros

Os nós usam o mesmo algoritmo e chegam ao mesmo resultado

Dois tipos de falhas

Quebra - Um nó para de mandar mensagens

Falhas Bizantinas - Um nó pode mandar mensagens arbitrárias

25 of 34

Problemas dos generais bizantinos

Mensageiros confiáveis

Não há problemas nos canais

Generais podem ser traidores

Cada general toma uma decisão individual

Atacar ou Recuar

Decisões de consenso são boas

Mas, se apenas um subconjunto dos generais atacar → problema

26 of 34

Tentar ver um pouco da intuição

A

R

A

R

R

A

A

27 of 34

Algoritmo Trivial

planType finalPlan�planType array[generals] plan

plan[myID] = choose Attack or Retreat�for all other general G� send(G, myID, plan[myID])�for all other general G� receive(G, plan[G])

finalPlan = majority(plan)

28 of 34

Exemplo com três generais

1 deles falha

1 A

2 R

3 A

29 of 34

Solução

Não estamos usando o fato que generais são leais

Ideia: Adicionar rodadas, os leais sempre mandarão a mesma coisa

​

30 of 34

Algoritmo duas fases 1/2

planType finalPlan�planType array[generals] plan�planType array[generals, generals] reportedPlan�planType array[generals] majorityPlan

plan[myID] = choose Attack or Retreat�for all other generals G� send(G, myID, plan[myID])�for all other generals G� receive(G, plan[G])

31 of 34

Algoritmo duas fases 2/2

for all other generals G� for all other generals G' except G� send(G', myID, G, plan[G])�for all other generals G� for all other generals G' except G� receive(G, G', reportedPlan[G, G'])

for all other generals G� majorityPlan[G] = majority(plan[G] U reportedPlan[*, G])�majorityPlan[myID] = plan[myID]�finalPlan = majority(majorityPlan)

32 of 34

ideia usar árvores de conhecimento

Uma representação virtual sobre o que se sabe

Ele me disse que …

Funciona para falhas bizantinas

Para t traidores o número de generais deve ser ao menos 3 t + 1

t rodadas são necessárias

mas o número de mensagens é enorme

(n - 1) + (n - 1)* (n - 2) + (n - 2) * (n - 3) + ...

33 of 34

Dá para simplificar para o caso de falhas?

Inundação

planType finalPlan�set of planType plan = choose Attack or Retreat�set of planType receivedPlan

do t + 1 times� for all other generals G� send(G, plan)� for all other generals G� receive(receivedPlan)� plan = plan U receivedPlan� finalPlan = majorityPlan

34 of 34

Sim, tem muito mais...

King, que manda menos mensagens, mas tolera menos traidores

Paxos, para ambientes assíncronos não bizantinos

BFT, para ambientes assíncronos bizantinos

POW, para ambientes assíncronos com blockchain

​