Tolerância a Falhas Bizantinas

A tolerância a falhas bizantinas é o estudo de como alcançar um acordo quando alguns processos podem falhar arbitrariamente, inclusive enviando mensagens conflitantes ou maliciosas.

Definition

Uma falha bizantina é um desvio arbitrário da especificação de um componente, incluindo comportamento malicioso; a tolerância a falhas bizantinas é a capacidade de um protocolo distribuído satisfazer suas condições de correção apesar de um número limitado de participantes defeituosos.

Scope

Este tópico abrange o problema dos generais bizantinos e os limites de resiliência rigorosos que ele estabelece (pelo menos 3f+1 processos, ou mensagens assinadas, para tolerar f falhas arbitrárias), os algoritmos de acordo síncronos de mensagens orais e assinadas, e protocolos assíncronos práticos tolerantes a falhas bizantinas, como o PBFT e seus descendentes. Ele fundamenta os modelos de confiança de blockchains permissionadas e serviços replicados de alta integridade.

Core questions

• Quantos processos corretos são necessários para tolerar um dado número de falhas arbitrárias?
• Como as assinaturas digitais alteram os limites de resiliência para o acordo bizantino?
• Como o acordo bizantino pode ser tornado eficiente o suficiente para sistemas assíncronos práticos?

Key theories

Limite dos generais bizantinos

Com mensagens não autenticadas (orais), o acordo bizantino é solucionável se e somente se mais de dois terços dos processos estiverem corretos (n > 3f); mensagens autenticadas com assinaturas infalsificáveis relaxam este requisito.

Replicação BFT prática

O PBFT mostra que o acordo bizantino pode ser executado em um sistema parcialmente síncrono com replicação de máquina de estados usando um primário e um protocolo de três fases, alcançando desempenho prático enquanto tolera até um terço de réplicas defeituosas.

Algoritmos de acordo síncronos

No modelo síncrono, algoritmos recursivos de mensagens orais e assinadas alcançam acordo em f+1 rodadas, ilustrando o custo de complexidade de rodadas para tolerar falhas arbitrárias.

Clinical relevance

A tolerância a falhas bizantinas é a base de sistemas que devem resistir não apenas a falhas, mas também a comprometimento ou comportamento malicioso, incluindo blockchains permissionadas, serviços replicados de alta garantia e controle de aviônicos e aeroespacial, onde falhas arbitrárias de componentes não podem ser descartadas.

History

Pease, Shostak e Lamport estabeleceram os limites de acordo em 1980 e os dramatizaram como o problema dos generais bizantinos em 1982; por quase duas décadas, o acordo bizantino foi considerado muito custoso para a prática até que o PBFT de Castro e Liskov em 1999 demonstrou replicação bizantina assíncrona eficiente, revivendo o campo e, posteriormente, informando o consenso de blockchain.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Por que tolerar f falhas bizantinas requer 3f+1 processos?

Os processos corretos devem chegar a uma decisão majoritária mesmo quando f processos defeituosos mentem e outros f podem ser lentos ou inalcançáveis; somente com mais de três vezes o número de processos defeituosos a maioria correta pode sempre superar a combinação de participantes defeituosos e atrasados.