Teorema de imposibilidad FLP y su demostración
Por ejemplo, algunos procesos que se ejecutan en el servidor no son confiables. Por ejemplo, el hardware del servidor puede fallar, el sistema operativo puede fallar y los procesos pueden fallar.
Otro ejemplo es que la comunicación de red entre procesos no es confiable. Los mensajes pueden perderse, retrasarse y las redes pueden fragmentarse.
Además de los fallos de hardware o de red mencionados anteriormente, incluso pueden producirse algunos problemas arbitrarios o fraudulentos en el proceso del sistema, que son los llamados fallos bizantinos. Por ejemplo, varios sensores instalados en instrumentos espaciales pueden exhibir un comportamiento arbitrario en entornos extremos, como la transmisión de parámetros erróneos. En una red blockchain como Bitcoin, los piratas informáticos controlarán algunos procesos y deliberadamente falsificarán y manipularán varias transacciones para lograr motivos ocultos. Por lo tanto, para un sistema distribuido, la falla es simplemente una ocurrencia común, es una idea descabellada suponer que todos los procesos en un sistema de red distribuido pueden operar normalmente bajo cualquier circunstancia;
Entonces la pregunta es, en una red asincrónica distribuida, ¿es posible que todos los procesos confiables alcancen * * * conocimiento a través de la comunicación? La respuesta es mágica, eso es imposible.
Te preguntarás, ¿cómo es posible que los sistemas distribuidos actuales no puedan alcanzar** el conocimiento? La respuesta es que la premisa aquí es una red asíncrona. 265438+1920s Ya sabemos que existen muchos algoritmos clásicos que pueden lograr * * * conocimiento, pero básicamente se basan en el modelo de red síncrona. Sin embargo, en el modelo de red asíncrona, sólo existen restricciones y reglas mínimas con respecto al cálculo del proceso y la transmisión de mensajes. El algoritmo está basado en eventos, es decir, un proceso puede transmitir y enviar información a todos los demás procesos. En una red completamente asíncrona, no podemos hacer referencia ni analizar la velocidad de procesamiento de procesos y transmisión de mensajes. Los mensajes en sí pueden retrasarse arbitrariamente y los mensajes recibidos pueden estar arbitrariamente desordenados. Suponemos que el proceso no puede hacer referencia al reloj de sincronización, lo que significa que el algoritmo basado en el mecanismo de tiempo de espera no se puede utilizar durante el proceso de diseño del algoritmo. No podemos detectar si un proceso es defectuoso porque no podemos decir y distinguir si la ejecución del proceso es demasiado lenta, la velocidad de entrega del mensaje es demasiado lenta o el proceso se ha bloqueado.
En esta famosa "Posibilidad de consenso distribuido con un proceso erróneo", se realiza una rigurosa demostración teórica. Este artículo llega a una conclusión concisa, elegante y sorprendente: en un sistema modelo mínimamente asíncrono suponiendo que la red es confiable y los nodos informáticos fallan sólo debido a fallas, todavía no existe un algoritmo determinista que pueda resolver el problema de consistencia. Después de la publicación de este artículo, inmediatamente recibió amplia atención e investigación. La prueba propuesta en este artículo lleva el nombre de los tres autores del artículo, Fisher, Lynch y Patterson, y se llama teorema FLP. Los tres son académicos autorizados en el campo de la informática distribuida. Este artículo sentó una de las bases teóricas de la computación distribuida, pero es tan oscuro que la mayoría de los libros de texto de teoría de la computación se saltan esta prueba, e incluso el libro de texto clásico de computación distribuida "Notas de computación distribuida" simplifica y se omiten algunos pasos de prueba en el texto. Sin embargo, después de consultar algunas publicaciones de blogs de la comunidad china, todavía no está muy claro, por lo que dedicaré un tiempo a explicar el proceso de prueba principal con algunas expresiones inexactas, con la esperanza de ayudar a todos a comprender mejor. Si tiene alguna pregunta o comentario, no dude en ponerse en contacto conmigo :)
Primero, definamos algunos conceptos comunes en el modelo de red asincrónica distribuida:
Proceso: uno en el sistema unidad de trabajo. (Debido a que este artículo se publicó relativamente temprano, en algunos libros de texto se utiliza el nodo Node para expresar este concepto).
Paso de mensajes: un sistema distribuido que consta de un conjunto de procesos, cada uno de los cuales puede realizar operaciones locales y enviar mensajes a otros procesos en la red.
Pérdida de mensajes: En el modo de mensajería con pérdida de mensajes, no hay garantía de que algún mensaje llegue de forma segura al receptor del mensaje.
* * *Consenso: para lograr * * * consenso, se deben cumplir los siguientes puntos al mismo tiempo:
Consenso: todos los procesos no defectuosos coinciden en el mismo valor .
Terminación: Todos los procesos no defectuosos eventualmente acordarán un valor.
Validez: El valor final acordado debe estar dentro del rango de valores válidos. Por ejemplo, aquí simplificamos el modelo y reducimos el rango de valores al conjunto {0, 1}, entonces el valor no puede ser 2. De manera similar, si todos los valores de entrada son 0, el valor del resultado final solo puede ser 0.
Este artículo relaja aún más las condiciones de prueba. Toleramos que solo un proceso falle y, una vez que falle, no procesaremos ningún mensaje. Excluimos las redes bizantinas y asumimos que todos los participantes en la red no son maliciosos. Asumimos que el sistema de mensajería es confiable, que todos los mensajes solo se enviarán una vez y que la transmisión es precisa. Este entorno de red es sin duda más confiable e ideal que un entorno de red asíncrono real. Además, como se mencionó anteriormente, reducimos el valor de * * conocimiento al conjunto de {0, 1} para simplificar aún más todo el modelo de análisis. Si incluso el modelo relajado anterior no puede encontrar un algoritmo efectivo para redes asíncronas, es concebible que en una red asíncrona distribuida real, sea aún menos probable encontrar un algoritmo de reconocimiento * * * efectivo;
El protocolo * * * en este artículo es el siguiente:
En un sistema asincrónico, hay N procesos (N≥2), y cada proceso P tiene un bit registro de entrada xp, un registro de salida yp y suficiente almacenamiento interno. El valor de salida puede ser 0 o 1, o puede ser incierto (por ejemplo, en la etapa inicial, el resultado es incierto, por lo que el valor es incierto). Si el registro de salida yp ya tiene un resultado (es decir, 0 o 1), se denomina estado de decisión. Cada salida de yp, una vez que se genera el resultado, ya no puede ser manipulada. Los estados iniciales y los procesos de transformación de todos los procesos constituyen el sistema completo * * * protocolo de conocimiento p.
Los diferentes procesos se comunican entre sí mediante el envío de mensajes. Definimos un mensaje como (p, m). p representa el proceso objetivo y m representa el contenido del mensaje específico. Cada proceso tiene un búfer de mensajes, que admite las dos operaciones siguientes:
Enviar(p, m) envía un mensaje y lo agrega al búfer.
Receive(p) recibe el mensaje y lo elimina del buffer. Obtenga y devuelva el mensaje m y elimine el correspondiente (p, m) de la cola, o no reciba el mensaje y devuelva nulo. Entonces, mientras el búfer no esté vacío, significa que algún mensaje aún no se ha entregado y se agotó el tiempo de espera.
Como se mencionó anteriormente, los mensajes aquí solo se retrasarán, no se perderán, y todos los mensajes eventualmente se recibirán. Pero nuevamente, incluso si hay (p, m) en el búfer, el proceso aún puede devolver un valor nulo, debido al no determinismo de las redes asincrónicas.
Configuración: La configuración del sistema incluye el estado interno de cada proceso y el contenido del buffer de mensajes. La configuración de inicialización incluye el estado inicial de todos los procesos y un conjunto de buffers de mensajes vacíos.
Pasar de una configuración a otra se llama paso. Supongamos que la configuración C está definida y un paso consta de dos fases:
Recibir (p) en C y obtener el mensaje m.
p recibe el mensaje M, ingresa a un nuevo estado interno y luego envía el mensaje a otros procesos.
El tamaño del paso está determinado por (p, m), y definimos (p, m) como un evento. Como el evento (p, nulo) siempre existe, p siempre puede realizar un paso.
Programación de eventos: A partir de una secuencia finita o infinita de eventos σ aplicada en c, una secuencia de pasos relacionados se denomina ejecución. Si la secuencia de eventos σ es limitada, usamos σ (C) para representar el resultado de la configuración, lo que significa que el resultado de la configuración es accesible desde la configuración C. A continuación asumimos que todas las configuraciones son accesibles.
One-leafness: Una configuración es one-leafness si el valor de decisión se puede determinar independientemente de eventos posteriores.
Binaria: Si el valor de decisión solo puede ser 0 o 1, entonces la configuración es binaria. (El valor de decisión depende del orden en que se reciben los mensajes o se producen los eventos de bloqueo, es decir, aún no se ha decidido qué valor generar en ese momento).
Si los valores de entrada de todos los procesos son 0, entonces, de acuerdo con la definición anterior, puede estar seguro de que la configuración tiene precio 0.
Si un proceso P ejecuta un número limitado de pasos, significa que cuando se ejecuta uno de los pasos, el proceso no se ejecutará, lo que se denomina falla, de lo contrario, es normal; Como se mencionó anteriormente, este modelo permite que un proceso falle y todos los procesos en buen estado eventualmente recibirán todos los mensajes.
¿Qué pasa si un proceso p tiene un valor de decisión? v, se dice que la configuración c tiene un valor decisivo v. Un protocolo de conocimiento * * * parcialmente correcto satisface las dos condiciones siguientes:
Ninguna configuración accesible tiene múltiples valores de decisión;
Para una configuración alcanzable, algunas configuraciones alcanzables tienen un valor decisivo V, donde v∈{0, 1}.
De las condiciones anteriores se puede ver que la condición 1 satisface la coherencia; la condición 2 satisface la validez.
Si una ejecución tiene un proceso para alcanzar un valor de decisión, entonces esta ejecución es una ejecución de decisión.
El * * * protocolo de conocimiento P completamente correcto satisface las siguientes condiciones:
Este * * * protocolo de conocimiento P es parcialmente correcto;
Cada ejecución es decisiva de.
Un acuerdo de conocimiento * * * completamente correcto es más rescindible si se basan en algunos acuerdos de conocimiento * * * correctos.
Después de presentar los conceptos principales anteriores, comencemos la demostración, comenzando con tres lemas:
El lema 1 es muy intuitivo y fácil de entender. Algo similar a los tipos de cambio: en la configuración C, hay dos conjuntos de secuencias de eventos no relacionados σ1 y σ2, por lo que el orden de ejecución de σ1 y σ2 no afectará el resultado final de la configuración final C3. Debido a que se ha explicado en la definición que σ1 y σ2 no están relacionados entre sí, ya sea que σ1 o σ2 se ejecuten primero, el efecto es el mismo.
Lema 2: El protocolo P tiene una configuración inicial bivalente.
Demostración: Aquí utilizamos la reducción al absurdo para demostrar. Según la definición anterior del modelo de protocolo, sabemos que P debe tener un precio de 0 y un precio de 1 al mismo tiempo, lo que significa que todas las configuraciones iniciales tienen precio 0 o precio 1. A continuación, definamos el concepto de adyacencia de configuración. Si sólo el valor inicial xp de un proceso P difiere entre dos configuraciones iniciales, decimos que las dos configuraciones son adyacentes. Obviamente, se pueden alcanzar dos configuraciones adyacentes, por lo que podemos enumerar todas las configuraciones iniciales posibles y, finalmente, podemos conectar todas las configuraciones iniciales posibles a través de relaciones adyacentes. Entonces, debe haber C0 y C1 adyacentes, de modo que C0 sea el precio 0, C1 sea el precio 1 y P sean los diferentes procesos de C0 y C1.
Ahora asumimos que hay una decisión de ejecutar, donde P es el proceso fallido, luego, por definición, después de excluir P, los demás procesos son exactamente iguales.
Entonces, el resultado de ejecutar esta decisión en C0 es el mismo que el resultado en C1. Si el resultado es precio 0, significa que C1 debe ser bivalente; si es precio 1, significa que C0 es bivalente; Esto es contrario a nuestra hipótesis anterior. Por tanto, la configuración inicial del protocolo P es bivalente.
El símbolo del Lema 3 en el texto original parece un poco confuso. Reemplacemos los símbolos relevantes aquí.
Lema 3: C es una configuración bivalente en el protocolo P, y el evento e(p, m) puede afectar a C. Llamamos accesibles a todos los conjuntos de configuraciones accesibles desde C sin aplicar E como A, de modo que B= e(A)={e(E)| E∈A y E se pueden aplicar a E}; entonces, B debe contener una configuración bivalente.
Prueba: debido a que E se puede aplicar a C, por definición podemos encontrar que A en realidad retrasa la recepción del evento E. Cualquier configuración en el conjunto puede aplicar E, y el conjunto de configuraciones derivadas de C no aplica E. es A, y aplicando E desde cualquier configuración en A, el conjunto de configuración resultante es b.
Todavía usamos prueba por contradicción. Supongamos que el conjunto B no contiene configuraciones bivalentes, entonces cada configuración en B es univalente, es decir, tiene 0 valencia o 1 valencia.
Definimos e i, alcanzable desde C, donde i=0, 1 (porque C es bivalente, entonces Ei existe).
Si Ei∈A, entonces por definición, después de aplicar e, existen fi = e (ei) y fi ∈ b.
Si se ha aplicado e para llegar a Ei, entonces existe Fi, Ei es alcanzable desde Fi y fi ∈ b.
En cualquier caso, fi pertenece a una sola hoja porque Fi∈b debe haber accesibilidad entre Ei y Fi. En Fi, i=0,1. Como suponemos que B no es bivalente, en resumen, podemos demostrar que B siempre contiene 0 y 1 valencias.
Si hay un paso entre dos configuraciones, decimos que las dos configuraciones son adyacentes. Definimos dos configuraciones adyacentes C0 y C1, donde C0 y C1 ∈ a. Según la definición, podemos obtener D0=e(C0) y D1=e(C1). Suponiendo que el evento E' se impone entre dos configuraciones adyacentes, podemos obtener C1=e'(C0), e'=(p', m'). Como se muestra en la siguiente figura:
Lo siguiente se puede dividir en dos casos para discusión:
Caso 1: p' ≠ p, es decir, los mensajes E y E' son diferentes .
Entonces, según el Lema 1, podemos construir el siguiente gráfico. D0 ha pasado del precio 0 a D1 con precio 1. Esto es contradictorio porque cualquier configuración de precio unitario determinada no se puede cambiar a otros valores, solo se puede cambiar del precio 0 al precio 0.
Caso 2: p' = p, es decir, los mensajes e y e' son iguales.
Podemos seguir construyendo "líneas auxiliares" para demostrarlo.
Supongamos que hay una ejecución de decisión con un número finito de pasos a partir de C0. Esta ejecución de decisión no contiene ningún paso relacionado con el proceso P, es decir, no tiene nada que ver con P. ¿Cuál es el proceso? ¿Secuencia de eventos en esta ejecución de decisión? Aquí construimos una configuración X tal que X=? (C0).(x aparece en rojo)
Como se muestra en la figura anterior, según el Lema 1,? no interseca e y e'. Por lo tanto, independientemente de e->? ,¿aún? ->e, el resultado es el mismo. Asimismo, e'->e->? ¿Cuál es el resultado? ->e '->e tiene el mismo resultado. ¿así que lo que? ¿Se puede aplicar a Di tal que Ei=? (Di), i=0, 1.e(X)=E0, e(e'(X))=E1
Entonces x es bivalente. Pero C0 también es precio unitario, ¿qué más? Este es un movimiento decisivo, que es contradictorio con el hecho de que x sea bivalente.
Entonces, si la hipótesis no se cumple, B debe contener una configuración bivalente.
Después de demostrar los tres lemas anteriores, demostremos el teorema de imposibilidad de FLP.
Según el Lema 2, P siempre tiene la configuración de inicialización de un cuerpo bivalente. En cualquier configuración que decida pasar de divalente a monovalente, debe haber un paso que cambie de divalente a monovalente. Este paso determina el valor de la decisión final. Podemos definir una configuración clave: si la configuración C es bivalente, pero todos los nodos secundarios directos de la configuración C son monovalentes, llamamos a C una configuración clave.
Sin embargo, según el Lema 3, la falla de un solo proceso (retrasando la recepción del evento E) conducirá a una configuración de nodo hoja bivalente. Siempre existe la posibilidad de que este paso crítico se retrase, lo que provocará que el sistema no pueda completar este paso tan crítico.
Por lo tanto, podemos sacar la conclusión final de que cuando f & gt0 (f es el proceso de falla), no existe un algoritmo determinista y * * * el reconocimiento siempre se puede lograr bajo el modelo asíncrono (P es siempre correcto).
Al mismo tiempo, también podemos extraer otro teorema: suponiendo que todos los procesos no defectuosos no han fallado, la mayoría de los procesos sobreviven desde el principio, existe un protocolo de conocimiento * * * parcialmente correcto y todos procesos no defectuosos Los procesos siempre logran * * conocimiento. Es decir, bajo el modelo de comunicación asincrónica, en el mejor de los casos solo podemos satisfacer la coherencia y la validez, pero no podemos garantizar la terminabilidad. La demostración de este teorema también se da en el texto. La prueba se omite aquí. Los estudiantes interesados pueden abrir el artículo y seguir el enlace al final del artículo para leerlo.
Resumen:
Hemos demostrado que en un modelo de comunicación totalmente asíncrono, mientras haya un nodo defectuoso, no existe un algoritmo de conocimiento determinista. Por supuesto, este resultado es más teórico y la probabilidad de que la terminación no pueda lograrse en la práctica es muy baja. Esta conclusión solo puede mostrar que no existe una solución perfecta en la ingeniería real; después de todo, es necesario comprender este teorema y hacer concesiones efectivas al diseñar protocolos, un protocolo que pretende implementar un algoritmo de identificación completamente correcto de forma asincrónica; La red es basura.
"Posibilidad de consenso distribuido bajo un proceso de falla" Dirección del artículo:/papers-we-love/papers-we-love/blob/master/distributed_systems/Possibility-of-consensus-with -one -proceso-fallo .pdf