Protocolo de Ordem Total
Fernando Ney da Costa Nascimento
Multicast com ordem total

Camadas abaixo:




Camada Multicast com Ordem Causal (MOC).
Camada de Gerenciamento de Grupo.
Idéia: Examinar o C-DAG e determinar a ordem
total (em todos os processos).
Sem mensagens adicionais além das mensagens da
camada MOC.
Esboço do Algoritmo
G = {Ø,Ø}
//DAG causal
A=Ø
//msg´s com ordem total
wave = 1
forever
when causal-deliver(mij), insert mij in G
loop until exit
compute C(G)
//candidatos
compute S(G)
//fontes
if Consensus(G)
deliver S(G) in a deterministic order
A=AUS
wave++
else exit
Definições



C(G): conjunto de mensagens candidatas a serem
entregues. Raízes do grafo G. (candidatas)
S(G): conjunto de mensagens a serem entregues em
uma determinada onda do protocolo. (fontes)
Entrega é realizada quando Consensus é satisfeito. O
protocolo deve garantir que cada processo irá
entregar o mesmo conjunto de mensagens S (fontes).

O Consensus é atingido quando S(G) não pode mudar,
mesmo se mais mensagens são recebidas.
Consenso

Uma simples estratégia para o consenso é esperar
uma mensagem de cada processo no C-DAG e
entregar as raízes do grafo (fontes) em uma ordem
deterministica.



Sem custo adicional de mensagens
O sistema opera na velocidade do processo mais lento
É possível dar prioridade as primeiras mensagens
recebidas com base na maioria dos processos.
Entrega Antecipada



A idéia é desenvolver uma regra de estabilidade que
funciona sem necessitar que uma mensagem seja
recebida de cada processador.
O conjunto S deve permanecer o mesmo em cada
possível extensão G´ de G. (Condição de Segurança)
G´ estende G se e somente se G  G´:

Future(G) = {G´ | G´ seja uma extensão de G}
Condições de Segurança (Estabilidade)

Cada mensagem candidata não-fonte em G não pode torna-se
uma fonte em G´.


Cada fonte em G é também uma fonte em G´.


se m  S(G), então m  S(G´) para todo G´  Future(G)
Mensagem não recebidas não podem torna-se fontes em G´.


se m  C(G) \ S(G), então m  C(G´) \ S(G´) para todo G´ 
Future(G)
se i  tail(G), então para todo j, mij  S(G´) para todo G´ 
Future(G)
Se G satisfaz as 3 condições acima, G é dito ser estável.
* tail(G): conjunto de processos com mensagens em G.
Condições de Vivacidade


Enquanto as condições de segurança garantem que
cada processo irá receber os mesmos conjuntos de
mensagens, é preciso ainda garantir, que
eventualmente, alguma mensagem seja entregue.
Condições de Vivacidade:


se |tail(G)| = M, então S(G) ≠ 
se |tail(G)| = M, então G é estável
Protocolo TOP

Voto de Processo:



A 1a mensagem mij do processo pi em G vota nas
mensagens candidatas do DAG causais a mij.
Cada mensagem vota em si própria.
A cada mensagem está associado um vetor de votos,
VV(m)[i].

VV(m)[i] =



1, se processo i votou em m
0, se processo i votou mas não em m
*, se processo i ainda não votou
Protocolo TOP

Número de processos que enviaram mensagens causualmente a m:


Número de processos que ainda não votaram:


u = |P – ntail(G)| = |{j : VV(m)[j]=*}| = M – ntail(G)
Número de votos de uma mensagem candidata:


ntail(m) = |tail(m)|
nvt(m) = |{i : VV(m)[i]=1}|
Mensagens candidatas são comparadas com base nos votos que as mesmas
recebem:


votes(m1,m2) = |{j : VV(m1)[j]=1  VV(m2)[j]=0}|
win(m1,m2) =



1, se votes(m1,m2) > threshold
0, se votes(m2,m1) > threshold
X, casos contrários
* threshold = M/2
Protocolo TOP

O valor de win é definido com base no grafo G atual. É necessário uma função em relação as
extensões de G, G´.


O único interessante modo de G´ estender G é especificando votos de processos que ainda não
votaram. Dessa forma, 1  win[G´](m1,m2) se e somente se o número de processos que votam
em m1 mas não em m2,+ o número de votos não processados, seja maior que threshold:




1  win[G´](m1,m2) se votes(m1,m2) + u > threshold
X  win[G´](m1,m2) se X  win(m1,m2)
0  win[G´](m1,m2) se 1  win[G´](m2,m1)
Ainda temos:



win[G´](m1,m2) = {win[G´](m1,m2), onde G´ estende G}
1  win[G´](m1,m2)  votes(m1,m2) + u ≤ threshold
win[G´](m1,m2) = {1}  win(m1,m2) = 1
Seja M(G) o número de candidatos no DAG causal G. O conjunto de fontes, S(G), é definida
como:


i  S(G)  i  M(G)  j  M(G), 1  win[G´](j,i)
ou seja, a mensagem i é uma fonte se ela nunca perde para qualquer outra mensagem j já em G.
TOP: Regras de Entrega
1) Entrega antecipada
Se
m  M(G)\S(G) m´  S(G), win[G´](m´,m) = 1

s  S(G), nvt(s) > threshold
2) Entrega normal
Se
ntail(G) = M
TOP: Corretude


Como mensagens são recebidas em ordem causal, um processo p que já
tem uma mensagem em G, não irá votar para mensagens a serem
recebidas. A primeia mensagem de p vota para as candidatas que ela
causalmente segue que já estão em G.
Entrega Antecipada:



Existe uma fonte s com pelo menos threshold+1 votos. s pode ainda
compartilhar esses votos com outras candidatas, mas todos os processos
(threshold+1) que ja votaram para s não iram votar para mensagens ainda
não recebidas. Quando s´ é recebida, se s´ é uma candidata, a mesma não se
tornará um fonte. s´ irá perder para s, desde que a maioria votou para s e não
irá votar para s´: votes(s,s´) > threshold
Uma candidata não-fonte i não irá torna-se uma fonte se i perde para uma
candidata j: win(j,i) = 1  win[G´](j,i) = 1
Entrega normal:

A condição de vivacidade é satisfeita desde se ntail(G) = M, ou a entrega
antecipada é satisfeita ou todas as candidatas são entregues.
TOP: Tolerância a falhas


Mudanças de configuração no grupo são
consistentemente informadas pela camada de
gerenciamento de grupo.
Um processo falho vota numa mensagem candidata
m da seguinte forma:

VV(m)[i] = 0, caso i seja um processo falho
TOP: Exemplo
E
D
A
H
C
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H
* 0 * * * * * *
M
B
*
1
*
*
*
*
*
*
*
*
M
C
*
0
*
*
*
*
*
*
*
*
M
D
*
0
*
*
*
*
*
*
*
*
M
E
*
0
*
*
*
*
*
*
*
*
M
F
*
0
*
*
*
*
*
*
*
*
M
G
*
0
*
*
*
*
*
*
*
*
M
H
*
0
*
*
*
*
*
*
*
*
M
I
*
0
*
*
*
*
*
*
*
*
M
J
*
0
*
*
*
*
*
*
*
*
I
*
J
*
B
TOP: Exemplo
M
A
A B C D E F G H I
* 0 * * * * * * 0
M
B
*
1
*
*
*
*
*
*
0
*
M
C
*
0
*
*
*
*
*
*
0
*
M
D
*
0
*
*
*
*
*
*
0
*
M
E
*
0
*
*
*
*
*
*
0
*
M
F
*
0
*
*
*
*
*
*
0
*
M
G
*
0
*
*
*
*
*
*
0
*
M
H
*
0
*
*
*
*
*
*
0
*
M
I
*
0
*
*
*
*
*
*
1
*
M
J
*
0
*
*
*
*
*
*
0
*
J
*
B
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 * * * * 0 * 0
M
B
*
1
*
*
*
*
1
*
0
*
M
C
*
0
*
*
*
*
0
*
0
*
M
D
*
0
*
*
*
*
0
*
0
*
M
E
*
0
*
*
*
*
0
*
0
*
M
F
*
0
*
*
*
*
0
*
0
*
M
G
*
0
*
*
*
*
1
*
0
*
M
H
*
0
*
*
*
*
0
*
0
*
M
I
*
0
*
*
*
*
0
*
1
*
M
J
*
0
*
*
*
*
0
*
0
*
J
*
G
B
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 * * * 0 0 * 0
M
B
*
1
*
*
*
0 1
*
0
*
M
C
*
0
*
*
*
0 0
*
0
*
M
D
*
0
*
*
*
0 0
*
0
*
M
E
*
0
*
*
*
0 0
*
0
*
M
F
*
0
*
*
*
1 0
*
0
*
M
G
*
0
*
*
*
0 1
*
0
*
M
H
*
0
*
*
*
0 0
*
0
*
M
I
*
0
*
*
*
0 0
*
1
*
M
J
*
0
*
*
*
0 0
*
0
*
J
*
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 0 * * 0 0 * 0
M
B
*
1 1
*
*
0 1
*
0
*
M
C
*
0 1
*
*
0 0
*
0
*
M
D
*
0 0
*
*
0 0
*
0
*
M
E
*
0 0
*
*
0 0
*
0
*
M
F
*
0 1
*
*
1 0
*
0
*
M
G
*
0 0
*
*
0 1
*
0
*
M
H
*
0 0
*
*
0 0
*
0
*
M
I
*
0 0
*
*
0 0
*
1
*
M
J
*
0 0
*
*
0 0
*
0
*
J
*
C
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 0 * 0 0 0 * 0
M
B
*
1 1
*
1 0 1
*
0
*
M
C
*
0 1
*
1 0 0
*
0
*
M
D
*
0 0
*
0 0 0
*
0
*
M
E
*
0 0
*
1 0 0
*
0
*
M
F
*
0 1
*
1 1 0
*
0
*
M
G
*
0 0
*
0 0 1
*
0
*
M
H
*
0 0
*
0 0 0
*
0
*
M
I
*
0 0
*
0 0 0
*
1
*
M
J
*
0 0
*
0 0 0
*
0
*
J
*
E
C
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 0 0 0 0 0 * 0
M
B
*
1 1 1 1 0 1
*
0
*
M
C
*
0 1 1 1 0 0
*
0
*
M
D
*
0 0 1 0 0 0
*
0
*
M
E
*
0 0 0 1 0 0
*
0
*
M
F
*
0 1 1 1 1 0
*
0
*
M
G
*
0 0 1 0 0 1
*
0
*
M
H
*
0 0 0 0 0 0
*
0
*
M
I
*
0 0 0 0 0 0
*
1
*
M
J
*
0 0 0 0 0 0
*
0
*
J
*
E
D
C
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H I
* 0 0 0 0 0 0 0 0
M
B
*
1 1 1 1 0 1 0 0
*
M
C
*
0 1 1 1 0 0 0 0
*
M
D
*
0 0 1 0 0 0 0 0
*
M
E
*
0 0 0 1 0 0 0 0
*
M
F
*
0 1 1 1 1 0 0 0
*
M
G
*
0 0 1 0 0 1 0 0
*
M
H
*
0 0 0 0 0 0 1 0
*
M
I
*
0 0 0 0 0 0 1 1
*
M
J
*
0 0 0 0 0 0 0 0
*
J
*
E
D
H
C
G
B
F
I
TOP: Exemplo
M
A
A B C D E F G H I
1 0 0 0 0 0 0 0 0
M
B
1 1 1 1 1 0 1 0 0
*
M
C
0 0 1 1 1 0 0 0 0
*
M
D
0 0 0 1 0 0 0 0 0
*
M
E
0 0 0 0 1 0 0 0 0
*
M
F
0 0 1 1 1 1 0 0 0
*
M
G
1 0 0 1 0 0 1 0 0
*
M
H
0 0 0 0 0 0 0 1 0
*
M
I
0 0 0 0 0 0 0 1 1
*
M
J
0 0 0 0 0 0 0 0 0
*
J
*
E
D
A
H
C
G
B
F
I
TOP: Exemplo
M = 10
threshold = 5
ntail(G) = 9
u = M - ntail(G) = 1
M(G) = {B, F, I}
mi
nvt(mi)
votes
B
F
I
B
F
I
{A,B,C,D,E,G} = 6
{C,D,E,F} = 4
{H,I} = 2
B
1
2
F
3
2
I
6
4
-
TOP: Exemplo

S(G) = i  M(G)  j  M(G), 1  win[G´](j,i)

B  S(G)


F  S(G)



votes(B,F) + u = 4 ≤ threshold
votes(I,F) + u = 3 ≤ threshold
I  S(G)



nvt(B) = 6 > threshold
nvt(I) = 2 ≤ threshold
B  M(G), votes(B,I) + u = 7 > threshold
Entrega Antecipada

M(G)\S(G) = {I}


nvt(I) + u = 3 ≤ threshold  B  S(G), votes(B,I) = 6 > threshold
B  S(G), nvt(B) > threshold