El modelo de fallas de parada u omisión de DLS: El paso previo a BFT

Cuando se aborda el consenso BFT en Consenso BFT desde cero, se salta directamente al adversario bizantino: réplicas que mienten, duplican votos y se coordinan para romper el registro. Ese salto es correcto para HotStuff, pero oculta un escalón intermedio que aclara de dónde salen los números.

El artículo de Dwork, Lynch y Stockmeyer de 1988 no estudia un solo tipo de falla. Recorre varios modelos con el mismo método y, para cada uno, demuestra cuántos procesos defectuosos se pueden tolerar cuando la red es parcialmente síncrona. [1] Leer esa tabla en orden es la forma más corta de entender por qué un protocolo tolerante a caídas trabaja con mayorías simples y uno bizantino con supermayorías de dos tercios.

Cuatro modelos de falla, de menor a mayor poder adversarial

DLS considera procesos con fallas por parada (fail-stop), por omisión, bizantinas con autenticación y bizantinas sin autenticación. [1] Conviene leerlos como una escalera: cada peldaño le da al proceso defectuoso todo lo que tenía el anterior y algo más.

En una falla por parada, el proceso ejecuta correctamente hasta cierto paso y luego se detiene para siempre. En una falla por omisión, el proceso no se detiene, pero puede no enviar algunos de los mensajes que el protocolo le exige; lo que sí envía es correcto. Desde fuera, la omisión es más difícil de manejar que la parada porque el proceso reaparece: unos vecinos lo escuchan y otros no.

En una falla bizantina, el proceso puede comportarse de cualquier manera. La variante autenticada añade una única restricción: existe un esquema de firmas que el proceso defectuoso no puede falsificar, de modo que no puede inventar mensajes firmados por procesos correctos. [1] Sigue pudiendo mentir sobre sus propios valores, firmar dos mensajes contradictorios o callar.

La escalera importa porque un protocolo diseñado para un peldaño funciona en los de abajo, pero no en los de arriba. Un protocolo bizantino tolera caídas; un protocolo de caídas no tolera mentiras.

Sincronía parcial: el terreno donde se miden las cotas

Las cotas de DLS no tienen sentido sin el modelo de tiempo. En un sistema totalmente asíncrono, Fischer, Lynch y Paterson demostraron que ningún protocolo determinista garantiza consenso si un solo proceso puede fallar por parada. [2] La razón de fondo es que un proceso caído y uno muy lento son indistinguibles cuando no existe ninguna cota de tiempo.

DLS propone un punto intermedio. En una versión del modelo, existen cotas sobre el retraso de los mensajes y la velocidad relativa de los procesos, pero no se conocen de antemano. En otra, las cotas se conocen, pero solo se cumplen a partir de un instante desconocido, el tiempo de estabilización global o GST. [1] Los protocolos del artículo mantienen safety siempre y garantizan terminación una vez que el sistema se comporta de forma síncrona el tiempo suficiente.

Este es el modelo que heredan PBFT y HotStuff: safety no depende de la red y liveness sí. PBFT lo dice explícitamente: no confía en la sincronía para proveer safety, pero necesita cierta sincronía para asegurar liveness. [4]

Las cotas de DLS: 2f + 1 frente a 3f + 1

Bajo sincronía parcial, DLS muestra que el consenso que tolera $f$ fallas es posible si y solo si $n \ge 2f + 1$ para parada y omisión, y $n \ge 3f + 1$ para fallas bizantinas. [1] La cota bizantina es la misma con autenticación y sin ella: las firmas no reducen el número de procesos necesarios en este modelo. [1]

Ese resultado contrasta con el modelo síncrono. Con mensajes firmados y sincronía, el algoritmo de Lamport, Shostak y Pease resuelve el problema de los generales bizantinos para cualquier número de generales; sin firmas, necesita más de $3m$ generales para tolerar $m$ traidores. [3] En otras palabras, la autenticación compra resiliencia cuando hay cotas de tiempo conocidas, pero no cuando la red puede retrasar mensajes de forma arbitraria hasta GST.

Por qué con caídas basta una mayoría

Una forma intuitiva de ver la cota $2f + 1$ es pensar en lo que un proceso puede esperar. Si hasta $f$ procesos pueden haberse detenido, ningún protocolo puede exigir respuestas de más de $n - f$ procesos sin arriesgarse a esperar para siempre. Antes de GST, además, los $f$ procesos que no respondieron podrían estar vivos y simplemente retrasados.

Supongamos $n = 2f$. La red podría dividir a los procesos en dos mitades de $f$ y retrasar todos los mensajes entre ellas. Cada mitad ve exactamente lo que vería si la otra se hubiera caído, así que debe decidir por su cuenta, y nada impide que decidan valores distintos. Con $n = 2f + 1$, dos grupos de $f + 1$ procesos siempre comparten al menos uno, y como en este modelo nadie miente, ese proceso común transporta la información correcta. Este argumento es una lectura informal; la demostración rigurosa está en el artículo. [1]

La omisión no cambia la cuenta bajo sincronía parcial porque, mirado desde fuera, un mensaje omitido se parece a un mensaje retrasado, y el modelo ya obliga al protocolo a convivir con retrasos arbitrarios antes de GST.

Por qué con fallas bizantinas hace falta 3f + 1

En el caso bizantino, el proceso común entre dos grupos ya no basta: podría ser uno de los defectuosos y contarle una historia distinta a cada grupo. Firmar no lo evita, porque una réplica bizantina puede firmar válidamente dos mensajes contradictorios.

El protocolo sigue sin poder esperar más de $n - f$ respuestas. Para que dos grupos de ese tamaño compartan al menos un proceso correcto, su intersección debe superar a los $f$ que pueden mentir: $2(n - f) - n \ge f + 1$, es decir, $n \ge 3f + 1$. Con $n = 3f + 1$, cada grupo tiene $2f + 1$ procesos y la intersección tiene al menos $f + 1$. Es la misma aritmética que PBFT convierte en regla de protocolo con $3f + 1$ réplicas y quórums de $2f + 1$ mensajes. [4]

Siguiente lectura

La intersección de quórums que aparece al final se demuestra paso a paso en Quórums en acción. Para ver cómo GST y los timeouts se combinan con esos quórums en un protocolo, continúa con Sincronía parcial y quórums.