💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes é um protocolo BFT de líder rotativo de dois turnos para $n=5f+1$ processos que elimina paradas de latência de cauda causadas por líderes lentos ou que falharam ao utilizar consenso de prefixo para finalizar o prefixo comum mais pesado de quaisquer $n-f$ votos, garantindo assim o progresso mesmo quando as visualizações expiram.

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

Publicado 2026-07-29

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um grupo de amigos tentando decidir qual filme assistir, mas eles estão espalhados pelo mundo, alguns têm internet instável e alguns amigos travessos estão tentando sabotar a decisão enviando links falsos ou fingindo estar offline. Este é o mundo do consenso de Tolerância a Falhas Bizantinas (BFT). Na ciência da computação, é assim que uma rede de computadores entra em acordo sobre uma verdade única — como a ordem das transações em um blockchain — sem confiar em um único chefe central. O objetivo é chegar a um acordo rapidamente (baixa latência), mesmo quando alguns computadores travam ou agem de forma maliciosa.

Por anos, esses sistemas dependeram de um "líder" para propor o próximo passo. Se o líder for rápido e honesto, todos concordam rapidamente. Mas se o líder for lento ou travar, todo o grupo tem que esperar um temporizador acabar, desistir desse líder e escolher um novo. Isso cria um dilema doloroso: defina o temporizador longo e você esperará para sempre por um líder quebrado; defina-o curto e você perderá tempo abandonando líderes que estavam apenas um pouco lentos. Este "dilema do timeout" é o gargalo que atrasa a extremidade final do sistema, fazendo com que as solicitações mais lentas demorem uma eternidade para terminar.

Este artigo apresenta o Hermes, um novo protocolo projetado para resolver esse problema específico. Em vez de desistir quando um líder é lento, o Hermes permite que o grupo termine o trabalho sobre o qual eles podem concordar, mesmo que o líder falhe. Ele transforma um timeout desperdiçado em uma decisão produtiva, garantindo que, não importa o que aconteça, o sistema continue avançando sem perder o progresso que já realizou.

O Problema: A "Armadilha do Timeout"

Imagine uma corrida de revezamento onde o capitão da equipe (o líder) deve entregar o bastão para o próximo corredor. Se o capitão for rápido, a corrida corre suavemente. Mas se o capitão tropeçar ou derrubar o bastão, toda a equipe tem que parar e esperar pelo apito de um árbitro (o timeout) antes de poderem escolher um novo capitão e recomeçar.

Nos sistemas tradicionais, este apito é uma aposta. Se o árbitro apitar cedo demais, eles podem interromper um capitão que estava apenas correndo um pouco devagar, mas que conseguiria completar o percurso. Se esperarem demais, a equipe fica ociosa por eras enquanto um capitão quebrado tenta se recuperar. De qualquer forma, o tempo gasto esperando é "tempo morto" — nenhum progresso é feito e a corrida fica estagnada. Este é o problema da "latência de cauda": os piores cenários arrastam todo o sistema para baixo.

A Solução: Hermes e o "Terreno Comum"

O Hermes muda as regras do jogo. Em vez de tratar um líder lento como uma falha total, o Hermes trata o acordo parcial do grupo como uma vitória.

Veja como funciona com uma analogia criativa: Imagine que a equipe está tentando construir uma torre longa de blocos.

O Jeito Antigo: O líder coloca um bloco. Todos esperam. Se o líder parar, a equipe espera o timeout, então joga fora a torre inteira e começa a construir uma nova com um novo líder.
O Jeito Hermes: O líder começa a colocar blocos, mas todos também começam a colocar seus próprios blocos simultaneamente. Se o líder for rápido, a equipe constrói a torre do líder perfeitamente. Se o líder travar, a equipe não joga a torre fora. Em vez disso, eles olham para todos os blocos que todos colocaram, encontram a seção mais longa onde todos concordam com a ordem dos blocos e declaram que essa seção está "finalizada".

Esta é a inovação central: Consenso de Prefixo. Nos tempos antigos, se duas pessoas votassem em torres ligeiramente diferentes, seus votos eram considerados uma discordância e descartados. O Hermes diz: "Espere, eles concordam com os 90% inferiores da torre! Vamos travar isso e seguir em frente."

Como o Hermes Funciona: A Dança de Duas Rodadas

O Hermes opera em "views" (visões/rodadas), cada uma com um líder designado. Ele utiliza uma dança inteligente de dois passos:

Rodada 1 (A Proposta): Todos transmitem sua própria ideia de como deve ser a próxima parte da torre. A ideia do líder é apenas uma entre muitas.
Rodada 2 (O Voto):
- Se o líder for rápido: Todos veem a proposta do líder, concordam e votam nela. A torre cresce com o bloco total do líder em apenas dois atrasos de mensagem (2δ).
- Se o líder for lento ou travar: O temporizador acaba. Em vez de votar para "cancelar" a rodada, todos votam no melhor acordo possível que conseguirem encontrar entre as propostas que receberam. Eles procuram pelo "Prefixo Comum Mais Pesado" (Heaviest Common Prefix - HCP) — a sequência mais longa de blocos que todos concordam, mesmo que suas propostas tenham divergido no final.

Isso significa que, mesmo que o líder falhe, o grupo não perde a visão. Eles finalizam a parte comum da torre e iniciam imediatamente a próxima rodada. O caminho do "timeout", que antes era um beco sem saída, agora produz um resultado.

A Magia dos "Prefixos" e "Skips"

Para fazer isso funcionar com múltiplas faixas de dados (como uma rodovia com muitas faixas de tráfego), o Hermes usa uma codificação especial chamada parent-relative delta tipcuts.

Pense nisso como um livro de "Escolha sua Própria Aventura", onde cada página faz referência à anterior. Se uma faixa de tráfego estiver faltando um carro (um bloco), o Hermes não diz "erro". Ele marca explicitamente aquele lugar como "pulado" (skipped) e avança para o próximo carro. Isso permite que o sistema compare diferentes propostas mesmo que lhes faltem peças diferentes. É como comparar duas histórias: mesmo que uma história pule um parágrafo e a outra o inclua, elas ainda podem concordar com o início e o fim, e o sistema trava esse acordo.

Os Resultados: Velocidade e Segurança

O artigo prova matematicamente que o Hermes é seguro (duas pessoas honestas nunca discordarão da parte finalizada) e vivo (o sistema sempre continuará se movendo).

O Caso Bom: Se o líder for honesto e rápido, o Hermes é tão rápido quanto os melhores sistemas existentes, finalizando em 2δ (dois atrasos de mensagem).
O Caso Ruim: Se o líder for lento ou travar, o Hermes finaliza o acordo comum em 2∆ + δ (onde ∆ é o timeout e δ é o atraso da rede). Crucialmente, isso é mais rápido do que o modo antigo de esperar por uma mudança completa de visão, porque pula o tempo "desperdiçado" de descartar a visão.

Os autores mostram que, ao usar erasure coding (uma forma de quebrar dados em pedaços para que possam ser reconstruídos mesmo se algumas partes forem perdidas), o Hermes mantém os custos de comunicação baixos, mesmo lidando com muitas faixas de dados.

Por Que Isso Importa

O Hermes resolve o "dilema do timeout" ao tornar o próprio timeout algo produtivo. Ele transforma um momento de falha em um momento de progresso. Em vez de perguntar, "O líder conseguiu chegar?" e esperar para ver, o Hermes pergunta: "No que todos nós concordamos?" e segue em frente.

Para um adolescente curioso, pense nisso como um grupo de chat onde todos estão tentando concordar com um plano. Se a pessoa que costuma sugerir o plano travar, o jeito antigo é esperar que ela responda ou iniciar um novo chat com um novo líder. O Hermes é como dizer: "Ok, eles não responderam, mas olhem todas as ideias que enviamos. Todos concordamos com os três primeiros passos. Vamos travar esses e começar a planejar o quarto passo." É uma maneira mais inteligente e resiliente de manter o grupo em movimento, não importa quem deixe a peteca cair.

Resumo Técnico: Hermes: Baixa Latência de Cauda Via Consenso de Prefixo

1. Declaração do Problema

Protocolos de Tolerância a Falhas Bizantinas (BFT) baseados em líder tipicamente finalizam transações apenas quando um líder designado é oportuno. Se um líder falha ou está lento, a visão deve ser terminada via um timeout, resultando em uma visão "desperdiçada" onde nenhum progresso é feito. Isso cria um compromisso fundamental na configuração de timeouts:

Timeouts conservadores: Toleram líderes lentos, mas convertem cada líder que falhou em um longo atraso.
Timeouts agressivos: Pulam líderes que falharam rapidamente, mas invalidam as visões de líderes que estão apenas lentos (uma ocorrência comum em sistemas geo-distribuídos).

Em ambos os casos, a visão expirada é desperdiçada, e a requisição deve esperar por uma mudança de visão e pela próxima rodada do próximo líder para ser finalizada. Esse compromisso, em vez do desempenho do "caso ideal", governa a latência de cauda do sistema. Além disso, arquiteturas modernas frequentemente separam a disseminação de dados (ex: DAGs, designs baseados em faixas/lanes) da ordenação de consenso. Nesses cenários, as propostas são prefixos de um fluxo, e propostas honestas dentro de uma visão frequentemente diferem apenas no sufixo devido ao jitter da rede. Protocolos existentes descartam esses votos não correspondentes como desacordos, falhando em utilizar o prefixo comum que compartilham.

2. Metodologia

Hermes é um protocolo de líder rotativo de duas rodadas projetado para $n = 5f + 1$ processos sob sincronia parcial. Ele introduz o Consenso de Prefixo, um mecanismo onde os votos carregam valores ordenados por uma relação de prefixo ( $\preceq$ ), e os quóruns exigem comparabilidade em vez de igualdade.

Mecanismos Principais

Estrutura de Duas Rodadas:
1. Rodada 1 (Proposta): Cada processo transmite uma proposta justificada. A proposta do líder de round-robin é uma entre $n$ .
2. Rodada 2 (Votação): Cada processo emite um único voto.
  - Se a proposta do líder for entregue oportunamente, os processos votam nela.
  - Se um timeout ( $2\Delta$ ) decorrer e $n-f$ propostas válidas forem recebidas, os processos votam em uma proposta de fallback selecionada a partir do conjunto disponível.
- Crucialmente, não há votos de nulificação (nullify votes).
Definições de Quórum:
- M-notarização: Um conjunto de $2f+1$ votos pairwise comparáveis. Isso permite que a visão avance para a próxima visão.
- L-notarização: Um conjunto de $n-f = 4f+1$ votos válidos (que não precisam ser idênticos). Este conjunto finaliza o Maior Prefixo Comum (HCP - Heaviest Common Prefix) dos votos.
Tratamento de Timeouts:
Em vez de invalidar uma visão quando o líder está lento, o Hermes utiliza o caminho do timeout para finalizar o HCP dos $n-f$ votos coletados. Um timeout agressivo agora custa apenas o sufixo onde os votos divergem, não a visão inteira. O HCP é finalizado em $2\Delta + \delta$ .
Instanciações do Espaço de Valores:
O protocolo é instanciado sobre um espaço de prefixo abstrato e aplicado a dois cenários específicos:
1. Faixa Única (Gadget de Finalidade): Sobre uma cadeia dinamicamente disponível (ex: Ethereum). Os valores são pontas (tips) da cadeia; a relação de prefixo é ancestralidade.
2. Múltiplas Faixas (Estilo Autobahn): Ordena faixas de dados concorrentes. Isso introduz três desafios específicos abordados por:
  - Intercalação Determinística: Uma ordem global para posições de faixas.
  - Delta Tipcuts Relativos ao Pai: Uma representação compacta usando identificadores de pai e marcadores de salto explícitos para lidar com velocidades heterogêneas de faixas sem transmitir valores completos.
  - Amplificação por Código de Erasura Indexada pelo Remetente: Para garantir a disponibilidade sem inflar a complexidade de comunicação para $O(n^3 \hat{m})$ , as propostas são amplificadas via códigos de erasura. As justificativas carregam identificadores, e os fragmentos são reconstruídos sob demanda.

3. Principais Contribuições

Protocolo Hermes: Um protocolo de líder rotativo de duas rodadas em $n=5f+1$ $n = 5 f + 1$ sem caminho de nulificação.
- Caso Ideal: Finalização em $2\delta$ sob um líder honesto oportuno.
- Caso Ruim: Finalização do HCP de quaisquer $n-f$ votos em $2\Delta + \delta$ .
- Segurança e Vivacidade (Liveness): Provadas sobre um espaço de valor de prefixo abstrato.
Instanciação de Faixa Única: Um gadget de finalidade para cadeias disponíveis onde os valores são pontas de cadeia.
Instanciação de Múltiplas Faixas: Um design para faixas estilo Autobahn apresentando:
- Intercalação determinística.
- Delta tipcuts relativos ao pai com certificação de salto explícita.
- Amplificação por código de erasura indexada pelo remetente.
- Complexidade: $O(n^2 \hat{m} + \lambda n^3)$ bits e $O(n^2)$ mensagens por visão (onde $\hat{m}$ é o número de faixas e $\lambda$ é o parâmetro de segurança).
Implementação e Avaliação: O artigo inclui uma implementação e avaliação (Seção 8), embora resultados numéricos específicos estejam marcados como "Adicionar resultados" no texto fornecido.

4. Resultados e Desempenho

Latência:
- Líder Oportuno: Finaliza em $2\delta$ .
- Líder Lento/Falho: Finaliza o HCP em $2\Delta + \delta$ . Isso é uma melhoria significativa em relação aos protocolos tradicionais onde um líder lento resulta em uma mudança de visão completa e uma rodada subsequente de $2\delta$ , totalizando $2\Delta + 3\delta$ ou mais antes da primeira finalização.
Comunicação:
- No cenário de múltiplas faixas com amplificação, o protocolo evita a complexidade quártica ( $O(n^3 \hat{m})$ ) associada ao encaminhamento de valores completos.
- O caso ideal mantém $O(n^2)$ mensagens. Sob falhas, a complexidade de mensagens pode subir para $O(n^3)$ devido ao tráfego de amplificação, mas a complexidade de bits permanece controlada.
Latência de Cauda: Ao tornar o caminho do timeout produtivo, o Hermes elimina a penalidade de "visão desperdiçada". Uma requisição que cai em uma visão ruim paga o timeout e a finalização do HCP, em vez de esperar por um ciclo completo de mudança de visão.

5. Significância

O artigo afirma que o Hermes altera fundamentalmente o compromisso entre responsividade (quão rápido uma visão muda) e estabilidade (quantas mudanças de visão produzem progresso).

Timeouts Produtivos: Ao contrário de designs anteriores onde um timeout implica uma visão invalidada, o Hermes garante que mesmo uma visão com um líder falho finalize um prefixo útil do fluxo de dados.
Compatibilidade com Arquiteturas Modernas: Ele preenche a lacuna entre camadas de disseminação de dados disponíveis (como DAGs ou sistemas baseados em faixas) e o consenso, permitindo que o gadget de finalidade ordene blocos que já foram propagados, mas que podem ter divergido ligeiramente na camada de disseminação.
Otimalidade: O Hermes atinge o limite teórico de $2\delta$ para o caso ideal enquanto resolve o problema da latência de cauda que persiste no BFT baseado em líder, sem exigir um protocolo de recuperação separado ou mecanismos de corrida.

O artigo posiciona o Hermes como o único protocolo em sua classe onde a própria visão de um líder falho se finaliza, contrastando com protocolos como o Minimmit (que anula tais visões) e o Raptr (que usa votação de prefixo para disponibilidade, mas dentro da proposta de um único líder).