Tolerancia a Fallos Bizantinos

La tolerancia a fallos bizantinos es el estudio de cómo alcanzar un acuerdo cuando algunos procesos pueden fallar arbitrariamente, incluso enviando mensajes conflictivos o maliciosos.

Definition

Un fallo bizantino es una desviación arbitraria de la especificación de un componente, incluyendo el comportamiento malicioso; la tolerancia a fallos bizantinos es la capacidad de un protocolo distribuido para satisfacer sus condiciones de corrección a pesar de un número limitado de participantes defectuosos.

Scope

Este tema abarca el problema de los generales bizantinos y los estrictos límites de resiliencia que establece (al menos 3f+1 procesos, o mensajes firmados, para tolerar f fallos arbitrarios), los algoritmos de acuerdo síncronos de mensajes orales y firmados, y los protocolos prácticos asíncronos tolerantes a fallos bizantinos como PBFT y sus descendientes. Sirve de base para los modelos de confianza de las cadenas de bloques permisionadas y los servicios replicados de alta integridad.

Core questions

• ¿Cuántos procesos correctos se necesitan para tolerar un número dado de fallos arbitrarios?
• ¿Cómo cambian las firmas digitales los límites de resiliencia para el acuerdo bizantino?
• ¿Cómo se puede hacer que el acuerdo bizantino sea lo suficientemente eficiente para sistemas asíncronos prácticos?

Key theories

Límite de los generales bizantinos

Con mensajes no autenticados (orales), el acuerdo bizantino es resoluble si y solo si más de dos tercios de los procesos son correctos (n > 3f); los mensajes autenticados con firmas infalsificables relajan este requisito.

Replicación BFT práctica

PBFT demuestra que el acuerdo bizantino puede ejecutarse en un sistema parcialmente síncrono con replicación de máquina de estados utilizando un primario y un protocolo de tres fases, logrando un rendimiento práctico mientras tolera hasta un tercio de réplicas defectuosas.

Algoritmos de acuerdo síncronos

En el modelo síncrono, los algoritmos recursivos de mensajes orales y mensajes firmados logran un acuerdo en f+1 rondas, ilustrando el costo de complejidad de rondas de tolerar fallos arbitrarios.

Clinical relevance

La tolerancia a fallos bizantinos es la base de los sistemas que deben soportar no solo fallos, sino también compromisos o comportamientos maliciosos, incluyendo cadenas de bloques permisionadas, servicios replicados de alta seguridad y control de aviónica y aeroespacial donde no se puede descartar un fallo arbitrario de los componentes.

History

Pease, Shostak y Lamport establecieron los límites de acuerdo en 1980 y los dramatizaron como el problema de los generales bizantinos en 1982; durante casi dos décadas, el acuerdo bizantino se consideró demasiado costoso para la práctica hasta que el PBFT de Castro y Liskov en 1999 demostró una replicación bizantina asíncrona eficiente, reviviendo el campo y, posteriormente, influyendo en el consenso de las cadenas de bloques.

Key figures

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

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

¿Por qué tolerar f fallos bizantinos requiere 3f+1 procesos?

Los procesos correctos deben alcanzar una decisión mayoritaria incluso cuando f procesos defectuosos mienten y otros f pueden ser lentos o inalcanzables; solo con más de tres veces el número de procesos defectuosos puede la mayoría correcta siempre superar en votos a la combinación de participantes defectuosos y rezagados.