¿Por qué no podemos usar timeouts fijos (Δ)? Los riesgos de liveness

A primera vista, la solución más intuitiva para programar un protocolo de consenso es definir una constante en el código fuente:

const CONFIG_TIMEOUT_MS = 3000; // 3 segundos fijos

Ese número es una apuesta sobre la red. En este artículo veremos por qué la apuesta puede perderse para siempre, cómo esa pérdida produce un livelock en el que el protocolo nunca viola safety pero tampoco confirma nada, y cómo un pacemaker con timeouts crecientes recupera el progreso.

Un timeout es una apuesta sobre una cota desconocida

El modelo de sincronía parcial de Dwork, Lynch y Stockmeyer tiene dos variantes. En una, existe una cota $\Delta$ para la entrega de mensajes, pero los procesos no la conocen. En la otra, $\Delta$ es conocida, pero solo se cumple a partir de un instante desconocido llamado GST (Global Stabilization Time). [1] Antes de ese punto, la red puede retrasar mensajes tanto como quiera.

Conviene separar dos símbolos que a menudo se confunden. $\Delta$ es una propiedad de la red: cuánto tarda, como máximo, un mensaje entre réplicas correctas una vez estabilizada. $T$ es una decisión de ingeniería: cuánto espera una réplica antes de abandonar la vista actual. Escribir CONFIG_TIMEOUT_MS = 3000 equivale a afirmar que $T$ es suficiente para cubrir todo lo que una vista necesita, es decir, la propuesta, los votos y su agregación, medidos en múltiplos de $\Delta$.

Si esa afirmación es falsa, el protocolo no se equivoca de bloque: la safety de PBFT y de HotStuff se apoya en quórums y certificados, no en relojes. [2] [3] Lo que se pierde es otra cosa: la garantía de que alguna vista termine con un bloque confirmado.

La trampa del cambio de vista infinito

Imaginemos una red de $n = 3f + 1$ nodos donde el protocolo exige $q = 2f + 1$ votos. Hemos fijado un timeout rígido de $T = 3\text{ s}$. Una congestión sostenida eleva la latencia entre validadores a $\delta = 3.1\text{ s}$. Para simplificar, supongamos que una vista solo necesita que la propuesta llegue a tiempo; con votos y agregación la cuenta empeora, pero el argumento es idéntico.

Veamos la secuencia de eventos:

1. Vista 1: el líder correcto $L_1$ genera una propuesta válida para el bloque $B_1$ en $t = 0$ y la difunde.
2. Tránsito: la propuesta tardará $3.1\text{ s}$ en llegar a las réplicas.
3. Timeout en $t = 3.0\text{ s}$: los temporizadores expiran. Las réplicas sospechan de $L_1$, envían su mensaje new-view y avanzan a la vista 2.
4. Llegada en $t = 3.1\text{ s}$: la propuesta de $L_1$ llega, pero las réplicas ya están en la vista 2 y la descartan por pertenecer a una vista anterior.
5. Vista 2: el nuevo líder $L_2$ propone en torno a $t = 3.0\text{ s}$. Su propuesta llega en $t = 6.1\text{ s}$, pero el temporizador de la vista 2 expira en $t = 6.0\text{ s}$.
6. Repetición: el patrón se reproduce en la vista 3, la 4 y todas las siguientes mientras $\delta$ se mantenga por encima de $T$.

Figura 1

El bucle infinito de timeouts estáticos

Fuentes:

[1]

Cómo leer esta figura

El diagrama de carriles muestra vistas consecutivas v1, v2 y v3. En cada vista, la propuesta enviada por el líder tarda δ = 3.1s. La ventana de timeout expira en 3.0s, provocando un cambio de vista antes de procesar el voto. La cadena de bloques permanece vacía indefinidamente.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Este fenómeno se denomina livelock: el sistema está activo, intercambia mensajes y cambia de líder, pero no progresa. Safety se conserva por completo, porque nadie confirmó un bloque incorrecto; el throughput, en cambio, es cero. Desde fuera es indistinguible de un sistema caído, y por eso suele diagnosticarse tarde.

Ojo con un detalle: el problema no es que todos los líderes sean lentos, sino que el protocolo no aprende del fracaso. Cada vista repite exactamente la misma apuesta con el mismo resultado.

Por qué ninguna constante es segura para liveness

¿No bastaría con elegir un $T$ generoso, por ejemplo $30\text{ s}$? Depende de la variante del modelo. Si $\Delta$ es conocida y solo falta esperar a GST, un timeout fijo calculado a partir de $\Delta$ funciona después de GST. [1] El riesgo aparece en la variante en que $\Delta$ existe pero nadie la conoce: para cualquier constante $T$ elegida de antemano, existen ejecuciones válidas del modelo en las que la latencia real supera a $T$ indefinidamente, y en todas ellas se repite el bucle anterior.

En sistemas reales la distinción no es académica. El operador no conoce $\Delta$; la estima a partir de mediciones pasadas, y la red cambia por despliegues en nuevas regiones, por congestión o por un adversario que ralentiza tráfico de forma selectiva. Un valor que era cómodo durante las pruebas se vuelve insuficiente en producción.

El argumento contrario también importa. Un $T$ fijo enorme sí evita el livelock por latencia, pero cobra un precio en cada falla del líder: si el líder de la vista está caído, todas las réplicas correctas esperan el timeout completo antes de reemplazarlo. Un timeout fijo obliga entonces a elegir entre dos fallos: demasiado corto produce livelock; demasiado largo convierte cada líder caído en una pausa larga. Ninguna constante resuelve ambos extremos a la vez.

Backoff: dejar que el timeout alcance la cota desconocida

La salida clásica es dejar de tratar el timeout como una constante y convertirlo en un estado local que reacciona a los fracasos. PBFT ya lo hacía: si el temporizador de una réplica expira en la vista $v + 1$ antes de recibir un mensaje new-view válido, la réplica inicia el cambio a la vista $v + 2$, pero esta vez espera el doble de tiempo antes de volver a abandonar la vista. [2] Los timeouts se duplican mientras los cambios de vista sigan siendo consecutivos.

Generalizando, la regla de actualización tras una vista fallida es:

$T_{v+1} = \min\left(T_v \cdot \gamma, \, T_{\max}\right) \quad \text{con } \gamma > 1$

• $\gamma = 2$ reproduce la duplicación de PBFT; otros diseños usan factores menores para crecer de forma más suave.
• $T_{\max}$ es un tope de ingeniería que evita esperas absurdas; si se fija por debajo de la cota real, vuelve a introducir el problema de la constante, de modo que debe elegirse con holgura.
• En el ejemplo anterior, con $T_1 = 3.0\text{ s}$ y $\gamma = 2$, la vista 2 espera $6.0\text{ s}$, más que los $3.1\text{ s}$ de la red, y la propuesta llega antes de que expire el temporizador.

La razón por la que esto funciona es simple: una sucesión geométrica con razón mayor que uno no está acotada. Para cualquier cota finita $D$ que necesite una vista después de GST, existe un $k$ finito con $T_1 \cdot \gamma^k \ge D$, y basta con aproximadamente $\log_\gamma(D / T_1)$ vistas fallidas para alcanzarlo. [1] El costo del error inicial es logarítmico, no indefinido.

El pacemaker como módulo separado en HotStuff y DiemBFT

El teorema anterior tiene una condición escondida: las réplicas correctas deben estar en la misma vista al mismo tiempo, y esa vista debe tener un líder correcto. Si cada réplica duplica su temporizador por su cuenta y entra en vistas distintas, el crecimiento del timeout no basta.

HotStuff hace explícita esa división de trabajo. El protocolo de votación, con sus QCs y su regla de bloqueo, garantiza safety bajo cualquier patrón de retrasos; un módulo aparte, el pacemaker, se encarga de sincronizar vistas y elegir líderes para que, después de GST, las réplicas correctas coincidan con un líder correcto durante el tiempo suficiente. [3] La política concreta de timeouts vive en ese módulo y puede cambiarse sin tocar el argumento de safety. Los detalles del cambio de vista están en view-change y pacemaker en HotStuff.

DiemBFT, un descendiente productivo de HotStuff, materializa la sincronización con un objeto verificable. Cuando el temporizador de una ronda expira, cada réplica difunde un mensaje de timeout firmado; $2f + 1$ de esos mensajes forman un timeout certificate (TC). [4] Una réplica avanza a la ronda siguiente al observar un QC o un TC de la ronda actual, de modo que el avance de ronda queda respaldado por un quórum y no por la impaciencia de una réplica aislada. [4]

La combinación es la que da liveness: los certificados alinean a las réplicas en la misma ronda, y el crecimiento del timeout garantiza que, una vez alineadas, la ronda dure lo suficiente.

Costos del backoff y decisiones de diseño

El backoff no es gratis. Después de una racha de fallos, el timeout queda alto, y si el siguiente líder está caído, las réplicas esperan más de lo necesario para reemplazarlo. Por eso todo pacemaker necesita una política de descenso: cuándo y cuánto reduce $T_v$ tras observar progreso. Reiniciar al valor base después de cada bloque confirmado reacciona rápido a una red que mejoró, pero puede devolver al sistema al borde del livelock si la latencia sigue alta; reducir gradualmente es más conservador y más lento.

Tampoco hay que confundir capas. El timeout solo decide cuándo abandonar una vista. Lo que se puede votar y confirmar lo deciden los quórums y los locks, y por eso un timeout mal calibrado degrada liveness y latencia, pero no puede producir dos bloques confirmados en conflicto. [3] Esa separación es la que permite experimentar con políticas de timeout sin rehacer la prueba de safety.

Finalmente, el backoff no elimina el costo de esperar timeouts cuando el líder falla; solo garantiza que la espera termine siendo suficiente. La propiedad que HotStuff busca en el caso bueno, avanzar a la velocidad real de la red una vez que hay un líder correcto, se llama responsiveness y se discute en safety, liveness y responsiveness en HotStuff.

Siguiente lectura

Continúa con view-change y pacemaker en HotStuff para ver cómo el cambio de vista transporta highQC entre líderes, y con safety, liveness y responsiveness para cerrar la discusión sobre cuándo el protocolo avanza a la velocidad real de la red.