💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes es un protocolo BFT de líder rotativo de dos rondas para $n=5f+1$ procesos que elimina las paradas de latencia de cola causadas por líderes lentos o caídos al utilizar el consenso de prefijo para finalizar el prefijo común más pesado de cualquier conjunto de $n-f$ votos, asegurando así el progreso incluso cuando las vistas expiran.

Autores originales: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Publicado 2026-07-29

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina a un grupo de amigos tratando de decidir qué película ver, pero están esparcidos por todo el mundo, algunos tienen un internet inestable y algunos amigos traviesos intentan sabotear la decisión enviando enlaces falsos o fingiendo estar desconectados. Este es el mundo del consenso de Tolerancia a Fallas Bizantinas (BFT). En la informática, así es como una red de computadoras llega a un acuerdo sobre una única verdad —como el orden de las transacciones en una cadena de bloques— sin confiar en un único jefe central. El objetivo es alcanzar un acuerdo rápidamente (baja latencia) incluso cuando algunas computadoras fallan o actúan de forma maliciosa.

Durante años, estos sistemas han dependido de un "líder" para proponer el siguiente paso. Si el líder es rápido y honesto, todos acuerdan rápidamente. Pero si el líder es lento o falla, todo el grupo tiene que esperar a que un temporizador se agote, darse por vencido con ese líder y elegir uno nuevo. Esto crea un intercambio doloroso: establece el temporizador largo y esperas una eternidad por un líder roto; establece el temporizador corto y pierdes tiempo abandonando líderes que solo estaban un poco lentos. Este "dilema del tiempo de espera" es el cuello de botella que ralentiza la cola del sistema, haciendo que las solicitudes más lentas tarden una eternidad en terminarse.

Este artículo presenta Hermes, un nuevo protocolo diseñado para resolver este dolor de cabeza específico. En lugar de rendirse cuando un líder es lento, Hermes permite que el grupo termine el trabajo en el que pueden ponerse de acuerdo, incluso si el líder falla. Convierte un tiempo de espera desperdiciado en una decisión productiva, asegurando que, pase lo que pase, el sistema siga avanzando sin perder el progreso que ya ha realizado.

El Problema: La "Trampa del Tiempo de Espera"

Imagina una carrera de relevos donde el capitán del equipo (el líder) debe entregar el testigo al siguiente corredor. Si el capitán es rápido, la carrera transcurre sin problemas. Pero si el capitán tropieza o suelta el testigo, todo el equipo tiene que detenerse y esperar a que un árbitro toque el silbato (el tiempo de espera) antes de poder elegir un nuevo capitán y comenzar de nuevo.

En los sistemas tradicionales, este silbato es una apuesta. Si el árbitro lo toca demasiado pronto, podrían detener a un capitán que solo iba un poco lento pero que habría llegado. Si esperan demasiado, el equipo se queda inactivo durante siglos mientras un capitán averiado intenta recuperarse. De cualquier manera, el tiempo pasado esperando es "tiempo muerto": no se hace ningún progreso y la carrera se detiene. Este es el problema de la "latencia de cola": los peores escenarios arrastran a todo el sistema.

La Solución: Hermes y el "Terreno Común"

Hermes cambia las reglas del juego. En lugar de tratar a un líder lento como un fallo total, Hermes trata el acuerdo parcial del grupo como una victoria.

Así es como funciona con una analogía creativa: Imagina que el equipo está intentando construir una torre larga con bloques.

La vieja forma: El líder coloca un bloque. Todos esperan. Si el líder se detiene, el equipo espera al tiempo de espera, luego tira toda la torre y comienza a construir una nueva con un nuevo líder.
La forma de Hermes: El líder comienza a colocar bloques, pero todos también comienzan a colocar sus propios bloques simultáneamente. Si el líder es rápido, el equipo construye la torre del líder perfectamente. Si el líder se queda trabado, el equipo no tira la torre. En su lugar, miran todos los bloques que todos colocaron, encuentran la sección más larga en la que todos están de acuerdo sobre el orden de los bloques, y declaran que esa sección está "terminada".

Esta es la innovación central: Consenso de Prefijo. En los viejos tiempos, si dos personas votaban por torres ligeramente diferentes, sus votos se consideraban un desacuerdo y se descartaban. Hermes dice: "¡Espera, están de acuerdo en el 90% inferior de la torre! Aseguremos eso y sigamos adelante".

Cómo funciona Hermes: La Danza de Dos Rondas

Hermes opera en "vistas" (rondas), cada una con un líder designado. Utiliza una hábil danza de dos pasos:

Ronda 1 (La Propuesta): Todos transmiten su propia idea de cómo debería verse la siguiente parte de la torre. La idea del líder es solo una de muchas.
Ronda 2 (La Votación):
- Si el líder es rápido: Todos ven la propuesta del líder, están de acuerdo y votan por ella. La torre crece por el bloque completo del líder en solo dos retrasos de mensajes (2δ).
- Si el líder es lento o falla: El temporizador se agota. En lugar de votar para "cancelar" la ronda, todos votan por el mejor acuerdo posible que puedan encontrar entre las propuestas que recibieron. Buscan el "Prefijo Común más Pesado" (HCP, por sus siglas en inglés)—la secuencia más larga de bloques en la que todos están de acuerdo, incluso si sus propuestas divergieron al final.

Esto significa que, incluso si el líder falla, el grupo no pierde la vista. Finalizan la parte común de la torre e inmediatamente comienzan la siguiente ronda. El "tiempo de espera", que antes era un callejón sin salida, ahora produce un resultado.

La Magia de los "Prefijos" y los "Saltos"

Para que esto funcione con múltiples carriles de datos (como una autopista con muchos carriles de tráfico), Hermes utiliza una codificación especial llamada tipcuts relativos al padre (parent-relative delta tipcuts).

Piensa en ello como un libro de "Elige tu propia aventura" donde cada página hace referencia a la anterior. Si un carril de tráfico pierde un coche (un bloque), Hermes no dice "error". Marca explícitamente ese lugar como "saltado" y pasa al siguiente coche. Esto permite que el sistema compare diferentes propuestas incluso si les faltan piezas distintas. Es como comparar dos historias: incluso si una historia salta un párrafo y la otra lo incluye, aún pueden estar de acuerdo en el principio y el final, y el sistema asegura ese acuerdo.

Los Resultados: Velocidad y Seguridad

El artículo demuestra matemáticamente que Hermes es seguro (ninguna dos personas honestas estarán nunca en desacuerdo sobre la parte finalizada) y vivo (el sistema siempre seguirá avanzando).

El Caso Bueno: Si el líder es honesto y rápido, Hermes es tan rápido como los mejores sistemas existentes, finalizando en 2δ (dos retrasos de mensajes).
El Caso Malo: Si el líder es lento o falla, Hermes finaliza el acuerdo común en 2∆ + δ (donde ∆ es el tiempo de espera y δ es el retraso de la red). Crucialmente, esto es más rápido que la forma antigua de esperar un cambio de vista completo, porque evita el tiempo "perdido" de descartar la vista.

Los autores muestran que, al usar codificación de borrado (erasure coding) (una forma de dividir los datos en piezas para que puedan reconstruirse incluso si algunas piezas se pierden), Hermes mantiene bajos los costos de comunicación, incluso cuando se trata de muchos carriles de datos.

Por qué esto importa

Hermes resuelve el "dilema del tiempo de espera" haciendo que el tiempo de espera sea productivo por sí mismo. Convierte un momento de fallo en un momento de progreso. En lugar de preguntar "¿Llegó el líder?" y esperar para ver, Hermes pregunta "¿En qué estamos todos de acuerdo?" y sigue adelante.

Para un adolescente curioso, piensa en ello como un chat grupal donde todos intentan ponerse de acuerdo en un plan. Si la persona que suele sugerir el plan se queda trabada, la forma antigua es esperar a que responda o iniciar un nuevo chat con un nuevo líder. Hermes es como decir: "Está bien, no respondió, pero miren todas las ideas que enviamos. Estamos de acuerdo en los primeros tres pasos. Aseguremos eso y empecemos a planificar el paso cuatro". Es una forma más inteligente y resiliente de mantener al grupo avanzando, sin importar quién suelte la pelota.

Resumen Técnico: Hermes: Baja Latencia de Cola mediante Consenso de Prefijos

1. Planteamiento del Problema

Los protocolos de Tolerancia a Fallos Bizantinos (BFT) basados en líderes típicamente finalizan las transacciones solo cuando un líder designado actúa oportunamente. Si un líder falla o es lento, la vista debe terminarse mediante un tiempo de espera (timeout), lo que resulta en una vista "desperdiciada" donde no se produce progreso. Esto crea un compromiso fundamental en la configuración de los tiempos de espera:

Tiemos de espera conservadores: Toleran líderes lentos pero convierten cada fallo de líder en una larga detención.
Tiemos de espera agresivos: Saltan rápidamente a los líderes fallidos pero invalidan las vistas de líderes que simplemente son lentos (un suceso común en sistemas geo-distribuidos).

En ambos casos, la vista expirada se desperdicia y la solicitud debe esperar a un cambio de vista y al siguiente viaje de ida y vuelta (round trip) del líder para finalizar. Este compromiso, en lugar del rendimiento del "caso ideal", gobierna la latencia de cola del sistema. Además, las arquitecturas modernas a menudo separan la diseminación de datos (por ejemplo, DAGs, diseños basados en carriles) del ordenamiento de consenso. En estos entornos, las propuestas son prefijos de un flujo, y las propuestas honestas dentro de una vista a menudo difieren solo en el sufijo debido al jitter de la red. Los protocolos existentes descartan estos votos no coincidentes como desacuerdos, fallando al no utilizar el prefijo común que comparten.

2. Metodología

Hermes es un protocolo de dos rondas con rotación de líder diseñado para $n = 5f + 1$ procesos bajo parcial sincronía. Introduce el Consenso de Prefijos, un mecanismo donde los votos portan valores ordenados por una relación de prefijo ( $\preceq$ ), y los quórums requieren comparabilidad en lugar de igualdad.

Mecanismos Centrales

Estructura de Dos Rondas:
1. Ronda 1 (Propuesta): Cada proceso transmite una propuesta justificada. La propuesta del líder de rotación es una entre $n$ .
2. Ronda 2 (Votación): Cada proceso emite un único voto.
  - Si la propuesta del líder se entrega oportunamente, los procesos votan por ella.
  - Si transcurre un tiempo de espera ( $2\Delta$ ) y se reciben $n-f$ propuestas válidas, los procesos votan por una propuesta de respaldo seleccionada del conjunto disponible.
- Crucialmente, no existen votos de nulificación.
Definiciones de Quórum:
- Notarización M: Un conjunto de $2f+1$ votos mutuamente comparables. Esto permite que la vista avance a la siguiente vista.
- Notarización L: Un conjunto de $n-f = 4f+1$ votos válidos (que no necesitan ser idénticos). Este conjunto finaliza el Prefijo Común Más Pesado (HCP, por sus siglas en inglés) de los votos.
Gestión de Tiemos de Espera:
En lugar de invalidar una vista cuando el líder es lento, Hermes utiliza la ruta de tiempo de espera para finalizar el HCP de los $n-f$ votos recolectados. Un tiempo de espera agresivo ahora solo cuesta el sufijo donde los votos discrepan, no la vista completa. El HCP se finaliza en $2\Delta + \delta$ .
Instanciaciones del Espacio de Valores:
El protocolo se instancia sobre un espacio abstracto de orden de prefijo y se aplica a dos escenarios específicos:
1. Carril Único (Gadget de Finalidad): Sobre una cadena disponible dinámicamente (por ejemplo, Ethereum). Los valores son puntas de cadena; la relación de prefijo es la ascendencia.
2. Multi-Carril (Estilo Autobahn): Ordena carriles de datos concurrentes. Esto introduce tres desafíos específicos abordados por:
  - Entrelazado Determinista: Un orden global para las posiciones de los carriles.
  - Delta Tipcuts Relativos al Padre: Una representación compacta utilizando identificadores de padre y marcas de salto explícitas para manejar velocidades de carril heterogéneas sin transmitir valores completos.
  - Amplificación de Código de Erasura Indexada por Emisor: Para asegurar la disponibilidad sin inflar la complejidad de comunicación a $O(n^3 \hat{m})$ , las propuestas se amplifican mediante códigos de erasures. Las justificaciones portan identificadores y los fragmentos se reconstruyen bajo demanda.

3. Contribuciones Clave

Protocolo Hermes: Un protocolo de dos rondas con rotación de líder a $n=5f+1$ $n = 5 f + 1$ sin ruta de nulificación.
- Caso Ideal: Finalización en $2\delta$ bajo un líder honesto oportuno.
- Caso Malo: Finalización del HCP de cualquier $n-f$ votos en $2\Delta + \delta$ .
- Seguridad y Vitalidad: Probadas sobre un espacio de valor de prefijo abstracto.
Instanciación de Carril Único: Un gadget de finalidad para cadenas disponibles donde los valores son puntas de cadena.
Instanciación Multi-Carril: Un diseño para carriles tipo Autobahn que presenta:
- Entrelazado determinista.
- Delta tipcuts relativos al padre con certificación de salto explícita.
- Amplificación de código de erasures indexada por emisor.
- Complejidad: $O(n^2 \hat{m} + \lambda n^3)$ bits y $O(n^2)$ mensajes por vista (donde $\hat{m}$ es el número de carriles y $\lambda$ es el parámetro de seguridad).
Implementación y Evaluación: El artículo incluye una implementación y evaluación (Sección 8), aunque los resultados numéricos específicos están marcados como "Añadir resultados" en el texto proporcionado.

4. Resultados y Rendimiento

Latencia:
- Líder Oportuno: Finaliza en $2\delta$ .
- Líder Lento/Fallido: Finaliza el HCP en $2\Delta + \delta$ . Esto es una mejora significativa respecto a los protocolos tradicionales donde un líder lento resulta en un cambio de vista completo y un subsiguiente ciclo de $2\delta$ , totalizando $2\Delta + 3\delta$ o más antes de la primera finalización.
Comunicación:
- En el entorno de multi-carriles con amplificación, el protocolo evita la complejidad cuártica ( $O(n^3 \hat{m})$ ) asociada con el reenvío de valores completos.
- El caso ideal mantiene una complejidad de $O(n^2)$ mensajes. Bajo fallos, la complejidad de mensajes puede aumentar a $O(n^3)$ debido al tráfico de amplificación, pero la complejidad de bits permanece controlada.
Latencia de Cola: Al hacer que la ruta de tiempo de espera sea productiva, Hermes elimina la penalización de la "vista desperdiciada". Una solicitud que cae en una mala vista paga el tiempo de espera y la finalización del HCP, en lugar de esperar un ciclo completo de cambio de vista.

5. Significado

El artículo afirma que Hermes altera fundamentalmente el compromiso entre capacidad de respuesta (qué tan rápido cambia una vista) y estabilidad (cuántos cambios de vista producen progreso).

Tiemos de Espera Productivos: A diferencia de diseños anteriores donde un tiempo de espera implica una vista invalidada, Hermes asegura que incluso una vista con un líder fallido finalice un prefijo útil del flujo de datos.
Compatibilidad con Arquitecturas Modernas: Une la brecha entre las capas de diseminación de datos disponibles (como DAGs o sistemas basados en carriles) y el consenso, permitiendo que el gadget de finalidad ordene bloques que ya han sido propagados pero que pueden haber divergido ligeramente en la capa de diseminación.
Optimalidad: Hermes alcanza el límite teórico inferior de $2\delta$ para el caso ideal mientras resuelve el problema de la latencia de cola que ha persistido en el BFT basado en líderes, sin requerir un protocolo de recuperación separado o mecanismos de carrera.

El artículo posiciona a Hermes como el único protocolo en su clase donde la vista de un líder fallido misma se finaliza, contrastando con protocolos como Minimmit (que nulifica tales vistas) o Raptr (que usa votación de prefijos para la disponibilidad pero dentro de la propuesta de un único líder).