El Teorema FLP: Por qué una sola computadora lenta puede romper el acuerdo

En 1985, Michael Fischer, Nancy Lynch y Michael Paterson publicaron en el Journal of the ACM un artículo breve que fijó un límite duro para toda la disciplina: "Impossibility of Distributed Consensus with One Faulty Process". [1]

Tras estudiar quórums en Consenso BFT desde cero, es natural preguntarse: si la aritmética de $q = 2f + 1$ sobre $n = 3f + 1$ es tan sólida, ¿podemos construir un protocolo que jamás se detenga, sin importar lo mala que sea la red? La respuesta de FLP es que no, al menos no con un algoritmo determinista y sin ninguna hipótesis temporal. Y lo sorprendente es que el obstáculo no requiere traidores bizantinos: basta un proceso que pueda detenerse en silencio.

El modelo exacto que asume FLP

La fuerza del teorema está en lo débil que es el adversario. FLP no supone mensajes falsificados, firmas rotas ni nodos maliciosos. Supone un sistema de $n$ procesos que se comunican por mensajes, con estas reglas: [1]

1. Asincronía completa: no hay relojes sincronizados, no hay cota conocida $\Delta$ para la entrega de mensajes y no hay cota para la velocidad relativa de los procesos.
2. Canales fiables: ningún mensaje se pierde ni se duplica; todo mensaje enviado a un proceso que sigue vivo termina entregándose, pero en un orden y un momento arbitrarios.
3. Determinismo: cada proceso es una máquina de estados; dado su estado y el mensaje recibido, su siguiente paso está completamente determinado.
4. Una falla por parada: a lo sumo un proceso puede detenerse (crash) y, desde fuera, una parada es indistinguible de un proceso extremadamente lento.

Cada proceso tiene un bit de entrada en $\{0,1\}$ y un registro de salida que se escribe una sola vez. El protocolo es parcialmente correcto si ningún par de procesos decide valores distintos y si ambas decisiones, $0$ y $1$, son posibles para alguna combinación de entradas. Esa última condición descarta el truco trivial de decidir siempre $0$.

Comparado con el problema de los generales bizantinos, el contraste es instructivo. Lamport, Shostak y Pease estudiaron un modelo síncrono, con rondas y relojes, y adversarios que mienten; allí demostraron que con mensajes orales no hay solución si un tercio o más de los generales son traidores. [3] FLP invierte los ejes: la falla es la más benigna posible, pero el tiempo deja de estar acotado. Y eso basta para perder la terminación garantizada. [1]

El enunciado: qué se pierde y qué no

El Teorema FLP establece que:

En un sistema distribuido asíncrono, no existe ningún protocolo de consenso determinista que sea parcialmente correcto y que además garantice la terminación de todos los procesos correctos si se permite que un solo proceso ($f = 1$) falle por parada.

Conviene leerlo con precisión. FLP no dice que el consenso nunca termine en la práctica, ni que todo protocolo viole safety. Dice que, para cualquier protocolo determinista que respete acuerdo y validez, existe al menos una ejecución admisible en la que nadie decide jamás. [1]

Un detalle sutil, y muy útil para leer papers posteriores, es que la ejecución no terminante que construye la prueba ni siquiera necesita que algún proceso falle de verdad. Todos los procesos dan infinitos pasos y todos los mensajes terminan entregándose. La mera posibilidad de una parada es lo que obliga al protocolo a no poder esperar indefinidamente a nadie, y esa obligación es la grieta que explota el planificador.

Figura 1

El laberinto de la bivalencia en FLP

Fuentes:

[1]

Cómo leer esta figura

El diagrama muestra configuraciones globales de red. Las configuraciones bivalentes C0 y C1 tienen caminos hacia decisiones de valor 0 o valor 1. Al retrasar estratégicamente el mensaje m que forzaría la decisión hacia univalencia, el adversario fuerza al sistema a transicionar a otro estado bivalente C2, atrapando el consenso en un bucle infinito.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Configuraciones bivalentes y univalentes

La prueba razona sobre configuraciones: el estado interno de todos los procesos junto con el conjunto de mensajes en vuelo. Un paso consiste en entregar un mensaje $m$ a un proceso $p$ (o entregarle "nada"), que entonces cambia de estado y puede enviar nuevos mensajes. Con ese vocabulario se definen dos clases:

• Configuración bivalente: desde ella son alcanzables ejecuciones que deciden $0$ y ejecuciones que deciden $1$. El resultado todavía no está escrito.
• Configuración univalente ($0$-valente o $1$-valente): todas las ejecuciones alcanzables deciden el mismo valor, aunque ningún proceso lo haya escrito aún en su registro de salida.

Esta distinción es la pieza conceptual clave. La decisión "real" del sistema ocurre en el instante en que la configuración pasa de bivalente a univalente, no cuando un proceso escribe su salida. Un protocolo que termina tiene que cruzar esa frontera en algún paso concreto. FLP demuestra que el planificador siempre puede impedir que ese cruce ocurra. [1]

La demostración en tres lemas

La estructura de la prueba es corta y elegante. Vale la pena seguirla con calma porque sus ideas reaparecen en casi todos los argumentos de imposibilidad posteriores. [1]

Lema 1, conmutatividad. Si dos secuencias de pasos afectan a conjuntos disjuntos de procesos, aplicarlas en un orden o en el otro conduce a la misma configuración. Es una observación casi obvia sobre independencia, pero permite intercambiar el orden de eventos dentro de la prueba.

Lema 2, existe una configuración inicial bivalente. Supongamos, por contradicción, que todas las configuraciones iniciales fueran univalentes, y ordenémoslas las configuraciones iniciales de forma que dos vecinas difieran solo en la entrada de un proceso $p$. Por validez, hay una configuración inicial $0$-valente y otra $1$-valente, así que en esa cadena existen dos vecinas, una $0$-valente y otra $1$-valente, que difieren solo en $p$.

Ahora consideremos una ejecución en la que $p$ no da ningún paso, algo que el protocolo debe tolerar porque $p$ podría haber caído. Esa ejecución es indistinguible desde ambas configuraciones para todos los demás procesos, de modo que decide el mismo valor en las dos. Contradicción: alguna configuración inicial tiene que ser bivalente.

Lema 3, siempre se puede seguir siendo bivalente. Sea $C$ bivalente y sea $e = (p, m)$ un evento aplicable a $C$. Si consideramos todas las configuraciones alcanzables desde $C$ sin aplicar $e$, y luego aplicamos $e$ al final, al menos una de las configuraciones resultantes es bivalente.

La prueba procede por contradicción. Si todas fueran univalentes, habría dos configuraciones vecinas, separadas por un solo evento $e'$, con valencias distintas tras aplicar $e$. Si $e'$ ocurre en un proceso distinto de $p$, el Lema 1 hace que ambos órdenes coincidan, lo que es imposible. Si $e'$ también ocurre en $p$, se considera una ejecución finita en la que $p$ no da pasos y el resto del sistema decide, algo que el protocolo debe permitir porque $p$ podría haber caído. Por el Lema 1, la configuración alcanzada por esa ejecución, que ya contiene una decisión, todavía podría conducir tanto a $0$ como a $1$: sería bivalente, lo que es imposible.

Ese segundo caso es el único lugar donde la prueba usa la falla por parada, y lo usa una sola vez. Es exactamente la razón por la que $f = 1$ basta.

El planificador que nunca deja decidir

Con los lemas, la ejecución infinita se construye por etapas. El planificador mantiene una cola de procesos y, en cada etapa, toma el proceso $p$ que está al frente y el mensaje más antiguo $m$ pendiente para él. Por el Lema 3, existe una forma de llegar a otra configuración bivalente cuyo último paso es justamente entregar $m$ a $p$. El planificador ejecuta esa secuencia, mueve a $p$ al final de la cola y repite. [1]

El resultado es una ejecución en la que cada proceso da infinitos pasos, cada mensaje termina entregándose y, sin embargo, la configuración nunca deja de ser bivalente. Ningún proceso puede decidir sin arriesgarse a contradecir otra ejecución alcanzable.

Desde dentro de un proceso, el dilema es siempre el mismo. Cuando falta una respuesta, no puede distinguir entre "el remitente cayó" y "el mensaje viene muy lento". Si decide sin esa información, puede violar acuerdo; si espera, el planificador puede hacerle esperar para siempre. FLP formaliza que ninguna regla determinista resuelve ese dilema en todos los casos.

Cómo evaden FLP los protocolos BFT reales

Si el consenso determinista es imposible en asincronía, ¿cómo funcionan Tendermint o HotStuff? Relajando exactamente una de las hipótesis del teorema, sin tocar las demás.

1. Sincronía parcial. Dwork, Lynch y Stockmeyer propusieron un modelo en el que la red puede comportarse de forma asíncrona durante un periodo arbitrario, pero eventualmente existe una cota $\Delta$ sobre la entrega de mensajes a partir de un instante desconocido, GST. En ese modelo el consenso es alcanzable tolerando $f$ fallas bizantinas con $n \ge 3f + 1$. [2] La clave es que safety se mantiene siempre, y solo la terminación depende de que llegue GST; lo desarrollamos en Sincronía parcial y quórums BFT.
2. Aleatorización. Si los procesos pueden lanzar monedas, la ejecución no terminante sigue existiendo, pero su probabilidad puede hacerse cero: el protocolo termina con probabilidad $1$. Esta vía abandona la hipótesis de determinismo, no la de asincronía.
3. Detectores de fallas. Otra familia añade un oráculo que sospecha de procesos caídos con cierta precisión eventual. Formalmente equivale a introducir información temporal que el modelo FLP no tiene.

HotStuff es un ejemplo directo de la primera vía. Su análisis declara el modelo de sincronía parcial: la seguridad vale en cualquier ejecución, mientras que el progreso se garantiza después de GST mediante un mecanismo de sincronización de vistas, el pacemaker. [4] El diseño del pacemaker se estudia en View-change y pacemaker en HotStuff.

Lo que FLP enseña sobre safety y liveness

El legado práctico de FLP no es pesimismo, sino una disciplina de diseño. Si la terminación no se puede garantizar en todas las ejecuciones asíncronas, entonces el protocolo tiene que decidir qué propiedad sacrifica temporalmente. La respuesta casi unánime de la literatura BFT es: nunca safety, a veces liveness. [2]

Eso se traduce en invariantes concretos. Un timeout puede cambiar el ritmo del protocolo, provocar un cambio de líder o una nueva vista, pero no puede autorizar a una réplica a votar por algo incompatible con lo que ya certificó. Los quórums y los certificados conservan la memoria segura; los relojes solo deciden cuándo vale la pena intentar de nuevo. [4]

La consecuencia operativa es fácil de olvidar. Un sistema BFT que se detiene durante una partición de red no está "roto": está ejecutando exactamente el compromiso que FLP obliga a aceptar. El error de diseño sería el contrario, un protocolo que decide con prisa durante la asincronía y luego descubre dos historias confirmadas. La relación formal entre ambas propiedades y la responsividad se retoma en Safety, liveness y responsiveness en HotStuff.

Siguiente lectura

Continúa con Sincronía parcial y quórums BFT, donde GST y la intersección de quórums explican cómo un protocolo recupera el progreso sin renunciar a safety.