Algoritmo práctico de tolerancia a fallos bizantinos (PBFT)
El Imperio Bizantino, el Imperio Romano de Oriente, tenía una enorme riqueza y hacía tiempo que se interesaba por sus vecinos. Por ello, envió 10 ejércitos para rodear a este enemigo. Aunque este enemigo no es tan poderoso como el Imperio Bizantino, es suficiente para resistir los ataques simultáneos de cinco ejércitos bizantinos convencionales. Por algunas razones, estos 10 ejércitos no pueden reunirse para abrirse paso en un solo punto, sino que deben atacar simultáneamente en estados de cerco separados. Ninguno de sus ejércitos tiene posibilidades de ganar si atacan solos, a menos que al menos 6 ejércitos ataquen al mismo tiempo, pueden capturar el país enemigo. Están dispersos por el país enemigo y dependen de las tropas de comunicaciones para comunicarse entre sí para negociar las intenciones y el tiempo de ataque. El problema que preocupa a estos generales es que no están seguros de si hay traidores entre ellos. Los traidores pueden cambiar la intención o el momento del ataque sin autorización. En este estado, ¿podrían los generales bizantinos encontrar un protocolo distribuido que les permitiera negociar de forma remota y ganar la batalla? Este es el famoso problema de los generales bizantinos en los sistemas distribuidos, lo que significa que los mensajes no sólo pueden perderse, retrasarse, reproducirse, sino también falsificarse.
El algoritmo PBFT (Practical Byzantine Fault Tolerance) fue propuesto por Miguel Castro y Barbara Liskov en 1999. Resolvió el problema de ineficiencia del algoritmo bizantino tolerante a fallos original y redujo la complejidad del algoritmo de exponencial a polinómico. ., lo que hace que el algoritmo bizantino tolerante a fallas sea factible en aplicaciones prácticas de sistemas.
PBFT es un algoritmo de replicación de copia de máquina de estado, que generalmente incluye tres protocolos: protocolo de coherencia (acuerdo), protocolo de punto de control (punto de control) y protocolo de cambio de vista (ver cambio). El algoritmo debe satisfacer las dos propiedades siguientes:
Seguridad: seguridad significa que no sucede nada malo. Vividez: vivacidad significa que algo bueno eventualmente sucede.
En un sistema bizantino, tolerar. En caso de errores de nodos bizantinos, el número de réplicas debe ser al menos 3f+1, lo cual es un requisito previo para la seguridad. Debido a retrasos en la red o tiempo de inactividad, hay f nodos en el sistema que no responden (los nodos f incluyen nodos bizantinos y nodos no bizantinos y, en el peor de los casos, los nodos f son todos nodos no bizantinos. Puede haber f). entre las 2f+1 respuestas restantes, obteniendo así n-2f>f, es decir, el número de nodos no bizantinos en la respuesta es mayor que el número de nodos bizantinos (f+1>f).
Si el algoritmo no depende de la sincronización para proporcionar seguridad, debe confiar en la sincronización para proporcionar actividad; de lo contrario, viola el teorema FLP (en un escenario de comunicación asincrónica, incluso si solo falla un proceso, ningún algoritmo puede garantizar que los procesos no fallidos puedan llegar a un consenso sexual). La actividad del sistema se puede garantizar cuando los nodos bizantinos no exceden f y el retraso (t) está limitado. El retraso (t) representa el intervalo de tiempo desde el envío del mensaje hasta la recepción.
En una vista, se seleccionará una principal de las réplicas y las réplicas restantes se denominarán copias de seguridad. Si el comportamiento del nodo maestro es anormal, realice un cambio de vista para cambiar el nodo maestro. ?
El juego comienza enviando una solicitud del cliente al primario. Operación de la máquina de estados, marca de tiempo. El juego finaliza después de recibir al menos f+1 réplicas de respuestas del cliente. Ver número, marca de tiempo, identidad del cliente, número de réplica, resultado de la solicitud.
¿Por qué f+1? Porque hay f nodos bizantinos entre los 2f+1 comprometidos que parecen estar de acuerdo con la solicitud, pero en realidad no responderán a la solicitud en absoluto
3.1 El gran espectáculo------tres- acuerdo de fase
Preparación previa:
Primario asigna un número de secuencia n a la solicitud del cliente y descubre mensajes preparados previamente para todas las copias de seguridad. Ver número, resumen del mensaje.
Preparar:
Las copias de seguridad aceptan mensajes preparados si se cumplen las siguientes condiciones: 1. La solicitud del cliente y el mensaje preparado tienen firmas correctas. 2. El número de vista actual es v. 3. Las copias de seguridad nunca recibieron una solicitud de preparación previa con el número de secuencia n, pero un resumen diferente en la vista actual v. 4.h Si se cumplen las condiciones anteriores, las copias de seguridad reciben el mensaje de preparación previa, ingresan a la fase de preparación y transmiten el mensaje de preparación a otros nodos. y escribe los mensajes de preparación previa y preparación. Ingrese el registro. confirmación: Si las copias de seguridad reciben 2f, incluido su propio mensaje de preparación coherente con el mensaje preparado previamente, el mensaje de solicitud y el mensaje preparado previamente tienen la misma vista v y número de secuencia. n, y después de que el mensaje relevante se haya escrito en el registro, ingresa a la fase de confirmación y transmite un mensaje de confirmación a otros nodos. Si cada nodo recibe 2f+1 mensajes de confirmación idénticos, envía un mensaje de respuesta al cliente. 3.2 Recolección de basura ? PBFT es un algoritmo de replicación de réplicas de máquinas de estado. Las réplicas registrarán los mensajes ejecutados en registros locales. Para ahorrar memoria, se necesita un mecanismo para limpiar el registro. . ¿Cuándo se limpiará? No es aconsejable ejecutarlo después de cada operación porque requiere más recursos. Se puede limpiar con regularidad, por ejemplo cada 100 veces. Llamamos punto de control al estado ejecutado después de la solicitud; el punto de control con prueba se denomina certificado estable. Cuando el nodo recibe mensajes de punto de control 2f+1, se puede demostrar que el punto de control estable es correcto. Se pueden eliminar los mensajes de registro antes del punto de control estable. Al limpiar el punto de control, la réplica i transmite un protocolo de punto de control a otras réplicas, que es el último número de secuencia de solicitud ejecutado correctamente y su resumen de estado actual. Si cada réplica recibe mensajes de punto de control 2f+1 con el mismo número de secuencia y resumen, entonces cada réplica puede borrar la información de registro con un número de secuencia menor o igual a n. El protocolo de punto de control también se utiliza para actualizar líneas horizontales. La línea horizontal baja es igual al número de secuencia del último punto de control estable y la línea horizontal alta es el tamaño del registro. 3.3 Ver cambios Cuando el nodo maestro cuelga, o durante la fase de confirmación, algunos nodos reciben confirmaciones 2f+1 y otros no reciben confirmaciones 2f+1, lo que resulta en inconsistencia estado. Estas condiciones requieren cambios en la vista para proporcionar vitalidad y seguridad al sistema. Cuando se agota el tiempo de espera de la solicitud, el nodo de respaldo ingresa a la vista v+1 y transmite el mensaje de cambio de vista. El número de secuencia del punto de control estable es una prueba de punto de control estable y es un conjunto que contiene un conjunto de mensajes relacionados con la solicitud (el número de secuencia solicitado es mayor que). Contiene 2f+1 mensajes de preparación idénticos. ?Cuando el nodo maestro de la vista v+1 recibe 2f mensajes de cambio de vista idénticos y transmite nuevos mensajes de vista a otras réplicas, son 2f+1 mensajes de cambio de vista. Las reglas de cálculo son las siguientes: 1. Determine el número de serie y. donde es igual al número de secuencia del punto de control estable en y es igual al número de secuencia máximo del mensaje de preparación en . ? 2. El nodo maestro asigna un mensaje de preparación previa a cada número de secuencia n entre y. Si contiene la combinación correspondiente a n, el mensaje preparado correspondiente es (es decir, la solicitud correspondiente al número de secuencia n tiene 2f+1 mensajes de preparación, y esta solicitud aún se envía en la nueva vista). Si no contiene la combinación correspondiente de n, el mensaje nulo se envía como , es decir, no se realiza ningún procesamiento. Después de recibir el mensaje de nueva vista, la réplica transmite un mensaje de preparación, ingresa v+1 y se completa el cambio de vista.