¿Por qué se determina un umbral para la tolerancia a fallas bizantinas de una red "asincrónica"?(donde no puede tolerar ni siquiera un nodo defectuoso)

Question

En la siguiente respuesta (ENLACE: https://bitcoin.stackexchange.com/a/58908/41513), se ha demostrado que para Acuerdo bizantino asincrónico:

"No podemos tolerar que 1/3 o más de los nodos sean deshonestos o perdemos ya sea seguridad o vida".

Para esta prueba se han considerado las siguientes condiciones/requisitos:

1. Nuestro sistema es asincrónico.
2. Algunos participantes pueden ser maliciosos.
3. Queremos seguridad.
4. Queremos vivacidad.

Una pregunta fundamental es que:

Teniendo en cuenta el conocido artículo titulado: "Imposibilidad de lograr un consenso distribuido con un proceso defectuoso" (ENLACE: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

mostrando que:

Ningún protocolo de consenso completamente asincrónico puede tolerar ni siquiera una única muerte de proceso no anunciada.,

¿Podemos seguir suponiendo que la red es asíncrona?Como en ese caso, la red no puede tolerar ni siquiera un nodo defectuoso.

Answer 1

La respuesta tiene que ver con el seguimiento de los supuestos precisos que se hacen en estos diferentes resultados.En resumen, si bien ambos resultados suponen asincronía, la "imposibilidad de un consenso distribuido con un proceso defectuoso" requiere una forma más fuerte de vivacidad y determinismo, y eso hace que el consenso sea imposible.

1.Imposibilidad de consenso distribuido con un proceso defectuoso

Este resultado fundamental (de Michael Fischer, Nancy Lynch y Michael Paterson) trata sobre el consenso distribuido donde el sistema no sólo es asincrónico, sino que también satisface:

• Determinismo. El algoritmo de consenso no utiliza ninguna aleatoriedad.

• Vivencia bajo retrasos en los mensajes. No sólo los mensajes pueden retrasarse arbitrariamente, sino que también debemos garantizar su vivacidad incluso en presencia de retrasos continuos.

Veamos por qué estas propiedades son demasiado fuertes y hacen imposible el consenso distribuido.

Considere un ejemplo:Alice, Bob y Charlie son amigos y quieren decidir dónde quedar para cenar.Es posible que uno de ellos inesperadamente se ausenta sin permiso (o decida que ya no está interesado en ser amigos) y deje de responder los mensajes.En este caso, los otros dos aún pueden decidir el lugar de reunión.Ahora ¿qué deberían hacer?

El enfoque obvio sería que:

Alice simplemente decide adónde ir y se lo cuenta a Bob y Charlie.

Pero esto no funciona porque Alice puede ser la que se ausenta sin permiso.Entonces, para solucionar este problema, el siguiente enfoque más obvio podría ser:

Tanto Alice como Bob les dicen a todos los demás adónde ir.Si todos tienen noticias de Alice, irán a donde Alice diga;de lo contrario, irán a donde dice Bob.

Pero esto tiene un nuevo problema.Supongamos que eres Charlie.Si tienes noticias de Alice, sabes adónde ir.Si no tiene noticias de ninguno de ellos, espere a recibir noticias.El problema es cuando has tenido noticias de Bob, pero no de Alice.Debido a que hay retrasos arbitrarios en los mensajes, no puedes comprometerte a ir a donde dijo Bob:Es posible que Alice haya dicho adónde ir, ¡y tú aún no lo has recibido!Así que estás completamente estancado, y si sucede que Alice se ha ausentado sin permiso, seguirás esperando para siempre.

El problema aquí es que no tenemos forma de cancelar la transacción;no hay forma de decir: "Está bien, esto no está funcionando, ha pasado demasiado tiempo y no he recibido un retraso, intentémoslo de nuevo". Los algoritmos de consenso del mundo real (el más conocido es Paxos) tienen la posibilidad de que las rondas fallen debido a retrasos en la red, y en este caso simplemente lo intentan de nuevo, con la esperanza de que los retrasos de la red sean más cortos.Además, es posible solucionar el problema utilizando protocolos aleatorios que generalmente funcionan y solo continúan para siempre con una probabilidad pequeña (o incluso nula).

2.Acuerdo Bizantino Asincrónico donde menos de $1/3$ de los nodos fallan

La publicación de bitcoinSE que usted vincula pasa por alto el tema de la vida y solo dice que es "la capacidad de continuar avanzando".De hecho, el resultado anterior muestra que la forma más estricta de esto es imposible, por lo que tenemos que relajar nuestros requisitos/suposiciones.

Consideremos dos ejemplos.En "Practical Byzantine Fault Tolerance" de Miguel Castro y Barbara Liskov, logran una vida práctica con menos de un tercio de los nodos defectuosos por suponiendo que los retrasos en los mensajes no continúan creciendo indefinidamente.Como afirman los autores:

Garantizamos la vivacidad, es decir, los clientes eventualmente recibir respuestas a sus solicitudes, siempre y cuando se $\frac{n-1}{3}$ Las réplicas son defectuosas y $retraso(t)$ No crecen más rápido que $t$ indefinidamente... Esta es una sincronía bastante débil suposición que es probable que sea cierta en cualquier sistema real siempre que las fallas de la red se reparen eventualmente, sin embargo, nos permite eludir el resultado de la imposibilidad en [9].

Aquí [9] está el resultado de imposibilidad discutido anteriormente.En términos sencillos para nuestro ejemplo, evitan el problema anterior con Charlie al requerir una forma débil de sincronía:Charlie no tiene que seguir esperando eternamente, ya que sabemos que los retrasos en los mensajes sólo pueden crecer temporalmente y no indefinidamente.(Por supuesto, el algoritmo real se vuelve mucho más complejo, pero esa es en parte la idea conceptual de por qué es posible la vida).

En el "Acuerdo bizantino rápido asincrónico con resiliencia óptima" de Ran Canetti y Tal Rabin, utilizan la aleatoriedad para obtener vida con menos de $n/3$ Fallos de nodos bizantinos.De su artículo:

En este contexto, describimos un $(\lceil\frac{n}{3} ceil- 1)$-Protocolo del Acuerdo Bizantino resistente.Con Probabilidad abrumadora de que todos los jugadores no defectuosos completen la ejecución del protocolo.Condicionado a la en el caso de que todos los jugadores no defectuosos hayan completado el ejecución del protocolo, lo hacen de manera constante Hora.

Aquí $(\lceil\frac{n}{3} ceil- 1)$-Resiliente sólo significa que menos de un tercio de los nodos son bizantinos.Tenga en cuenta las palabras clave con una probabilidad abrumadora. Por lo tanto, tienen un algoritmo probabilístico que tiene muchas "ejecuciones" posibles y, abrumadoramente, la mayoría de ellas funcionan.Tenga en cuenta que el resultado de imposibilidad anterior implica que siempre debe haber alguno carreras donde no se produce vida, es decirno hay consenso:

El resultado fundamental de imposibilidad de Fischer, Lynch y Paterson [FLP] para protocolos deterministas implica que cualquier protocolo (aleatorizado) que llegue a BA debe tener ejecuciones no terminantes.