💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes est un protocole BFT à deux tours avec un leader tournant pour $n=5f+1$ processus qui élimine les blocages de latence de queue causés par des leaders lents ou en panne en utilisant le consensus de préfixe pour finaliser le préfixe commun le plus lourd à partir de n'importe quels $n-f$ votes, assurant ainsi la progression même lorsque les vues expirent.

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

Publié 2026-07-29

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

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

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un groupe d'amis essayant de décider quel film regarder, mais ils sont dispersés à travers le monde, certains ont une connexion internet instable, et quelques amis malicieux tentent de saboter la décision en envoyant de faux liens ou en prétendant être hors ligne. C'est le monde du consensus Byzantine Fault Tolerant (BFT). En informatique, c'est ainsi qu'un réseau d'ordinateurs s'accorde sur une vérité unique — comme l'ordre des transactions dans une blockchain — sans faire confiance à un seul chef central. L'objectif est de parvenir à un accord rapidement (faible latence) même lorsque certains ordinateurs tombent en panne ou agissent de manière malveillante.

Pendant des années, ces systèmes se sont appuyés sur un « leader » pour proposer l'étape suivante. Si le leader est rapide et honnête, tout le monde se met d'accord rapidement. Mais si le leader est lent ou tombe en panne, tout le groupe doit attendre qu'un minuteur s'écoule, renoncer à ce leader et en choisir un nouveau. Cela crée un arbitrage douloureux : régler le minuteur sur une durée longue, et vous attendez éternellement un leader défaillant ; le régler court, et vous perdez du temps à abandonner des leaders qui étaient juste un peu lents. Ce « dilemme du timeout » est le goulot d'étranglement qui ralentit la fin de la file du système, faisant en sorte que les requêtes les plus lentes mettent une éternité à se terminer.

Ce document présente Hermes, un nouveau protocole conçu pour résoudre ce problème spécifique. Au lieu d'abandonner lorsqu'un leader est lent, Hermes permet au groupe de terminer le travail sur lequel ils peuvent s'accorder, même si le leader échoue. Il transforme un timeout gâché en une décision productive, garantissant que, peu importe ce qui arrive, le système continue d'avancer sans perdre le progrès déjà accompli.

Le Problème : Le « Piège du Timeout »

Imaginez une course de relais où le capitaine de l'équipe (le leader) est censé passer le témoin au coureur suivant. Si le capitaine est rapide, la course se déroule sans accroc. Mais si le capitaine trébuche ou fait tomber le témoin, toute l'équipe doit s'arrêter et attendre le coup de sifflet d'un arbitre (le timeout) avant de pouvoir choisir un nouveau capitaine et recommencer.

Dans les systèmes traditionnels, ce sifflet est un pari. Si l'arbitre siffle trop tôt, ils pourraient arrêter un capitaine qui était juste un peu lent mais qui aurait réussi. S'ils attendent trop longtemps, l'équipe reste inactive pendant des siècles pendant qu'un capitaine défectueux tente de se rétablir. Dans les deux cas, le temps passé à attendre est du « temps mort » — aucun progrès n'est fait, et la course est interrompue. C'est le problème de la « latence de queue » (tail latency) : les scénarios les plus défavorables tirent tout le système vers le bas.

La Solution : Hermes et le « Terrain d'Entente »

Hermes change les règles du jeu. Au lieu de traiter un leader lent comme un échec total, Hermes considère l'accord partiel du groupe comme une victoire.

Voici comment cela fonctionne avec une analogie créative : Imaginez que l'équipe essaie de construire une longue tour de blocs.

L'ancienne méthode : Le leader pose un bloc. Tout le monde attend. Si le leader s'arrête, l'équipe attend le timeout, puis jette toute la tour et commence à construire une nouvelle tour avec un nouveau leader.
La méthode Hermes : Le leader commence à poser des blocs, mais tout le monde commence aussi à poser ses propres blocs simultanément. Si le leader est rapide, l'équipe construit la tour du leader parfaitement. Si le leader est bloqué, l'équipe ne jette pas la tour. Au lieu de cela, ils regardent tous les blocs que chacun a posés, trouvent la plus longue section sur laquelle tout le monde est d'accord sur l'ordre des blocs, et déclarent cette section « terminée ».

C'est l'innovation centrale : le Consensus de Préfixe (Prefix Consensus). Autrefois, si deux personnes votaient pour des tours légèrement différentes, leurs votes étaient considérés comme un désaccord et rejetés. Hermes dit : « Attendez, ils sont d'accord sur les 90 % du bas de la tour ! Verrouillons cela et passons à la suite. »

Comment fonctionne Hermes : La Danse en Deux Temps

Hermes opère par « vues » (rounds), chacune ayant un leader désigné. Il utilise une danse astucieuse en deux étapes :

Round 1 (La Proposition) : Tout le monde diffuse sa propre idée de ce à quoi devrait ressembler la prochaine partie de la tour. L'idée du leader n'est qu'une parmi tant d'autres.
Round 2 (Le Vote) :
- Si le leader est rapide : Tout le monde voit la proposition du leader, est d'accord et vote pour elle. La tour grandit de la pleine unité du leader en seulement deux délais de messages (2δ).
- Si le leader est lent ou tombe en panne : Le minuteur s'écoule. Au lieu de voter pour « annuler » le tour, tout le monde vote pour le meilleur accord possible qu'ils peuvent trouver parmi les propositions reçues. Ils cherchent le « Préfixe Commun le plus Lourd » (Heaviest Common Prefix - HCP) — la plus longue séquence de blocs sur laquelle tout le monde est d'accord, même si leurs propositions ont divergé à la toute fin.

Cela signifie que même si le leader échoue, le groupe ne perd pas la vue. Ils finalisent la partie commune de la tour et commencent immédiatement le tour suivant. Le « timeout », qui était autrefois une impasse, produit désormais un résultat.

La Magie des « Préfixes » et des « Sauts »

Pour faire fonctionner cela avec plusieurs voies de données (comme une autoroute avec de nombreuses voies de circulation), Hermes utilise un codage spécial appelé parent-relative delta tipcuts.

Voyez cela comme un livre dont vous êtes le héros où chaque page fait référence à la précédente. Si une voie de circulation manque une voiture (un bloc), Hermes ne dit pas « erreur ». Il marque explicitement cet endroit comme « sauté » (skipped) et passe à la voiture suivante. Cela permet au système de comparer différentes propositions même s'il manque des morceaux à certaines d'entre elles. C'est comme comparer deux histoires : même si une histoire saute un paragraphe et que l'autre l'inclut, elles peuvent toujours s'accorder sur le début et la fin, et le système verrouille cet accord.

Les Résultats : Vitesse et Sécurité

Le document prouve mathématiquement que Hermes est sûr (deux personnes honnêtes ne seront jamais en désaccord sur la partie finalisée) et vivant (le système continue toujours d'avancer).

Le Cas Idéal : Si le leader est honnête et rapide, Hermes est aussi rapide que les meilleurs systèmes existants, finalisant en 2δ (deux délais de messages).
Le Mauvais Cas : Si le leader est lent ou tombe en panne, Hermes finalise l'accord commun en 2∆ + δ (où ∆ est le timeout et δ est le délai réseau). Crucialement, c'est plus rapide que l'ancienne méthode consistant à attendre un changement de vue complet, car cela évite le temps « perdu » à rejeter la vue.

Les auteurs démontrent qu'en utilisant le codage par effacement (erasure coding) (une façon de diviser les données en morceaux afin qu'elles puissent être reconstruites même si certains morceaux sont perdus), Hermes maintient des coûts de communication bas, même en traitant de nombreuses voies de données.

Pourquoi cela importe

Hermes résout le « dilemme du timeout » en rendant le timeout lui-même productif. Il transforme un moment d'échec en un moment de progrès. Au lieu de demander : « Est-ce que le leader a réussi ? » et d'attendre de voir, Hermes demande : « Sur quoi sommes-nous tous d'accord ? » et avance.

Pour un adolescent curieux, pensez à un groupe de discussion (chat) où tout le monde essaie de se mettre d'accord sur un plan. Si la personne qui propose habituellement le plan reste bloquée, l'ancienne méthode consiste à attendre sa réponse ou à créer une nouvelle discussion avec un nouveau leader. Hermes, c'est comme dire : « Bon, ils n'ont pas répondu, mais regardez toutes les idées que nous avons envoyées. Nous sommes tous d'accord sur les trois premières étapes. Verrouillons-les et commençons à planifier la quatrième étape. » C'est une façon plus intelligente et plus résiliente de faire avancer le groupe, peu importe qui lâche le ballon.

Résumé Technique : Hermes : Faible Latence de Queue via le Consensus de Préfixe

1. Énoncé du Problème

Les protocoles de tolérance aux pannes byzantines (BFT) basés sur un leader ne finalisent généralement les transactions que lorsqu'un leader désigné est opportun. Si un leader tombe en panne ou est lent, la vue doit être terminée via un délai d'expiration (timeout), ce qui entraîne une vue « gaspillée » où aucun progrès n'est réalisé. Cela crée un compromis fondamental dans la configuration des délais :

Délais conservateurs : Tolèrent les leaders lents mais transforment chaque crash de leader en un blocage prolongé.
Délais agressifs : Sautent rapidement les leaders en panne mais invalident les vues des leaders qui sont simplement lents (un cas fréquent dans les systèmes géodistribués).

Dans les deux cas, la vue expirée est perdue, et la requête doit attendre un changement de vue et le prochain aller-retour du leader pour être finalisée. Ce compromis, plutôt que la performance du « cas idéal », régit la latence de queue du système. De plus, les architectures modernes séparent souvent la dissémination des données (ex: DAG, conceptions par voies/lanes) de l'ordonnancement du consensus. Dans ces contextes, les propositions sont des préfixes d'un flux, et les propositions honnêtes au sein d'une même vue ne diffèrent souvent que par le suffixe en raison de la gigue réseau. Les protocoles existants rejettent ces votes non concordants comme étant des désaccords, échouant ainsi à utiliser le préfixe commun qu'ils partagent.

2. Méthodologie

Hermes est un protocole à deux tours avec rotation de leader, conçu pour $n = 5f + 1$ processus sous synchronie partielle. Il introduit le Consensus de Préfixe, un mécanisme où les votes transportent des valeurs ordonnées par une relation de préfixe ( $\preceq$ ), et où les quorums exigent la comparabilité plutôt que l'égalité.

Mécanismes Fondamentaux

Structure à deux tours :
1. Tour 1 (Proposition) : Chaque processus diffuse une proposition justifiée. La proposition du leader en rotation est l'une parmi $n$ .
2. Tour 2 (Vote) : Chaque processus émet un vote unique.
  - Si la proposition du leader est livrée à temps, les processus votent pour elle.
  - Si un délai d'expiration ( $2\Delta$ ) s'écoule et que $n-f$ propositions valides sont reçues, les processus votent pour une proposition de repli sélectionnée parmi l'ensemble disponible.
- Crucialement, il n'y a pas de votes de nullification.
Définitions de Quorum :
- M-notarisation : Un ensemble de $2f+1$ votes mutuellement comparables. Cela permet à la vue de progresser vers la vue suivante.
- L-notarisation : Un ensemble de $n-f = 4f+1$ votes valides (qui n'ont pas besoin d'être identiques). Cet ensemble finalise le Plus Long Préfixe Commun (HCP - Heaviest Common Prefix) des votes.
Gestion des Délais (Timeouts) :
Au lieu d'invalider une vue lorsqu'un leader est lent, Hermes utilise le chemin du délai d'expiration pour finaliser le HCP des $n-f$ votes collectés. Un délai agressif ne coûte désormais que le suffixe où les votes divergent, et non l'intégralité de la vue. Le HCP est finalisé à $2\Delta + \delta$ .
Instanciations de l'Espace de Valeurs :
Le protocole est instancié sur un espace abstrait ordonné par préfixe et appliqué à deux scénarios spécifiques :
1. Voie Unique (Gadget de Finalité) : Sur une chaîne dynamiquement disponible (ex: Ethereum). Les valeurs sont les sommets de la chaîne ; la relation de préfixe est l'ancêtre.
2. Voies Multiples (Style Autobahn) : Ordonne des voies de données concurrentes. Cela introduit trois défis spécifiques adressés par :
  - Entrelacement Déterministe : Un ordre global pour les positions des voies.
  - Delta Tipcuts Relatifs au Parent : Une représentation compacte utilisant des identifiants de parents et des marqueurs de saut explicites pour gérer les vitesses de voies hétérogènes sans transmettre de valeurs complètes.
  - Amplification par Code d'Erreur Indexée par l'Émetteur : Pour garantir la disponibilité sans gonfler la complexité de communication à $O(n^3 \hat{m})$ , les propositions sont amplifiées via des codes correcteurs d'erreurs. Les justifications transportent des identifiants, et les fragments sont reconstruits à la demande.

3. Contributions Clés

Protocole Hermes : Un protocole à deux tours avec rotation de leader à $n=5f+1$ $n = 5 f + 1$ sans chemin de nullification.
- Cas Idéal : Finalisation en $2\delta$ sous un leader honnête et opportun.
- Cas Dégradé : Finalisation du HCP de n'importe quels $n-f$ votes à $2\Delta + \delta$ .
- Sécurité et Vivacité : Prouvées sur un espace de valeur de préfixe abstrait.
Instanciation Voie Unique : Un gadget de finalité pour les chaînes disponibles où les valeurs sont les sommets de la chaîne.
Instanciation Voies Multiples : Une conception pour des voies de type Autobahn comprenant :
- Entrelacement déterministe.
- Delta tipcuts relatifs au parent avec certification de saut explicite.
- Amplification par code d'erreur indexée par l'émetteur.
- Complexité : $O(n^2 \hat{m} + \lambda n^3)$ bits et $O(n^2)$ messages par vue (où $\hat{m}$ est le nombre de voies et $\lambda$ le paramètre de sécurité).
Implémentation et Évaluation : Le papier inclut une implémentation et une évaluation (Section 8), bien que les résultats numériques spécifiques soient marqués comme "Ajouter les résultats" dans le texte fourni.

4. Résultats et Performance

Latence :
- Leader Opportun : Finalise en $2\delta$ .
- Leader Lent/En Panne : Finalise le HCP en $2\Delta + \delta$ . C'est une amélioration significative par rapport aux protocoles traditionnels où un leader lent entraîne un changement de vue complet et un cycle de $2\delta$ consécutif, totalisant $2\Delta + 3\delta$ ou plus avant la première finalisation.
Communication :
- Dans le cadre des voies multiples avec amplification, le protocole évite la complexité quartique ( $O(n^3 \hat{m})$ ) associée au transfert de valeurs complètes.
- Le cas idéal maintient une complexité de $O(n^2)$ messages. En cas de fautes, la complexité de messages peut monter à $O(n^3)$ en raison du trafic d'amplification, mais la complexité en bits reste maîtrisée.
Latence de Queue : En rendant le chemin du délai d'expiration productif, Hermes élimine la pénalité de la « vue gaspillée ». Une requête tombant dans une mauvaise vue paie le délai et la finalisation du HCP, plutôt que d'attendre un cycle complet de changement de vue.

5. Signification

Le papier affirme que Hermes modifie fondamentalement le compromis entre la réactivité (la vitesse à laquelle une vue change) et la stabilité (combien de changements de vue produisent un progrès).

Délais Productifs : Contrairement aux conceptions précédentes où un délai implique une vue invalidée, Hermes garantit que même une vue avec un leader défaillant finalise un préfixe utile du flux de données.
Compatibilité avec les Architectures Modernes : Il comble le fossé entre les couches de dissémination de données disponibles (comme les DAG ou les systèmes à voies) et le consensus, permettant au gadget de finalité d'ordonner des blocs qui ont déjà été propagés mais qui peuvent diverger légèrement dans la couche de dissémination.
Optimalité : Hermes atteint la borne théorique de $2\delta$ pour le cas idéal tout en résolvant le problème de la latence de queue qui persiste dans le BFT basé sur un leader, sans nécessiter de protocole de récupération séparé ou de mécanismes de course.

Le papier positionne Hermes comme le seul protocole de sa classe où la vue d'un leader défaillant se finalise elle-même, contrastant avec des protocoles comme Minimmit (qui annule de telles vues) ou Raptr (qui utilise le vote de préfixe pour la disponibilité mais au sein de la proposition d'un seul leader).