Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, and Lary Stockmeyer
1985
Discussão dos algoritmos
g
e modelos
Por
Prof. Raimundo Macêdo, LaSiD/DCC/UFBA
Sincronia parcial
1 Δ/Φ é conhecido
1.
h id ((canais
i e processadores
d
síncronos)
í
)
2. Δ/Φ é desconhecido: para cada Run, existe Δ/Φ que é válido em [1,infinito)
3. Δ/Φ é conhecido e válido em algum instante: para cada Run, existe T onde Δ/Φ
é válido em [T,infinito)
[1,infinito) significa que desde o tempo 1 até antes do infinito Δ/Φ (n conhecido) é válido
[T,infinito) significa que existe um tempo T desconhecido a partir do qual Δ/Φ é válido
Se (2) ou (3) é válido,
então processadores (Φ) e/ou canais de comunicação (Δ) são síncronos parciais
Critérios de Correção
Suposições (assumptions)
A-ΔeΦ
F - modelo de falhas
N – número de processadores
t - resiliência 0 ≤ t ≤ N
Considere C = N – t, o conjunto dos processadores corretos, e qualquer Run
satisfazendo A
Considere também que processadores fora de C são caracterizados por F
•Consistência: q
quaisquer
q
dois p
processadores em C não decidem p
por valorem distintos
•Terminação: Se Run é infinito, então cada processador de C faz um decisão
•Unanimidade forte: se todos valores inicias (V) são idênticos e iguais a v, se algum
processador em C decide, então decide por v
•Unanimidade fraca: se todos valores inicias (V) são idênticos e iguais a v, se algum
processador em C decide e |C| = N, então decide por v
Modelo básico baseado em rodadas (Basic Round Model)
Processamento é dividido em rodadas de síncronas de troca de mensagens
Cada rodada
•send
•receive
•computation
Não necessariamente todas as mensagens enviadas numa rodada são entregues na
mesma rodada (algumas podem ser perdidas), mas
GST ---- existe uma rodada a partir da qual todas a mensagens enviadas por
processadores corretos são entregues na rodada em que foram enviadas
N h
Nenhum
processador
d conhece
h
GST
Protocolos de Consenso para o modelo básico de rodadas
Alegação (claim) – a ser provada
Os protocolos descritos satisfazem unanimidade forte
Notações dos algoritmos
Proper
ope Value:
a ue se todos
odos os valores
a o es iniciais
c a s são v,, v é o único
ú co p
proper
ope
value; se pelo menos 2 valores iniciais são distintos, qualquer valor
inicial é um proper value.
Processadores mentem uma variável proper que é sempre
atualizada e sempre transmitida (biggybacked) junto a todas
mensagens enviadas
Consenso para fail-stop e omissions
Algoritmo 1: N ≥ 2t + 1
Considere pi
Proper := vi
Mensagens transmitidas carregam proper (m.proper)
Mensagens recebidas atualizam properi; properi := properi ∪ m.proper
(para cada receive[m.proper]).
ÆProperi sempre terá proper value (fácil verificar)
As rodadas são organizadas numa seqüência de fases
Trying (3 rodadas)
Lock-release
Lock
release (1 rodada)
Fase h pertence ao processador h mod N
Essência do algoritmo --- fase k para pi , onde i = k (mod N) – 4 rodadas
1ª rodada : todos enviam p
para p
pi seus valores acceptable.
p
Então, p
pi testa: existe um ou
mais valores que são acceptable para N – t processadores?
Se sim propõe um valor v (se existe mais de um possível, escolhe um aleatoriamente)
2ª rodada: pi broadcast valor proposto (v,k)
Processos que recebem (v,k), adotam (v,k), liberando outros locks em v
3ªª rodada: quem recebeu ((v,k),
) send ((ack,k))
pi testa: se recebeu t + 1 (ack,k). Caso positivo decide (obs: veja que agora existem
t+1 processadores que trancaram (v,k) e pelo lema 3.1.2 v continuará trancado em k ou
k’ k’ >k
k’,
>k. Î não
ã há possibilidade
ibilid d d
de existir
i ti um valor
l w, w ≠ v, onde
d N – t reconhecem
h
w
como acceptable ..... Porque no máximo teríamos t + 1
Discussão
Um valor v somente é acceptable
p
se é o único trancado (p
(por definição
ç e acceptable)
p
)
Para haver um valor w ≠ v que fosse proposto por pi, pi teria que ter recebido de N-t
processos w como acceptable... Ora, isso é impossível por que t +1 processos têm v
como acceptable (e não vão mudar de opinião – lemmas 1 e 2).
Prova (considere os quoruns abaixo)
((a)) quorum t+1: processos que têm v trancado
(b) quorum N - (t+1) : processos que não necessariamente teriam v trancado e portanto
poderiam ter w como acceptable
( ) quorum N - t : processos que precisariam
(c)
i i
tter w como acceptable
t bl para propor w
Para que w seja proposto e portanto acceptable para N-t, teríamos...
b ≥ c Î N – t – 1 ≥ N – t Î N – N ≥ t – t + 1 Î 0 ≥ 1 (impossível)
Ou seja, se t + 1 decide v, resta então N - t -1 o que não é suficiente para n-t propor w.
Outras discussões (contribuições): qual a relação entre t e N?
1) a ≤ N (para que seja possível uma decisão) Î t + 1 ≤ N Î t < N
2) a ∩ c ≠ vazio para garantir consistência
consistência. Para que isso ocorra é necessário que |a|
+ |c| > N. Î t+1+N-1 = N + 1 > N.
3) Existem dois WAITs no programa (pelos quoruns a e c).
Outras discussões (contribuições): qual a relação entre t e N?
1) a ≤ N (para que seja possível uma decisão) Î t + 1 ≤ N Î t < N
2) a ∩ c ≠ vazio para garantir consistência. Para que isso ocorra é necessário que |a|
+ |c| > N.
N Î t+1+N-1 = N + 1 > N
N. Isso portanto é sempre garantido
3) Existem dois WAITs no programa (pelos quoruns a e c).
Wait N – t (sempre termina, pois N – t são corretos)
Wait t + 1 (depende da relação entre t e N – vide abaixo)
Ou seja,
o quorum t + 1 precisa ser menor ou igual ao numero de processos corretos N - t
T + 1 ≤ N – t Î N ≥ 2t + 1 (i)
Dado que (i) seja verdadeiro, qual o valor máximo para t?
Seria quando N = 2t + 1Î t = (N-1)/2
Os dois quoruns ficam assim:
N-t Î N – (N-1)/2Î (N+1)/2 .................. t + 1Î (N-1)/2 + 1Î (N+1)/2
Devido a N pares, deve-se usar o teto de (N+1)/2
Mais discussões
Se enfraquecermos a condição N ≥ 2t + 1, para, por exemplo, N ≥2t e alternarmos o
Al it
Algoritmo
para na 3ª rodada
d d ffazer WAIT t acks
k (ao
( invés
i é d
de tt+1),
1) então
tã pode
d haver
h
Inconsistência, apesar de garantir terminação.
Portanto para que haja interseção nos quoruns
Portanto,
quoruns, garantindo a terminação N ≥ 2t + 1.
1
Um processador pode trancar um valor v em vários instantes do algoritmo;
existe sempre um número de fase associado a um lock.
*** quando um valor v é trancado em pi?
Quando pi recebe uma mensagem lock (v,k) e manda uma ack na forma (ack,
) Observe q
que somente existe um único k p
para cada valor v ((lemma 3.1.1)....
)
k)....
Cada pi pode ter mais de um valor trancado
*** quando um lock é liderado?
Se p locks v na fase k = i mod N, então p crê que processador pi pode
decidir v na fase k
P somente libera lock (k,v) se aprende que sua suposição é falsa. Ou seja, que
“processador
processador pi poderia decidir v na fase k”
k é falso
Um valor v é acceptable
p
p
para p se p não tem outro valor com lock ((i.e,, somente
tem lock em v)
.... O algoritmo
Considere uma fase k
i = k mod N
s = 4k – 3 (primeira rodada de uma seqüência de 4 rodadas da fase k)
Rodada s – para todos os processadores – send
Cada processo envia {proper ∩ accaeptable) para pi; obs: no inicio apenas o valor
inicial
Ou seja, Send(pi, list); onde list = {proper ∩ accaeptable) e pi é o coordenador ou
responsável da fase k
Rodada s – para pi– receive
pi faz receive(p); wait receive de N - t
Rodada s – para pi somente – computation
pi tenta propor um valor v
se para dado v recebeu N-t {proper + accaeptable) então propõe v
(se houver mais de um v, um é escolhido aleatoriamente)
Considere uma fase k
Rodada s+1 = 4k – 2 (segunda rodada de uma seqüência de 4 rodadas da fase k)
-etapa send - somente pelo coordenador pi
Se para dado v, pi recebeu N-t mensagens {proper ∪ accaeptable)
então
Send(pj,
(pj msg)
g) p
para cada pj
pj, onde msg
g = ((lock k,v))
(se houver mais de um v, um é escolhido aleatoriamente)
senão va para a proxima fase k + 1
Rodada s+1 = 4k – 2 (segunda rodada de uma seqüência de 4 rodadas da fase k)
Etapa receive – todos processadores
Se foi recebido (lock,k,v) então lock v,k
S
Senao
va para ffase k +1
Considere uma fase k
Rodada s+2 = 4k – 3 (terceira rodada de uma seqüência de 4 rodadas da fase k)
Etapa send – todos processadores
Se foi recebido (lock
(lock,k,v)
k v)
Send(pi,k,ack) – envia ack k para coordenador pi
Libera qualquer outro lock em v
Outros locks em outros valores não são liberados
Rodada s+2 = 4k – 3 (terceira rodada de uma seqüência de 4 rodadas da fase k)
Etapa receive – coordenador pi
Se pi recebeu t +1 acks, pi decide v e continua
Rodada s + 3 = 4k (Lock-release )
Etapa send
Broadcast (v,h) para cada lock (v,h)
R d d s + 3 = 4k (L
Rodada
(Lock-release
k l
)
Etapa receive
Se o processador tem lock (v,h) e recebe lock(w,h`), v≠w e h`> h, então libera lock em v
Prova de Correção
Lemma 1- valores distintos trancados nunca têm o mesmo número de lock
O numero de lock esta associado ao numero fase onde o coordenador tentou gerar
o lock. Como somente existe um coordenador por fase e o coordenador não envia
mensagens para locks distintos na mesma fase, essa possibilidade é impossível.
Lemma 2- suponha que algum processo decide v na fase
f
k, e k é o menor numero
de fase em que uma decisão é feita. Então, pelo menos t + 1 processadores definiram
Lock v na fase k (i). Mais ainda, cada processo que criou lock v na fase k, a partir desse
momento
t sempre terá
t á um lock
l k para v com numero igual
i
l ou maior
i a k (ii)
(ii).
Prova. (i) esta claro pelo algoritmo.
Para provar (ii), suponha, por absurdo, que (ii) é falso.
Assuma que l é a primeira fase na qual um dos locks em v é liberado, sem, contudo,
ser substituído por outro lock em v com valor de fase maior que kk.
Observe que locks somente são liberados na rodada de lock-release. Portanto, assuma
que o lock em (v
(v,k)
k) foi liberado na fase l quando algum processador aprende que outro
processador tem um outro lock (w,h), onde k ≤ h ≤ l.
Já que pelo lema 1, não pode existir outro lock num valor w, w ≠ v, com fase k, então:
Portanto, podemos inferir que algum processador tem um lock em w com fase
associada h, onde K < h ≤ l (i)
Por outro lado, para (i) ser verdade, w foi encontrado “acceptable” para N – t
processadores na primeira rodada da fase h. O que por sua vez implica que pelo
menos N – t processadores não possuem lock em v na primeira rodada da fase h
(absurdo).
F lh Bizantinas
Falhas
Bi
ti
com A
Autenticação
t ti
ã
2 4 Corretude
2.4
• Dadas:
– Suposições A sobre os processadores e sobre a
sincronia da comunicação;
– Um tipo de falha F; e
– Um número N de processadores e um inteiro t (0 ≤ t ≤
N)
A corretude de um protocolo de consenso
t-resiliente é assim definido:
2 4 Corretude
2.4
• Para todo conjunto C contendo ao menos
N-t processadores, e toda execução R
que:
– Satisfaça as condições de A;
– os processadores em C sejam corretos; e
– Aos processadores que não estejam em C
seja permitido o tipo de falta F.
F
O protocolo deverá garantir:
2 4 Corretude
2.4
• O protocolo deverá garantir:
– Consistência: Dois processadores em C não decidam
diferentemente.
– Terminação: se R for infinita, então todo processador em C faz
um decisão.
– Unanimidade:
U
i id d
• Unanimidade Forte:
– Se todo valor inicial for v, e se todo processador em C decide, então
ele decide v.
• Unanimidade Fraca:
– Se todo valor inicial for v, se C contém todos os processadores, e
se todo processador decide, então ele decide v.
Protocolo
• Definições:
D fi i õ
– Ej: Função de autenticação de Pj;
– v é próprio se:
• Todos os processadores iniciam com o valor v;
• Existem
E i t
ao menos d
dois
i valores
l
iiniciais
i i i dif
diferentes,
t
ev
pertence a V.
– v é aceitável por Pj se:
• Pj não possui trava em algum outro valor diferente de
v;
– proof: conjunto das mensagens Ej (list,k)
recebidos por Pi e em que v é aceitável e próprio.
Protocolo (Round 1)
• Processo PJ ((send))
–
–
–
–
i=mod (k,N)
PROPER ← valor inicial
List ←valores aceitáveis em PROPER
Send Ej (list,k) para Pi
• Processo
P
Pi (i=mod(k,N))
(i
d(k N)) ((receive)
i )
– Recebe valores iniciais
– Ao receber 2t+1
2t 1 mensagens: (compute)
2t +1 (ou seja, não bloqueia)
– veja que (3t + 1) – t =
• Se não existem t+1 mensagens com um mesmo valor:
– PROPER ← todos os valores – domínio V
• Se
S existem
i
t+1
1 mensagens com um mesmo valor
l v:
– PROPER ← v
Protocolo (Round 2)
• Processo Pi (send)
– Se receber ao menos N-t mensagens com um
mesmo valor v (qque é acceptable
p
and p
proper
p )
):
• Broadcasts Ei (lock v, k, proof)
• Processo PJ (receive)
– Recebe Ei (lock v, k, proof);
– Se já existe lock v em fase h, com h < k:
(compute)
• Unlock (v,h);
(v h);
• lock (v,k);
Protocolo (Round 3)
• Processo
P
PJ (send)
(
d)
– Send Ack para Pi
• Processo Pi (receive)
– Recebe (Ack,k);
– Caso receba 2t+1 Ack: (compute)
• Decidir v.
Protocolo (Lock
(Lock-Release)
Release)
• Processo PJ (send)
– Broadcasts Ei (lock v, k, proof)
• Processo PJ (receive)
– Recebe Ei (lock vv, kk, proof);
– Lock (v,k);
(
(compute)
p )
– Se existe lock(w,h), com h < k e w ≠ v:
• Unlock (w,h)
– Se existe lock(v,h), com h < k:
• Unlock (v,h)
Falhas Bizantinas com Autenticação
Fase k
F
Round s=4k-3
Observação:
Para
k=1 => s=1
k=2 => s=5
etc.
Trying Fase
Com N-t mensagens
eceb das co
com o valor
ao v
recebidas
aceitável, v será proposto
na fase k
P2
P1
E2(list,k)
Pn
E1(list,k)
Pi
EJ(list,k):
(list k): Lista autenticada
de todos os valores
aceitáveis por PJ na fase k
E3(list,k)
EJ(list,k)
P3
PJ
Com t+1 mensagens
recebidas com o valor v
aceitável, v será
considerado um valor
aceitável.
i á l Caso
C
contrário,
ái
todo o domínio de valores
será aceitável.
Falhas Bizantinas com Autenticação
Fase k
F
Round s+1
Trying Fase
Pn
Pi broadcasts
Ei(lock v,
v k,
k proof),
proof)
propondo o valor v.
P2
P1
Ei(lock v, k, proof)
Ei(lock v, k, proof)
Ei(lock v, k, proof)
Pi
Ei(lock v, k, proof)
Ei(lock v, k, proof)
P3
PJ
Falhas Bizantinas com Autenticação
Fase k
F
Round s+2
Trying Fase
Lock (v,k)
Lock (v,k)
P2
P1
ack
Pn
Se forem recebidos ao
menos 2t+1 acks, Pi
decide por v.
ack
Decide (v,k)
Pi
ack
ack
Lock (v,k)
P3
PJ
Lock (v,k)
Falhas Bizantinas com Autenticação
Travam
o valor v
T processos
corretos + 1
Por quê 2t+1 acks
são necessários?
T processos
incorretos
T processos
corretos
Não h
Nã
haverá
áN
N-tt
processos
suficientes que
aceitem um
outro valor w
Falhas Bizantinas com Autenticação
Fase k
F
Round s+3
Lock (v,k)
P2
P1
Pn
Lock (v,k)
Ei(lock v, k, proof)
Ei(lock v, k, proof)
Lock-release Fase
Processos fazem
broadcast informando
que possuem um lock
em v na fase k: Ei(lock v,
k, proof)
Decide (v,k)
Pi
Lock (v,k)
Se algum processo
possuir um lock em um
round anterior, irá
atualizá-lo no round k
Ei(lock v, k, proof)
P3
Ei(lock v, k, proof)
PJ
Lock (v,k)
Falhas Bizantinas com Autenticação
• Lema 3.4: “É
É impossível que dois valores distintos sejam
validamente travados (locked) na mesma fase, se esta
fase pertencer a um processo correto
correto.”
• Prova:
– Para que dois valores distintos v e w sejam validamente
travados na mesma fase, o processo possuidor desta fase
precisaria ter enviado mensagens conflitantes propondo valores
distintos para processos diferentes
diferentes. Logo o processo possuidor
da fase não seria um processo correto (contradição).
Falhas Bizantinas com Autenticação
•
•
Lema 3
3.5:
5: “Suponha
Suponha que algum processo correto decidiu o
valor v na fase k, e k foi a primeira fase em que um processo
correto fez uma decisão. Portanto ao menos t+1 processos
corretos
t travaram
t
o valor
l v na fase
f
k.
k Assim,
A i cada
d um dos
d
processos corretos que travaram v na fase k sempre terão uma
trava em v associada a uma fase igual ou maior do que k.”
Prova:
– Como ao menos 2t+1 processos enviaram um ack para possibilitar
que o processo correto decidisse por v na fase k, então ao menos
t+1 processos travaram v na fase k. Para que esta trava seja
substituída pela trava em um outro valor w em um round posterior
((k+i),
), um outro processo
p
deve ter proposto
p p
este novo valor após
p
ter recebido mensagens de N-t processos indicando ser w
aceitável no round k+i (contradição)
Falhas Bizantinas com Autenticação
• Lema 3
3.6:
6: “Imediatamente
Imediatamente após uma fase lock
lockrelease que ocorre após GST (ou em GST), o
conjunto de valores travados por processos corretos
conterá no máximo um valor.”
• Prova:
– Direto da regra lock-release, onde um processo que recebe
uma mensagem autenticada informando que houve um
travamento em um valor v na fase k deverá liberar as travas
de fases anteriores, mantendo apenas a trava do valor v na
fase k.
Falhas Bizantinas com Autenticação
• Teorema 3
3.2:
2: “Assuma
Assuma o modelo básico com falhas
bizantinas e autenticação. Assuma N>=3t+1. Então
o Algoritmo 2 garante consistência, unanimidade
forte e terminação para um domínio arbitrário de
valores.”
• Prova:
– A prova de consistência e unanimidade forte é idêntica a
prova do
d T
Teorema 1
1.
– Para garantir terminação (segue)
Falhas Bizantinas com Autenticação
• Prova(Teorema 3
3.2
2 - Terminação):
– Considere uma trying fase k, pertencente a um processo
correto P, que é executada após uma fase lock-release,
ambas tendo ocorrido após GST.
– Pelo lema 3.6 existe ao máximo um valor travado por um
processo correto no início da trying fase k.
• Se este valor existir,, ele deve ser considerado próprio
p p p
por N-t
processos (destes N-2t >= t+1 corretos) no início da trying
fase k. Estes processos comunicaram (durante a fase lockrelease) a todos os processos que v é um valor aceitável e
com isso
co
sso v foi
o considerado
co s de ado ace
aceitável
tá e po
por todos os p
processos
ocessos
corretos no início da trying fase k.
• Caso não haja nenhum valor travado, todos os valores são
considerados próprios.
• O processo dono
d
d
da ffase poderá
d ád
decidir
idi por um valor
l aceitável
itá l
por todos os demais processos corretos.
Seminários
1)
2)
3)
4)
5)
6)
7)
Recuperação pró-ativa de falhas
T
Testes
d robustez
de
b
através
é d
de iinjeção
j
d
de ffalhas
lh
Consistência de Réplica
Armazenamento estável
C
Comunicação
i
ã em G
Grupo em Si
Sistemas
t
Di
Distribuídos
t ib íd Híb
Híbridos
id
State-Machine Approach
Distributed Checkpointing