Bizâncio, a capital do antigo Império Romano do Oriente, foi uma das cidades mais poderosas e ricas do mundo. No entanto, devido ao seu vasto território, Bizâncio frequentemente enfrentava invasões externas e rebeliões internas. Para defender suas fronteiras, Bizâncio enviava múltiplos exércitos, cada um comandado por diferentes generais. Alcançar consenso entre esses generais tornou-se um desafio significativo.
O Problema dos Generais Bizantinos tem uma relação próxima com o blockchain. Uma rede blockchain é uma rede distribuída onde os nós, como os generais bizantinos, devem alcançar consenso sobre transações e dados em um ambiente de rede não confiável.

Problema dos dois generais

O Problema dos Dois Generais é um caso especial do Problema dos Generais Bizantinos. O problema e sua prova de impossibilidade foram propostos pela primeira vez por E.A. Akkoyunlu, K.Ekanadham e R.V. Huber em seu artigo de 1975 "Algumas Restrições e Compromissos no Projeto de Comunicações de Rede". Em 1978, Jim Gray formalmente nomeou esse problema como "Problema dos Dois Generais" em seu livro "Notas sobre Sistemas Operacionais de Banco de Dados". Originalmente, foi usado para analisar as questões de alcançar consenso por meio da comunicação em uma ligação de comunicação não confiável. Atualmente, é comumente usado para ilustrar questões de consistência e consenso em sistemas distribuídos.

Definição do Problema:
Dois exércitos do país A, cada um liderado por um general, estão se preparando para atacar um exército do país B. O exército do país B está cercado em um vale, com os dois exércitos de A estacionados nas colinas de cada lado do vale. No entanto, o único caminho entre os dois exércitos de A passa pelo vale. O exército de B é mais forte do que qualquer um dos exércitos de A individualmente, mas se ambos os exércitos de A atacarem juntos, podem derrotar o exército de B.
Problema: Pode ser elaborado um algoritmo que permita que os dois generais dos exércitos de A concordem com um ataque simultâneo? O algoritmo pode incluir o envio e recebimento de mensagens.
Solução: O clássico Problema dos Dois Generais é insolúvel. Não há protocolo que possa garantir que os dois exércitos de A coordenem com sucesso seu ataque. No entanto, em sistemas práticos, as questões podem ser abordadas de forma relativamente confiável, como com o mecanismo de “aperto de mãos de três vias” no protocolo TCP.

Problema dos generais bizantinos

O Problema dos generais bizantinos foi proposto pela primeira vez por Leslie Lamport, vencedor do Prêmio Turing de 2013, em seu artigo de 1982 “O Problema dos generais bizantinos”. O problema descreve como alcançar consistência em sistemas distribuídos na presença de comportamento malicioso, como adulteração de mensagens.
Várias armadas do Império Bizantino cercam uma cidade inimiga, cada uma liderada por um general. As armadas bizantinas só podiam se comunicar por mensageiros. Após observar as forças inimigas, os generais bizantinos devem chegar à mesma conclusão: somente se mais da metade das armadas bizantinas atacarem juntas é que podem capturar a cidade e alcançar a vitória.

Solução: Se o número de generais (nós) em um sistema bizantino for Z e o número de generais não confiáveis (traidores) for X, então somente quando Z ≥ 3X + 1 um protocolo de Tolerância a Falhas Bizantinas (BFT) pode garantir a consistência do sistema.
Em sistemas práticos, falhas que fazem com que os nós fiquem inativos são classificadas como "Falhas de colapso," enquanto nós que forjam ou adulteram mensagens são classificados como "Falhas bizantinas."

Classificação do Algoritmo de Consenso

Os sistemas de blockchain são um tipo de sistema distribuído, especialmente as cadeias públicas como Bitcoin e Ethereum, que consistem em inúmeros nós de rede altamente descentralizados e mutuamente desconfiados. O mecanismo de consenso do blockchain garante que o sistema de blockchain alcance consistentemente a consistência dos dados sem bifurcações.
Com base no tipo de tolerância a falhas, os algoritmos de consenso podem ser classificados em algoritmos de Tolerância a Falhas Não Bizantinas (CFT) e algoritmos de Tolerância a Falhas Bizantinas (BFT).

Algoritmos de Tolerância a Falhas não Bizantinas

Em sistemas distribuídos, algoritmos de Tolerância a Falhas não-bizantinas garantem a confiabilidade de todo o sistema distribuído quando os nós enfrentam falhas do sistema ou interrupções não planejadas (falhas não-bizantinas). No entanto, quando nós maliciosos falsificam ou alteram dados, os algoritmos de Tolerância a Falhas não-bizantinas não podem garantir a confiabilidade do sistema. Esses algoritmos são principalmente usados em sistemas distribuídos empresariais fechados e controlados. Os algoritmos de Tolerância a Falhas não-bizantinas mais representativos incluem o algoritmo Paxos e o algoritmo Raft.

Algoritmos de Tolerância a Falhas Bizantinas

Algoritmos de Tolerância a Falhas Bizantinas permitem que um sistema distribuído garanta confiabilidade, mesmo se os nós sofrerem qualquer tipo de falha, desde que o número de nós defeituosos não exceda uma certa proporção. Simplificando, contanto que o número de nós defeituosos (devido a falhas não bizantinas ou bizantinas) seja inferior a uma certa proporção do total de nós, os algoritmos de Tolerância a Falhas Bizantinas podem garantir a confiabilidade do sistema. Devido à presença de muitos nós de rede não confiáveis em sistemas blockchain como Bitcoin e Ethereum, os algoritmos de Tolerância a Falhas Bizantinas são usados principalmente em mecanismos de consenso blockchain. Os algoritmos de Tolerância a Falhas Bizantinas mais representativos incluem PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work) e PoS (Proof of Stake).