El Pacemaker en detalle: Coordinar relojes en el caos sin sobrecargar la red

En Cambio de vista y Pacemaker vimos la idea general: HotStuff separa las reglas que protegen safety del mecanismo que garantiza progreso. Este artículo baja un nivel. Queremos entender qué decisiones toma exactamente ese mecanismo, qué información necesita y por qué los descendientes de producción, como DiemBFT, le añadieron un objeto nuevo: el certificado de timeout.

La pregunta guía es sencilla. Las réplicas no comparten un reloj. Cada una mide el tiempo con su propio temporizador y ve los mensajes con retrasos distintos. ¿Cómo se ponen de acuerdo en cuándo abandonar a un líder sin que ese acuerdo se convierta en un consenso dentro del consenso?

Por qué separar safety de la sincronización de vistas

El paper de HotStuff describe el protocolo como un núcleo de reglas de voto y bloqueo más un componente llamado Pacemaker, cuya única responsabilidad es la liveness. [1] El núcleo decide cuándo es seguro votar: una réplica guarda su lockedQC y solo acepta una propuesta si extiende ese bloqueo o si trae un QC de vista más alta. El Pacemaker decide cuándo cambiar de vista y quién lidera la siguiente.

La consecuencia práctica es fuerte. La safety de HotStuff no depende de que el Pacemaker funcione bien. [1] Si el Pacemaker elige mal los tiempos, rota líderes de forma torpe o deja a las réplicas en vistas distintas, el sistema puede quedarse sin progreso, pero las reglas de voto siguen impidiendo dos commits en conflicto. Ojo con esto al depurar: un bug de Pacemaker se manifiesta como estancamiento o latencia, no como bifurcación.

Esta separación tiene raíz en el modelo de sincronía parcial. En ese modelo existe un instante desconocido, GST, después del cual los mensajes entre réplicas correctas llegan dentro de una cota $\Delta$; antes de GST no hay cota útil. [4] Safety tiene que sobrevivir a cualquier retraso, así que no puede apoyarse en relojes. Liveness, en cambio, solo se promete después de GST, y ahí sí pueden entrar los temporizadores. El Pacemaker es el lugar donde se concentra todo lo que depende del tiempo.

Rotación de líderes y el mensaje new-view en HotStuff

Cada vista tiene un líder determinado por una función conocida de antemano, de modo que todas las réplicas saben a quién esperar sin intercambiar mensajes para elegirlo. [1] Una rotación por turnos es la opción más simple. Rotar en cada vista, y no solo cuando el líder falla, reparte la carga de proponer y limita cuánto tiempo puede retrasar un líder bizantino el sistema.

Cuando una réplica pasa a la vista $v + 1$, envía al nuevo líder un mensaje new-view con el QC más alto que conoce, su $\operatorname{highQC}_i$. El líder espera $n - f$ de esos mensajes, elige el QC de mayor vista y construye su propuesta sobre él. [1] Como cada mensaje lleva un solo certificado y el líder reenvía solo el mejor, el cambio de vista mantiene comunicación lineal en el número de réplicas.

En HotStuff el new-view va dirigido al líder siguiente, no a todos. Eso ahorra mensajes, pero deja una pregunta abierta: ¿qué pasa si las réplicas no entran en la vista $v + 1$ más o menos al mismo tiempo? El paper reconoce que sincronizar vistas es un problema en sí mismo y lo delega al Pacemaker sin fijar una única implementación. [1]

Timeouts: el reloj que cada réplica lleva por su cuenta

Un temporizador local solo responde a una pregunta: ¿cuánto estoy dispuesto a esperar al líder de esta vista? Si el valor es demasiado corto, las réplicas abandonan líderes correctos que simplemente están lentos. Si es demasiado largo, un líder caído paraliza el sistema durante todo ese tiempo.

Antes de GST ningún valor fijo es correcto, porque la red no tiene cota. La solución habitual es hacer crecer el temporizador cuando las vistas fallan seguidas, por ejemplo duplicándolo, y reducirlo cuando vuelve el progreso. Con un crecimiento así, después de GST el temporizador termina superando el tiempo real que necesita una vista completa, aunque nadie conozca $\Delta$. Ese razonamiento es la versión operativa del modelo de sincronía parcial. [4] La política concreta de crecimiento es una decisión de implementación; el artículo Por qué no timeouts fijos desarrolla ese punto.

La garantía de HotStuff está formulada exactamente en estos términos. [1]

Observa que el teorema no dice cómo conseguir la ventana común. Esa es precisamente la tarea del Pacemaker.

Certificados de timeout en DiemBFT

DiemBFT, el descendiente de HotStuff diseñado para producción, hace explícita la sincronización. [2] Su Pacemaker avanza de ronda por dos caminos: al ver un QC de la ronda actual o al ver un certificado de timeout (TC) de esa ronda. Las réplicas que llegan tarde no necesitan recorrer los temporizadores de las rondas intermedias; les basta un certificado verificable para saltar.

Cuando vence el temporizador local, la réplica deja de votar en esa ronda, firma un mensaje de timeout que incluye la ronda y su QC más alto, y lo difunde a todas las réplicas. [2] Con $2f + 1$ mensajes de timeout para la misma ronda se forma el TC. La aritmética es la de siempre: cualquier conjunto de $2f + 1$ firmas entre $3f + 1$ réplicas contiene al menos $f + 1$ réplicas correctas, de modo que el TC no puede fabricarlo un grupo bizantino por sí solo.

Que la réplica deje de votar al emitir el timeout importa para safety. Si una ronda acaba con un TC, ninguna réplica correcta del TC votará después en esa ronda, así que nadie puede usar sus votos tardíos para completar un QC que contradiga lo que el TC reporta. El líder de la ronda siguiente incluye el TC en su propuesta cuando no tiene un QC de la ronda anterior, y las réplicas aceptan esa propuesta solo si extiende un QC al menos tan alto como el mayor $\operatorname{highQC}$ reportado en el TC. [2]

Figura 1

Alineación de vistas con un certificado de timeout

Fuentes:

[1][2]

Cómo leer esta figura

El diagrama de carril muestra dos réplicas que agotan el tiempo de la vista 9 y una tercera rezagada en la vista 8. Los timeouts de la vista 9 forman un certificado de 2f + 1 firmas (TC de la vista 9). Al recibirlo, las tres réplicas entran en la vista 10, incluida la rezagada, que se pone al día al verificar el certificado. Es un esquema simplificado del mecanismo de DiemBFT.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Qué compra el TC y cuánto cuesta

El TC resuelve dos problemas a la vez. Primero, sincroniza: una prueba transferible permite que cualquier réplica, incluso una que no vio los mensajes originales, entre en la ronda correcta. Segundo, transporta información de safety: los $\operatorname{highQC}$ incluidos le dicen al siguiente líder sobre qué debe construir y le dan a cada réplica una forma de comprobarlo.

El precio es la comunicación. Difundir timeouts a todas las réplicas, cada uno con su certificado, cuesta un número de mensajes cuadrático en el peor caso. Jolteon asume ese coste a propósito: mantiene el camino normal lineal, como HotStuff, y usa un cambio de vista cuadrático con TCs para confirmar con una cadena de dos QCs en lugar de tres. [3] La idea es que los cambios de vista son raros en buen clima, así que pagar más en ellos para ahorrar una fase en cada bloque es buen negocio. La línea de DiemBFT v4 adopta ese mismo intercambio. [2] [3]

Hay un matiz que conviene no perder. El TC no hace que el sistema avance por sí solo; solo saca a las réplicas de una ronda sin futuro y las junta en la siguiente. El progreso real sigue necesitando un líder correcto y una red que, después de GST, entregue mensajes a tiempo. [1] Por eso la reputación de líderes de DiemBFT, que intenta evitar dar turno a réplicas que no han estado participando, complementa al Pacemaker en lugar de reemplazarlo. [2]

Siguiente lectura

Para ver cómo el Pacemaker encaja con las propiedades formales del protocolo, continúa con Safety, liveness y responsiveness en HotStuff. Si te interesa el diseño de producción que adoptó los certificados de timeout, sigue con DiemBFT, Jolteon y Ditto.