Impossibility of Distributed
Consensus with One Faulty
Process
Michael J. Fischer
Nancy A. Lynch
Michael S. Paterson
1985
Apresentado por Nazareno Andrade
Roteiro
Introdução
 Modelo do sistema
 Prova do resultado
 Conclusões

Introdução

Problema:

Consenso de um sistema de processos
distribuído sobre um valor de um conjunto
pré-determinado.
•
•
•
•
Processamento de dados distribuídos;
Sistemas de arquivos distribuídos;
Aplicações distribuídas tolerantes a falhas;
Etc.
Introdução

Falhas.

O consenso é Impossível em um
sistema assíncrono com possibilidade
de uma falha.

“Nenhum protocolo de consenso
completamente assíncrono pode tolerar
mesmo uma falta.”
Introdução

O sistema não difere entre um processo
lento e um processo morto.

Se o consenso depende de um processo
morto, o sistema esperará para sempre.

O formalismo para estas afirmações
segue.
Modelo do Sistema

Completamente assíncrono





Nenhuma restrição sobre as velocidades
relativas dos processos ou o tempo de
entrega das mensagens;
Não há relógios sincronizados;
Sistema de mensagens confiável;
É impossível detectar a morte de um
processo;
Processos falham por parada.
Modelo do Sistema
Consenso simples (“weak”)



Cada processo começa com um valor em
{0,1}
Um processo correto decide indo para um
valor de decisão em {0,1}
Todos os processos corretos devem escolher o
mesmo valor.
Consenso
simples
(“weak”)
Consenso
mais
complexo
Restrições
fortes
sobre as
falhas
Restrições
fracas
sobre as
falhas
Modelo do Sistema:
Protocolo

Um protocolo de consenso é um
sistema assíncrono de 2 ou mais
processos.


Os processos são autômatos que se
comunicam por meio de mensagens;
As mensagens são entregues por um
sistema de mensagens global confiável.
Modelo do Sistema:
Sistema de mensagens





Uma mensagem é um par (p,m)
Atomic broadcasting assumido;
Não-determinístico;
Mantém um buffer global;
Duas primitivas:


send (p, m):
receive (p):
• É permitido que receive retore  um número
finito de vezes, mesmo se (p,m) está no buffer.
Modelo do Sistema:
Processo

Processo:
• Um registro de input xp
• Um registro de output yp = {b, 0, 1},
inicializado em b e “write once”.
• Capacidade de armazenamento interna
ilimitada
• Xp + Yp + armazenamento interno +
program counter = estado interno.
Xp
Program counter
armazenamento
Yp
Modelo do Sistema:
Execução de um processo

O resultado do processamento depende
do input, da comunicação e das funções
de transição.

Um processo age deterministicamente
de acordo com sua função de transição.

A função altera o estado interno do
processo de acordo com o input

Se Yp  b então o processo está num
estado de decisão.
Modelo do Sistema:
Configuração


Configuração do sistema:
 Estados internos de todos os
processos
 Conteúdo do Buffer de mensagens
Configuração inicial:
 Todos os processos em estado inicial
 Buffer vazio.
Modelo do Sistema:
Steps

Um step primitivo de um processo que
leva uma configuração a outra.
• receive(p) -> novo estado interno ->
envia um número finito de mensagens;

Pode ser definido por um par (p,m) = e,
um evento.
Modelo do Sistema:
Steps (cont.)

e(C) é então a configuração obtida pela
aplicação de e a C;
C0

e0
C1
e1
C2
e2
C3
(p, ) pode ser sempre aplicado  não
há deadlocks.
Modelo do Sistema:
Runs e Schedules


Schedule:  = e1, e2, e3,…, en aplicáveis a
C em ordem.
 Finita ou infinita
Run: s = step1, step2, … stepn
associada.
C0
C0
e0

C1
C3
e1
C2
e2
C3
 = {e0, e1, e2}
Modelo do Sistema:
Mais algumas definições

  finita t.q. (C)=C’  C’ é alcançável
(reachable) a partir de C;

Se C é uma configuração inicial, então
C’ é acessível.

Todas as configurações consideradas
são acessíveis.
Modelo do Sistema:
Lema 1

“Suponha que em alguma configuração C as
schedules 1 e 2 levem às configurações C1
e C2, respectivamente. Se os conjuntos de
processos dando steps em 1 e 2 são
disjuntos, então 2 pode ser aplicado a C1 e
1 pode ser aplicado a C2 e ambas levarão à
mesma configuração C3”.

“Comutatividade” das Schedules.
Modelo do Sistema:
Lema 1 (cont.)

Prova:

Definição do sistema.
P1= {0,b}
1
C0
C1
2
1
2
C2
C3
1
P2 {0, b}
P3{0, b}
2
P1= {0,b}
P1= {1,1}
P2 {1, 0}
P2 {0, b}
P3{1, b}
P3{0, b}
2
P1= {1,1}
P2 {1, 0}
P3{1, b}
1
Modelo do Sistema:
Definições

Uma configuração do sistema possui um
valor de decisão v se algum processo p
está no estado de decisão com yp = v
(v!=b).

Um protocolo de consenso é
parcialmente correto se


Nenhuma configuração acessível possui
mais de um valor de decisão;
Para cada v  {0,1} alguma configuração
acessível tem valor v.
Modelo o Sistema:
Definições

Processo correto - infinitos steps em um run.
Processo falho – número finito de steps

Run admissível:




No máximo um processo é falho
Todas as mensagens enviadas a processos corretos
são eventually recebidas.
Run de decisão:

Algum processo atinge estado de decisão nesta run.
Modelo do Sistema:
Definições

Protocolo consenso totalmente
correto apesar de uma falta:
 Parcialmente correto
 Toda run admissível é uma run de
decisão
•Nenhuma configuração
acessível possui mais de um
valor de decisão;
•Para cada v  {0,1} alguma
configuração acessível tem valor v.
•Toda run admissível é uma run de
decisão
•Consenso
•Não trivialidade
•Terminação
Modelo do Sistema:
Valência

Sendo V o conjunto de valores de
decisão das configurações alcançáveis a
partir de C
 Se | V | = 2, C é bivalente;
 Se | V | = 1, C é univalente;
• V = {1}, C é 1- valente;
• V = {0}, C é 0- valente.
Prova do Resultado:
Teorema
“Nenhum protocolo de consenso é
totalmente correto apesar de uma
falta.”

Prova:


Existe alguma configuração inicial bivalente;
É possível construir uma run admissível que
evite sempre dar o step que decidiria por
um valor.
Prova do Resultado:
Lema 2

“Existe uma configuração inicial
bivalente.”

Prova por contradição
 Hipótese: Não existem estados iniciais
bivalentes.

Pela definição


Configurações iniciais 0 e 1-valentes (não trivialidade).
C0 é 0-valente e C1 é 1-valente
• Existem C0 e C1 que diferem apenas em um
processo p ( que é decisivo ).
Prova do Resultado:
Lema 2
C0
0


1
0
1
1
0
1
0
0
1 C1
Aplicando-se schedules em que p não
dá passos (falha?), o estado interno de
C0 e C1 será idêntico, com exceção de
xp de p
C0 e C1 eventually atingirão um mesmo
valor de decisão.
Prova do Resultado:
Lema 2


Mas C0 e C1 têm valências diferentes.
C0 ou C1 é bivalente  contradição.
C0 - 0-valente
diferem
em xp
 (p não dá passos)
decidem
em v
C1 - 1-valente

“Existe uma configuração inicial
bivalente”.
Prova do Resultado:
Lema 3




Seja C uma configuração bivalende de P
e e=(p,m) um evento que é aplicável a
C.
Seja  o conjnto das configurações
atingíveis a partir de C sem aplicar e, e
 ={ e(E) | E   }.
 possui uma configuração bivalente.
I.e., é possível ir de uma configuração
bivalente a outra por uma schedule
não-vazia.
Prova do Resultado:
Lema 3
Se
C
e
Então * tal que
C
*

E
e
B

bivalente

 possui uma configuração bivalente.
Prova do Resultado:
Lema 3

Prova por contradição
 Hipótese:  não possui nenhuma
configuração bivalente.

Pela definição
 Existem E0 e E1, 0 e 1-valentes,
respectivamente;
Prova do Resultado:
Lema 3

 possui estados 0 e 1-valentes:



E0 é 0-valente
Se E0   então F0 = e(E0)    F0 is 0valente
Se E0   então existe F0   do qual E0 is
reachable  F0 is 0-valente

Em ambos os casos, F0 é 0-valente e pertence
a

Idem para uma configuração 1-valente
Prova do Resultado:
Lema 3

Para e=(p,m) e e’=(p’,m’):

Ca e Cb tal que Ca = e’(Cb)  
• Ca bivalente e Cb 1-valente
D0 = e(Ca)   é 0-valente
 D1 = e(Cb)   é 1-valente

e’
Ca
e
Cb
D0
D1
e’
Prova do Resultado:
Lema 3

se em e=(p,m) e e’=(p’,m’) p’  p’
podemos aplicar o lema1
(comutatividade)
Ca
e’
Cb
D0
e
e
D1
e’
Mas D0 é 0 valente e D1 é 1-valente 
contradição
Prova do Resultado:
Lema 3

A outra possibilidade é p’=p

Considere uma schedule  de uma deciding
run em que p pára. Seja A = (Ca).
C0
e

D0
e

E0
e’
C1
A é bivalente 
e
A
contradição
D1
e’
e

E1
Prova do Resultado:
Lema 3

Pela contradição da hipótese “ não
possui nenhuma configuração
bivalente”, provou-se que

É possível sempre ir de um estado
bivalente a outro por uma schedule
não-vazia.
Prova do Resultado:
Impossibilidade

Pelos lema 2 e 3:



É possível, partindo de uma configuração
inicial em que o resultado não está
previamente determinado construir uma run
admissível que evita para sempre a decisão.
Sempre tomar um passo para outro estado
não determinado.
Esta run será infinita.
Prova do Resultado:
Impossibilidade

Assim, pela contradição da hipótese da
prova:
Não existe um protocolo de
consenso totalmente correto
apesar de uma falha.
Conclusões

O consenso em sistemas totalmente
assíncronos é impossível.

Para possibilitar um consenso
satisfatório é necessário mudar o
modelo



Sincronismo
Introduzir possiblidade de consenso
Prover uma forma de detectar a morte de
processos