Replicación de Máquina de Estados (SMR) con manzanas y peras

En el banco sin cajero central vimos la intuición: varias réplicas sin jefe pueden mantener el mismo estado si respetan un orden total y ejecutan de forma determinista. Ahora toca bajar al detalle y seguir, paso a paso, cómo evoluciona el estado interno de cada réplica cuando llegan operaciones.

Para ello usaremos una metáfora deliberadamente sencilla: una cadena de fruterías con 4 sucursales, que llamaremos réplicas $N_1$, $N_2$, $N_3$ y $N_4$. Cuatro no es un número casual: es el comité mínimo $3f + 1$ para tolerar $f = 1$ réplica bizantina, el tamaño que usan los protocolos de la serie. [1]

La frutería replicada, paso a paso

Supongamos que las 4 sucursales inician la mañana con el mismo inventario:

• Estado inicial $S_0$: 10 manzanas y 5 peras.

A lo largo de la mañana llegan dos operaciones de clientes:

1. Transacción $T_1$: "recibir 3 manzanas", que suma 3 al contador de manzanas.
2. Transacción $T_2$: "vender 2 peras", que resta 2 al contador de peras si hay existencias suficientes.

Si el protocolo de consenso fija que el orden es primero $T_1$ y después $T_2$, cada réplica calcula por su cuenta:

$S_1 = f(S_0, T_1) = (13 \text{ manzanas},\ 5 \text{ peras})$

$S_2 = f(S_1, T_2) = (13 \text{ manzanas},\ 3 \text{ peras})$

Al terminar, las 4 sucursales tienen 13 manzanas y 3 peras. Ninguna tuvo que copiar el inventario de otra ni preguntar el resultado; todas lo calcularon de forma independiente y coincidieron. Esa es la idea central de SMR: no se replican los datos, se replica la historia que produce los datos.

Castro y Liskov formulan el mismo modelo para PBFT: el servicio es una máquina de estados replicada, las réplicas deben ser deterministas y deben empezar en el mismo estado. [1] Con esas dos condiciones, el único trabajo del protocolo es garantizar que las réplicas no defectuosas ejecuten las peticiones en el mismo orden total. [1]

Por qué el orden importa: operaciones que no conmutan

En el ejemplo anterior el orden daba igual: sumar manzanas y restar peras afectan a contadores distintos, así que $T_1$ y $T_2$ conmutan. Eso es una casualidad del ejemplo, no una propiedad general. Basta con cambiar la segunda operación para verlo.

Supongamos ahora que $T_2$ es "duplicar el inventario de manzanas", por ejemplo porque llega un pedido que repone exactamente lo que hay en estantería. Partiendo de 10 manzanas:

• Orden $T_1, T_2$: $10 + 3 = 13$, y después $13 \cdot 2 = 26$ manzanas.
• Orden $T_2, T_1$: $10 \cdot 2 = 20$, y después $20 + 3 = 23$ manzanas.

Las dos réplicas aplicaron las mismas operaciones, ambas de forma determinista, y aun así terminaron con estados distintos. El determinismo solo garantiza igualdad si la secuencia es la misma. Por eso la regla de oro exige las dos condiciones a la vez.

Uno podría pensar en evitar el problema permitiendo solo operaciones conmutativas. Para un inventario simple quizá funcione, pero en cuanto aparecen reglas como "vender solo si hay existencias" o "aplicar un descuento del 10 %", el orden vuelve a importar. Un retiro que es válido después de una reposición puede ser inválido antes. Es la misma estructura del doble gasto: la validez de una operación depende de lo que ocurrió antes.

El log: la pieza que replica el consenso

Si el estado se deriva de la historia, lo que realmente hay que acordar es esa historia: una lista numerada de operaciones, el log. El estado en cada réplica es simplemente el resultado de aplicar el log desde $S_0$.

HotStuff describe su objetivo justo en estos términos: es un protocolo de replicación BFT en el que las réplicas acuerdan una secuencia creciente de comandos propuestos por los clientes. [2] En HotStuff los comandos viajan agrupados en bloques encadenados, y una réplica ejecuta los comandos de un bloque cuando ese bloque queda confirmado por la regla de commit del protocolo, siguiendo el orden de la cadena. [2]

Esta visión tiene una consecuencia arquitectónica importante: el consenso no necesita entender las operaciones. Para ordenar "recibir 3 manzanas" y "duplicar manzanas" no hace falta saber nada de fruta; basta con tratarlas como comandos opacos y fijar su posición. La aplicación, por su parte, no necesita saber nada de quórums: recibe comandos en orden y los ejecuta. Esa separación entre ordenar y ejecutar es una idea de diseño general de SMR, y permite cambiar la lógica de la aplicación sin tocar el protocolo de acuerdo, siempre que la nueva lógica siga siendo determinista.

Dónde se rompe la regla en la práctica

La regla de oro es una implicación: si el log es el mismo y la ejecución es determinista, el estado es el mismo. En sistemas reales hay que vigilar las dos premisas.

El log puede diferir si el protocolo de consenso falla o si una réplica es bizantina. Una réplica bizantina puede ignorar el log, ejecutar otra cosa o mentir sobre su estado. SMR no promete nada sobre ella; promete que las réplicas correctas coinciden. Por eso el problema de fondo es el de los generales bizantinos: que todos los participantes leales actúen sobre la misma información aunque algunos mientan. [3] Lamport, Shostak y Pease también señalan que un sistema fiable basado en varios procesadores que votan solo funciona si todos los procesadores correctos usan la misma entrada. [3]

La ejecución puede no ser determinista sin que nadie lo note. Leer el reloj local, generar un número aleatorio, recorrer una tabla hash cuyo orden de iteración varía entre ejecuciones o depender de la precisión de punto flotante de cada máquina son fuentes clásicas de divergencia. PBFT reconoce el problema y propone que el valor no determinista se fije de forma acordada, por ejemplo propuesto por el primario, en lugar de que cada réplica lo calcule por su cuenta. [1]

Además, PBFT incluye un mecanismo que ayuda a comprobar el estado: las réplicas generan periódicamente puntos de control con un resumen de su estado, y un punto de control se considera estable cuando lo respaldan $2f + 1$ réplicas. [1] Ese mecanismo permite descartar mensajes antiguos del log y da un punto de referencia común sobre el estado.

Qué pide SMR a cada capa

Resumiendo el reparto. El protocolo de consenso se compromete a que todas las réplicas correctas vean el mismo log, con las mismas operaciones en las mismas posiciones, tolerando hasta $f$ réplicas bizantinas en un comité de $3f + 1$. [2] La aplicación se compromete a que su función de transición sea determinista. Y el estado inicial se fija una vez, idéntico para todos.

Con esas tres piezas, la frutería de cuatro sucursales se comporta como si fuera una sola tienda, aunque una de ellas mienta. Lo que queda por estudiar, y ocupa el resto de la serie, es cómo construir el log de forma eficiente: cuántos mensajes cuesta, cómo se reemplaza a un líder que falla y cuándo puede una réplica dar una posición del log por definitiva.

Criterios clave

Siguiente lectura

Para ver cómo un protocolo concreto construye ese log ordenado, sigue con PBFT 1999: tres pasos de confirmación. Si quieres saltar directamente a la versión de HotStuff, lee QC, highQC y three-chain.