Sincronía vs. Asincronía: El caos de no saber si un mensaje se perdió o si la red está saturada

En el artículo sobre el Teorema FLP vimos que basta la posibilidad de una sola falla por parada para que ningún consenso determinista garantice terminar en un sistema asíncrono. [1] Ese resultado tiene una consecuencia práctica inmediata: la hipótesis que hagamos sobre el tiempo decide qué puede prometer un protocolo. Este artículo pone esa hipótesis bajo la lupa.

En un laboratorio, dos servidores conectados por un cable corto intercambian paquetes con latencias pequeñas y bastante estables. En una red de producción la situación es otra: colas en routers, congestión, pausas del proceso por recolección de basura, reinicios o cambios de ruta pueden retrasar un mensaje mucho más de lo habitual. Ninguna de esas causas es exótica, y ninguna avisa antes de ocurrir.

Tres modelos para una sola pregunta

Todos los modelos de tiempo responden a la misma pregunta: ¿cuánto puede tardar un mensaje enviado por un proceso correcto? Las respuestas posibles son tres.

Sincronía. Existe una cota $\Delta$ conocida por todos: un mensaje enviado en el instante $t$ llega antes de $t + \Delta$, y los procesos avanzan a velocidades también acotadas. En este mundo el silencio es información: si el mensaje no llegó a tiempo, el remitente falló. Por eso los protocolos síncronos pueden organizarse en rondas fijas y tratar a quien no habla como caído.

Asincronía. No hay ninguna cota. Un mensaje llega en algún momento finito, pero ese momento puede ser arbitrariamente tardío, y no hay relojes compartidos que ayuden a razonar. Es el modelo de FLP. [1]

Sincronía parcial. Dwork, Lynch y Stockmeyer propusieron un punto intermedio: las cotas de tiempo existen, pero el protocolo no puede contar con ellas desde el principio. En una variante la cota $\Delta$ existe pero no se conoce de antemano; en la otra se conoce, pero solo se cumple a partir de un instante desconocido llamado GST (Global Stabilization Time). [2]

Conviene no confundir el modelo con la red física. Un modelo es un contrato de análisis: dice qué comportamientos del adversario se consideran posibles. Elegir el modelo asíncrono no significa creer que la red sea siempre caótica, sino exigir que el protocolo sobreviva incluso si lo es.

Por qué un mensaje lento es indistinguible de uno perdido

Pongámonos en el lugar de una réplica que espera un voto. Su única evidencia es lo que le llegó por la red y lo que marca su propio reloj. Si el voto no aparece, hay al menos tres explicaciones posibles: el remitente cayó, el mensaje está atrapado en una cola o el remitente es lento. Desde dentro de la réplica, las tres producen exactamente la misma vista local: ningún mensaje.

En sincronía esa ambigüedad desaparece porque la cota $\Delta$ permite descartar las dos últimas explicaciones tras esperar lo suficiente. En asincronía no hay espera que baste. FLP formaliza este punto: un proceso detenido no se distingue de uno muy lento, y la prueba usa precisamente esa indistinguibilidad para construir una ejecución en la que nadie decide. [1]

La consecuencia de diseño es fuerte. Cualquier regla del tipo "si no recibo respuesta en $T$ segundos, entonces el otro falló" es una sospecha, no un hecho. Un protocolo robusto puede usar esa sospecha para cambiar de líder o reintentar, pero no puede usarla para concluir algo que comprometa la consistencia del estado replicado.

El riesgo de apostar safety a una cota de tiempo

Veamos un protocolo hipotético, construido a propósito para fallar. Un líder envía un bloque y aplica la regla: "si en 30 segundos nadie objeta, el bloque queda finalizado". La regla funciona mientras la red cumpla su cota. Si una partición retrasa los mensajes durante 31 segundos, el líder finaliza el bloque, mientras que las réplicas que nunca lo vieron pueden sospechar del líder, elegir otro y aceptar un bloque incompatible. El resultado son dos historias finalizadas.

El error no es haber elegido mal el número 30. Con 300 o con 3000 segundos el escenario sigue siendo posible; solo se vuelve menos frecuente. El error es estructural: la safety del protocolo depende de que la red cumpla una cota temporal. En un entorno donde esa cota puede violarse, una sola violación basta para producir un daño irreversible.

Por eso la literatura BFT parcialmente síncrona adopta una división de responsabilidades: las propiedades de safety (acuerdo y validez) deben valer en cualquier ejecución, sea cual sea el comportamiento temporal de la red, y solo la terminación puede depender de que la red se estabilice. [2]

Asincronía pura: la pared de FLP

Si la sincronía es demasiado optimista, ¿por qué no diseñar directamente para asincronía? Porque ahí aparece FLP: ningún protocolo de consenso determinista puede garantizar a la vez acuerdo, validez y terminación en un sistema asíncrono si un solo proceso puede detenerse. [1]

Leído con cuidado, FLP no prohíbe la safety en asincronía. Lo que prohíbe es combinarla con terminación garantizada en todas las ejecuciones, usando un algoritmo determinista. Eso deja dos salidas clásicas: renunciar al determinismo, por ejemplo con aleatoriedad, o debilitar la hipótesis de asincronía total. La segunda salida es la de buena parte de los protocolos BFT prácticos, HotStuff incluido, y su forma más estudiada es la sincronía parcial. [3]

Sincronía parcial: el compromiso de DLS

La propuesta de Dwork, Lynch y Stockmeyer es pragmática: aceptar que la red puede pasar periodos arbitrariamente malos, siempre que esos periodos no duren para siempre. Sobre ese modelo demostraron protocolos de consenso para varias clases de fallas y caracterizaron cuántas toleran: con fallas bizantinas hace falta $n \ge 3f + 1$, mientras que con fallas por parada u omisión basta $n \ge 2f + 1$. [2]

Lo valioso del modelo es que encaja con la ingeniería real. Una red de producción suele comportarse bien la mayor parte del tiempo y mal durante episodios acotados. La sincronía parcial pide que el protocolo sea seguro durante los episodios malos y que vuelva a avanzar después de ellos, sin que nadie tenga que anunciar cuándo terminaron. [2]

La ventaja frente a la sincronía es clara: el protocolo no depende de acertar una cota para no bifurcarse. La ventaja frente a la asincronía también: la terminación vuelve a ser demostrable, porque el modelo descarta el planificador que retrasa mensajes indefinidamente. El precio es que antes de la estabilización el protocolo puede quedarse quieto, y eso debe considerarse comportamiento esperado, no un fallo. El mecanismo de GST y la intersección de quórums se desarrollan en Sincronía parcial y quórums BFT.

Del modelo al protocolo: el caso HotStuff

HotStuff declara explícitamente el modelo de sincronía parcial. Su argumento de safety no usa el tiempo en absoluto: se apoya en quórums de $2f + 1$ votos y en las reglas de bloqueo. Su argumento de liveness, en cambio, solo aplica después de GST, cuando un mecanismo de sincronización de vistas, el pacemaker, consigue que las réplicas correctas coincidan en una vista con un líder correcto. [3]

HotStuff añade un matiz que el modelo DLS no exigía: la responsividad optimista. Después de GST, un líder correcto puede avanzar en cuanto recibe las respuestas de $n - f$ réplicas, al ritmo del retardo real $\delta$ de la red y no al de la cota máxima $\Delta$. [3] Es decir, la cota $\Delta$ se usa como red de seguridad para abandonar vistas improductivas, no como metrónomo del camino feliz. La relación entre estas tres propiedades se estudia 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.