El concepto de GST: El momento mágico en el que la tormenta de red cesa

En Sincronía parcial y quórums BFT presentamos la sincronía parcial como la salida práctica al Teorema FLP. La pieza que hace funcionar ese modelo es un concepto con nombre solemne: GST, o Global Stabilization Time, introducido por Dwork, Lynch y Stockmeyer en 1988. [1]

El nombre invita a una lectura equivocada. Suena a una alarma global, a un reloj atómico compartido o a un mensaje que anuncia "la red ya está bien". No es nada de eso. GST es una herramienta de análisis: un instante que existe en la demostración, que ninguna réplica observa y que el código del protocolo no menciona. Entender esa distinción es la mitad del camino para leer bien cualquier argumento de liveness de la familia HotStuff.

Qué afirma exactamente GST

En el modelo con GST, la cota de comunicación $\Delta$ es conocida, pero solo se garantiza a partir de un instante $t_{\text{GST}}$ que nadie conoce de antemano. [1] Escrito de forma compacta, si $s(m)$ es el instante de envío y $r(m)$ el de entrega de un mensaje $m$ entre procesos correctos:

$\exists\, t_{\text{GST}} < \infty \;:\; s(m) \ge t_{\text{GST}} \implies r(m) \le s(m) + \Delta$

Hay tres ideas dentro de esa línea. Primero, GST es finito: la estabilización ocurre en alguna ejecución concreta, aunque sea muy tarde. Segundo, antes de GST no se promete nada sobre los retardos: la red puede comportarse como en el modelo asíncrono de FLP. Tercero, GST es una propiedad de la ejecución, no un parámetro del protocolo: el protocolo debe funcionar para cualquier valor que el adversario elija.

Las formulaciones posteriores difieren en detalles, por ejemplo en cómo tratan los mensajes enviados antes de GST, así que al leer un paper conviene comprobar qué versión exacta del supuesto usa. La idea central es siempre la misma: hay un prefijo de la ejecución sin garantías temporales y un sufijo con ellas.

Figura 1

La línea de tiempo de GST en sincronía parcial

Fuentes:

[1]

Cómo leer esta figura

El diagrama muestra el eje del tiempo t. A la izquierda de t_GST, las flechas de mensajes sufren demoras variables e indefinidas sin violar safety. En t_GST la red se estabiliza; a la derecha, todos los mensajes entre réplicas correctas se entregan dentro de la ventana Δ.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Las dos variantes de DLS: cota desconocida o cota tardía

El paper de DLS no define una sola sincronía parcial, sino dos modelos emparentados. [1]

1. La cota existe pero no se conoce. Hay un $\Delta$ fijo que se cumple durante toda la ejecución, pero el protocolo no sabe cuánto vale. No puede escribir "espera $\Delta$" en su código, porque no tiene el número.
2. La cota se conoce pero solo vale después de GST. El protocolo sabe cuánto vale $\Delta$, pero no sabe desde cuándo se cumple. Antes de $t_{\text{GST}}$ cualquier retardo es posible.

Las dos variantes capturan intuiciones distintas. La primera describe una red que siempre se porta razonablemente, pero cuya latencia real ignoramos. La segunda describe una red cuya latencia conocemos en régimen normal, pero que puede atravesar un periodo de caos de duración desconocida. DLS considera además cotas análogas sobre la velocidad relativa de los procesadores, no solo sobre la comunicación. [1]

En ambas variantes el obstáculo es el mismo: el protocolo no puede fijar de antemano cuánto esperar. Por eso las soluciones se parecen: rondas o vistas que se repiten, y una forma de garantizar que, tarde o temprano, alguna ronda transcurra con la red cumpliendo la cota. Los protocolos BFT de la línea de HotStuff suelen redactar sus argumentos de liveness con la segunda variante, hablando explícitamente de "después de GST". [3]

Safety en toda ejecución, liveness después de GST

La consecuencia más importante del modelo es una asimetría entre propiedades. Los protocolos de DLS garantizan acuerdo y validez en toda ejecución, incluso en el prefijo caótico anterior a GST; la terminación es lo único que se garantiza solo una vez que las cotas se cumplen. [1]

La asimetría no es una preferencia estética, sino una necesidad lógica. Como ninguna réplica sabe si GST ya ocurrió, ninguna puede razonar "la red ya es estable, así que puedo relajar mis reglas". Cualquier regla de safety que dependiera de la estabilización podría activarse justo en el prefijo malo y producir dos decisiones incompatibles, y safety es una propiedad que se rompe en un instante finito y no se repara después.

Con liveness ocurre lo contrario: es una propiedad sobre el futuro. Decir "el protocolo termina decidiendo" admite que antes de decidir pase un tiempo arbitrario. Por eso puede apoyarse en GST sin contradicción: el adversario puede retrasar el progreso tanto como quiera antes de GST, pero no puede impedirlo para siempre.

Esto también explica la relación con FLP. La ejecución infinita sin decisión que construye FLP requiere un planificador que retrase mensajes indefinidamente. [2] El supuesto de GST excluye exactamente ese planificador a partir de cierto instante, y con ello reabre la puerta a demostrar terminación sin tocar el argumento de safety.

Por qué ninguna réplica necesita saber cuándo ocurre GST

El código de una réplica no contiene ninguna variable llamada GST. Lo que contiene son temporizadores locales, números de vista y reglas para cambiar de líder. ¿Cómo puede entonces el protocolo aprovechar algo que no observa?

La respuesta está en la forma del argumento. El protocolo intenta progresar en vistas sucesivas. Cada intento fallido cuesta tiempo, pero no compromete safety, porque las reglas de voto se basan en quórums y certificados, no en relojes. La demostración de liveness solo necesita probar que, después de GST, llegará una vista con un líder correcto en la que las réplicas correctas permanezcan el tiempo suficiente para completar el protocolo.

En HotStuff, esa tarea recae en el pacemaker, el mecanismo que sincroniza vistas y elige líderes; el paper separa explícitamente esa función de las reglas de safety y garantiza progreso después de GST. [3] Una técnica habitual en estos mecanismos es aumentar el timeout tras cada vista fallida: si el valor inicial era demasiado corto para la latencia real, tarde o temprano deja de serlo, sin que nadie haya tenido que conocer GST ni el retardo verdadero. Por qué no basta con un timeout fijo se analiza en Por qué no timeouts fijos.

Lo que GST no dice

GST suele malinterpretarse en tres sentidos, y cada malentendido produce errores de diseño distintos.

No es un evento observable. Ninguna réplica puede detectar que GST ocurrió. Una racha de mensajes rápidos no prueba nada: el adversario podría volver a retrasarlos un instante después si GST aún no llegó. Un protocolo que "detecta la estabilidad" y relaja sus reglas está reintroduciendo una dependencia temporal en safety.

No promete una red perfecta para siempre en la práctica. El modelo dice que, a partir de GST, la cota vale indefinidamente. Las redes reales alternan periodos buenos y malos. La lectura práctica es que el periodo estable debe durar lo suficiente para que el protocolo complete una decisión; cuando vuelve el caos, safety sigue intacta y el progreso se reanuda en el siguiente periodo estable.

No fija la velocidad del progreso. GST garantiza que el progreso ocurrirá, no lo rápido que será. Un protocolo puede terminar después de GST esperando siempre el máximo $\Delta$ en cada paso. HotStuff va más allá con la responsividad optimista: después de GST y con líder correcto, avanza al ritmo del retardo real $\delta$ de la red, que puede ser mucho menor que $\Delta$. [3] Esa diferencia se estudia en Safety, liveness y responsiveness en HotStuff.

Siguiente lectura

Continúa con ¿Por qué no podemos usar timeouts fijos?, donde se analiza qué ocurre con la liveness cuando la espera $\Delta$ se fija de antemano.