💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes ist ein zweiründiges, rotierendes Leader-BFT-Protokoll für $n=5f+1$ Prozesse, das durch die Nutzung von Präfix-Konsens zur Finalisierung des schwersten gemeinsamen Präfixes aus beliebigen $n-f$ Stimmen Latenzspitzen durch langsame oder abgestürzte Leader eliminiert und dadurch den Fortschritt auch dann sicherstellt, wenn Views ablaufen.

Ursprüngliche Autoren: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Veröffentlicht 2026-07-29

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Gruppe von Freunden vor, die versuchen, einen Film auszusuchen, aber sie sind über die ganze Welt verstreut, einige haben eine instabile Internetverbindung und ein paar intrigante Freunde versuchen, die Entscheidung zu sabotieren, indem sie gefälschte Links senden oder so tun, als wären sie offline. Dies ist die Welt des Byzantine Fault Tolerant (BFT) Konsens. In der Informatik ist dies die Art und Weise, wie ein Netzwerk von Computern einer einzigen Wahrheit zustimmt – wie etwa der Reihenfolge von Transaktionen in einer Blockchain – ohne einen einzelnen zentralen Chef zu benötigen. Das Ziel ist es, schnell eine Einigung zu erzielen (geringe Latenz), selbst wenn einige Computer abstürzen oder bösartig agieren.

Jahrelang verließen sich diese Systeme auf einen „Leader“ (Leiter), der den nächsten Schritt vorschlägt. Wenn der Leader schnell und ehrlich ist, stimmt die Gruppe schnell überein. Aber wenn der Leader langsam ist oder abstürzt, muss die ganze Gruppe warten, bis ein Timer abläuft, den Leader aufgibt und einen neuen wählt. Dies erzeugt ein schmerzhaftes Dilemma: Setzt man den Timer lang an, wartet man ewig auf einen defekten Leader; setzt man ihn kurz an, verschwendet man Zeit damit, Leader aufzuge-geben, die nur ein wenig langsam waren. Dieses „Timeout-Dilemma“ ist der Flaschenhals, der das Ende des Systems verlangsamt und dafür sorgt, dass die langsamsten Anfragen ewig brauchen, um abgeschlossen zu werden.

Dieses Paper stellt Hermes vor, ein neues Protokoll, das genau dieses Problem lösen soll. Anstatt aufzugeben, wenn ein Leader langsam ist, lässt Hermes die Gruppe die Arbeit abschließen, die sie konnte, selbst wenn der Leader ausfällt. Es verwandelt ein verschwendetes Timeout in eine produktive Entscheidung und stellt sicher, dass das System, egal was passiert, vorankommt, ohne den bereits gemachten Fortschritt zu verlieren.

Das Problem: Die „Timeout-Falle“

Stellen Sie sich ein Staffettenrennen vor, bei dem der Kapitän des Teams (der Leader) den Stab an den nächsten Läufer übergeben soll. Wenn der Kapitän schnell ist, läuft das Rennen reibungslos. Aber wenn der Kapitän stolpert oder den Stab fallen lässt, muss das ganze Team warten, bis ein Schiedsrichter die Pfeife ertönen lässt (das Timeout), bevor sie einen neuen Kapitän wählen und von vorne beginnen können.

In traditionellen Systemen ist diese Pfeife ein Glücksspiel. Wenn der Schiedsrichter zu früh pfeift, unterbricht er vielleicht einen Kapitän, der nur etwas langsam lief, aber durchgekommen wäre. Wenn sie zu lange warten, sitzt das Team ewig untätig herum, während ein kaputter Kapitän versucht, sich zu erholen. In beiden Fällen ist die gewonnene Zeit „tote Zeit“ – es wird kein Fortschritt gemacht und das Rennen stockt. Dies ist das „Tail-Latency“-Problem: Die extremsten Szenarien ziehen das gesamte System nach unten.

Die Lösung: Hermes und der „Gemeinsame Nenner“

Hermes ändert die Regeln des Spiels. Anstatt einen langsamen Leader als Totalausfall zu betrachten, betrachtet Hermes die Teilzustimmung der Gruppe als einen Sieg.

So funktioniert es mit einer kreativen Analogie: Stellen Sie sich vor, das Team versucht, einen langen Turm aus Blöcken zu bauen.

Der alte Weg: Der Leader platziert einen Block. Alle warten. Wenn der Leader stoppt, wartet das Team auf das Timeout, wirft dann den ganzen Turm weg und beginnt mit einem neuen Leader einen neuen Aufbau.
Der Hermes-Weg: Der Leader beginnt, Blöcke zu platzieren, aber jeder beginnt gleichzeitig, auch seine eigenen Blöcke zu platzieren. Wenn der Leader schnell ist, baut das Team den Turm des Leaders perfekt auf. Wenn der Leader stecken bleibt, wirft das Team den Turm nicht weg. Stattdessen schauen sie sich alle Blöcke an, die alle platziert haben, finden den längsten Abschnitt, in dem alle über die Reihenfolge der Blöcke übereinstimmen, und erklären diesen Abschnitt für „abgeschlossen“.

Dies ist die zentrale Innovation: Prefix-Konsens. In der Vergangenheit wurden die Stimmen als Uneinigkeit gewertet und verworfen, wenn zwei Personen leicht unterschiedliche Türme stimmten. Hermes sagt: „Warten Sie, sie stimmen bei den unteren 90 % des Turms überein! Lassen Sie uns diesen Teil festlegen und weitermachen.“

Wie Hermes funktioniert: Der Zwei-Runden-Tanz

Hermes operiert in „Views“ (Ansichten/Runden), wobei jede Runde einen designierten Leader hat. Es nutzt einen klugen Zwei-Schritte-Tanz:

Runde 1 (Der Vorschlag): Jeder sendet seine eigene Idee darüber aus, wie der nächste Teil des Turms aussehen sollte. Die Idee des Leaders ist dabei nur eine von vielen.
Runde 2 (Die Abstimmung):
- Wenn der Leader schnell ist: Jeder sieht den Vorschlag des Leaders, stimmt ihm zu und stimmt dafür ab. Der Turm wächst um den vollen Block des Leaders in nur zwei Nachrichtenverzögerungen (2δ).
- Wenn der Leader langsam ist oder abstürzt: Die Zeit läuft ab. Anstatt abzustimmen, um die Runde zu „abbrechen“, stimmen alle für die bestmögliche Übereinstimmung, die sie unter den erhaltenen Vorschlägen finden können. Sie suchen nach dem „Heaviest Common Prefix“ (HCP) – der längsten Sequenz von Blöcken, über die sich alle einig sind, selbst wenn ihre Vorschläge am Ende divergieren.

Das bedeutet, dass die Gruppe selbst dann die View nicht verliert, wenn der Leader ausfällt. Sie finalisieren den gemeinsamen Teil des Turms und beginnen sofort mit der nächsten Runde. Der „Timeout“-Pfad, der früher ein Sackgasse war, liefert nun ein Ergebnis.

Die Magie von „Präfixen“ und „Skips“

Um dies mit mehreren Datenbahnen (wie einer Autobahn mit vielen Fahrspuren) zu ermöglichen, verwendet Hermes eine spezielle Kodierung namens parent-relative delta tipcuts.

Denken Sie an ein „Choose Your Own Adventure“-Buch, in dem jede Seite auf die vorherige Bezug nimmt. Wenn einer Fahrspur ein Auto (ein Block) fehlt, sagt Hermes nicht „Fehler“. Es markiert diese Stelle explizit als „übersprungen“ (skipped) und bewegt sich zum nächsten Auto. Dies ermöglicht es dem System, verschiedene Vorschläge zu vergleichen, selbst wenn ihnen unterschiedliche Teile fehlen. Es ist wie der Vergleich zweier Geschichten: Selbst wenn eine Geschichte einen Absatz überspringt und die andere ihn enthält, können sie sich immer noch über den Anfang und das Ende einig sein, und das System verankert diese Übereinstimmung.

Die Ergebnisse: Geschwindigkeit und Sicherheit

Das Paper beweist mathematisch, dass Hermes sicher (keine zwei ehrlichen Teilnehmer werden jemals über den finalisierten Teil uneins sein) und lebendig (das System wird immer in Bewegung bleiben) ist.

Der gute Fall: Wenn der Leader ehrlich und schnell ist, ist Hermes genauso schnell wie die besten bestehenden Systeme und finalisiert in 2δ (zwei Nachrichtenverzögerungen).
Der schlechte Fall: Wenn der Leader langsam ist oder abstürzt, finalisiert Hermes die gemeinsame Übereinstimmung in 2∆ + δ (wobei ∆ das Timeout und δ die Netzwerkverzögerung ist). Entscheidend ist, dass dies schneller ist als der alte Weg, bei dem man auf einen vollständigen View-Wechsel warten musste, da es die „verschwendete“ Zeit des Verwerfens der View vermeidet.

Die Autoren zeigen, dass Hermes durch die Verwendung von Erasure Coding (einer Methode, Daten in Teile zu zerlegen, sodass sie rekonstruiert werden können, selbst wenn einige Teile verloren gehen) die Kommunikationskosten niedrig hält, selbst wenn mit vielen Datenbahnen gearbeitet wird.

Warum das wichtig ist

Hermes löst das „Timeout-Dilemma“, indem es das Timeout selbst produktiv macht. Es verwandelt einen Moment des Scheiterns in einen Moment des Fortschritts. Anstatt zu fragen: „Hat der Leader es geschafft?“ und abzuwarten, fragt Hermes: „Worüber sind wir uns alle einig?“ und macht weiter.

Für einen neugierigen Teenager gedacht: Es ist wie ein Gruppenchat, in dem alle versuchen, einen Plan zu vereinbaren. Wenn die Person, die normalerweise den Plan vorschlägt, nicht antwortet, ist der alte Weg, auf sie zu warten oder einen neuen Chat mit einem neuen Leiter zu beginnen. Hermes ist wie zu sagen: „Okay, sie hat nicht geantwortet, aber schaut euch mal an, welche Ideen wir gesendet haben. Wir sind uns über die ersten drei Schritte einig. Lass uns die festlegen und mit der Planung für Schritt vier beginnen.“ Es ist eine intelligentere, resilientere Art, die Gruppe in Bewegung zu halten, egal wer den Ball fallen lässt.

Technisches Resümee: Hermes: Niedrige Tail-Latenz durch Präfix-Konsens

1. Problemstellung

Leader-basierte Byzantine Fault Tolerant (BFT) Protokolle finalisieren Transaktionen typischerweise erst dann, wenn ein designierter Leader zeitgerecht agiert. Wenn ein Leader abstürzt oder langsam ist, muss die View via Timeout terminiert werden, was zu einer „verschwendeten“ View führt, in der keine Fortschritte erzielt werden. Dies erzeugt einen fundamentalen Trade-off bei der Konfiguration von Timeouts:

Konservative Timeouts: Tolerieren langsame Leader, verwandeln aber jeden abgestürzten Leader in eine lange Verzögerung.
Aggressive Timeouts: Überspringen abgestürzte Leader schnell, entwerten jedoch die Views von Leadern, die lediglich langsam sind (ein häufiges Vorkommnis in geo-verteilten Systemen).

In beiden Fällen ist die abgelaufene View verschwendet, und die Anfrage muss auf einen View Change und den nächsten Round-Trip des Leaders warten, um zu finalisieren. Dieser Trade-off, statt der Performance im „Good Case“, bestimmt die Tail-Latenz des Systems. Darüber hinaus trennen moderne Architekturen oft die Datenverbreitung (z. B. DAGs, Lane-basierte Designs) von der Konsens-Ordnung. In diesen Settings sind Proposals Präfixe eines Streams, und ehrliche Proposals innerhalb einer View unterscheiden sich oft nur im Suffix aufgrund von Netzwerk-Jitter. Bestehende Protokolle verwerfen diese nicht übereinstimmenden Stimmen als Disagreements und versäumen es so, das gemeinsame Präfix zu nutzen, das sie teilen.

2. Methodik

Hermes ist ein Zwei-Runden-Rotating-Leader-Protokoll, das für $n = 5f + 1$ Prozesse unter partieller Synchronität entwickelt wurde. Es führt den Präfix-Konsens ein, einen Mechanismus, bei dem Stimmen Werte tragen, die durch eine Präfix-Relation ( $\preceq$ ) geordnet sind, und Quoren Vergleichbarkeit statt Gleichheit erfordern.

Kernmechanismen

Zwei-Runden-Struktur:
1. Runde 1 (Proposal): Jeder Prozess broadcastet ein gerechtfertigtes Proposal. Das Round-Robin-Leader-Proposal ist eines unter $n$ .
2. Runde 2 (Voting): Jeder Prozess gibt eine einzelne Stimme ab.
  - Wenn das Leader-Proposal zeitgerecht geliefert wird, stimmen die Prozesse für dieses.
  - Wenn ein Timeout ( $2\Delta$ ) abläuft und $n-f$ valide Proposals empfangen wurden, stimmen die Prozesse für ein Fallback-Proposal, das aus dem verfügbaren Set ausgewählt wurde.
- Entscheidend ist: Es gibt keine Nullify-Votes.
Quorum-Definitionen:
- M-Notarisierung: Eine Menge von $2f+1$ paarweise vergleichbaren Stimmen. Dies ermöglicht den Übergang zur nächsten View.
- L-Notarisierung: Eine Menge von $n-f = 4f+1$ validen Stimmen (die nicht identisch sein müssen). Diese Menge finalisiert das Heaviest Common Prefix (HCP) der Stimmen.
Umgang mit Timeouts:
Anstatt eine View zu entwerten, wenn der Leader langsam ist, nutzt Hermes den Timeout-Pfad, um das HCP der $n-f$ Stimmen zu finalisieren. Ein aggressiver Timeout kostet nun nur das Suffix, in dem die Stimmen divergieren, nicht die gesamte View. Das HCP wird bei $2\Delta + \delta$ finalisiert.
Instanziierungen des Werte-Raums:
Das Protokoll wird über einen abstrakten präfix-geordneten Raum instanziiert und auf zwei spezifische Szenarien angewendet:
1. Single-Lane (Finality Gadget): Über eine dynamisch verfügbare Chain (z. B. Ethereum). Die Werte sind Chain-Tips; die Präfix-Relation ist die Ancestry.
2. Multi-Lane (Autobahn-Stil): Ordnet konkurrierende Daten-Lanes. Dies führt drei spezifische Herausforderungen ein, die adressiert werden:
  - Deterministische Interleaving: Eine globale Ordnung für Lane-Positionen.
  - Parent-Relative Delta Tipcuts: Eine kompakte Repräsentation mittels Parent-Identifikatoren und expliziter Skip-Marker, um heterogene Lane-Geschwindigkeiten ohne Übertragung voller Werte zu handhaben.
  - Sender-Indexierte Erasure-Coded Amplifikation: Um Verfügbarkeit zu gewährleisten, ohne die Kommunikationskomplexität auf $O(n^3 \hat{m})$ aufzublähen, werden Proposals via Erasure Codes amplifiziert. Justifications tragen Identifikatoren, und Fragmente werden bei Bedarf rekonstruiert.

3. Wesentliche Beiträge

Hermes-Protokoll: Ein Zwei-Runden-Rotating-Leader-Protokoll bei $n=5f+1$ $n = 5 f + 1$ ohne Nullification-Pfad.
- Good Case: $2\delta$ Finalisierung unter einem zeitgerechten ehrlichen Leader.
- Bad Case: Finalisierung des HCP von beliebigen $n-f$ Stimmen bei $2\Delta + \delta$ .
- Sicherheit & Liveness: Bewiesen über einen abstrakten Präfix-Werte-Raum.
Single-Lane Instanziierung: Ein Finality Gadget für verfügbare Chains, bei denen die Werte Chain-Tips sind.
Multi-Lane Instanziierung: Ein Design für Autobahn-Stil Lanes mit:
- Deterministischem Interleaving.
- Parent-relativen Delta Tipcuts mit expliziter Skip-Zertifizierung.
- Sender-indexierter Erasure-Coded Amplifikation.
- Komplexität: $O(n^2 \hat{m} + \lambda n^3)$ Bits und $O(n^2)$ Nachrichten pro View (wobei $\hat{m}$ die Anzahl der Lanes und $\lambda$ der Sicherheitsparameter ist).
Implementierung und Evaluierung: Das Paper enthält eine Implementierung und Evaluierung (Abschnitt 8), wobei spezifische numerische Ergebnisse im bereitgestellten Text als „Add results“ markiert sind.

4. Ergebnisse und Performance

Latenz:
- Timely Leader: Finalisiert in $2\delta$ .
- Slow/Crashed Leader: Finalisiert das HCP in $2\Delta + \delta$ . Dies ist eine signifikante Verbesserung gegenüber traditionellen Protokollen, bei denen ein langsamer Leader zu einem vollständigen View Change und einem anschließenden $2\delta$ Round führt, was insgesamt $2\Delta + 3\delta$ oder mehr vor der ersten Finalisierung bedeutet.
Kommunikation:
- Im Multi-Lane-Setting mit Amplifikation vermeidet das Protokoll die quartische Komplexität ( $O(n^3 \hat{m})$ ), die mit dem Weiterleiten voller Werte verbunden ist.
- Der Good Case behält eine $O(n^2)$ Nachrichtenkomplexität bei. Unter Fehlern kann die Nachrichtenkomplexität aufgrund von Amplifikations-Traffic auf $O(n^3)$ ansteigen, aber die Bit-Komplexität bleibt kontrolliert.
Tail-Latenz: Durch die Produktivierung des Timeout-Pfads eliminiert Hermes die „Wasted View“-Strafe. Eine Anfrage, die in einer schlechten View landet, zahlt den Timeout und die HCP-Finalisierung, anstatt auf einen vollständigen View-Change-Zyklus zu warten.

5. Bedeutung

Das Paper behauptet, dass Hermes den Trade-off zwischen Responsivität (wie schnell eine View wechselt) und Stabilität (wie viele View Changes Fortschritt erzeugen) grundlegend verändert.

Produktive Timeouts: Im Gegensatz zu bisherigen Designs, bei denen ein Timeout eine entwertete View impliziert, stellt Hermes sicher, dass selbst eine View mit einem fehlgeschlagenen Leader ein nützliches Präfix des Datenstroms finalisiert.
Kompatibilität mit modernen Architekturen: Es schließt die Lücke zwischen verfügbaren Datenverbreitungsschichten (wie DAGs oder Lane-basierten Systemen) und dem Konsens, indem es als Finality Gadget fungiert, das Blöcke ordnet, die bereits propagiert wurden, sich aber in der Dissemination-Layer leicht unterscheiden können.
Optimalität: Hermes erreicht die theoretische Untergrenze von $2\delta$ für den Good Case und löst gleichzeitig das Tail-Latenz-Problem, das in Leader-basierten BFT-Systemen bestanden hat, ohne einen separaten Recovery-Protokoll oder Racing-Mechanismen zu benötigen.

Das Paper positioniert Hermes als das einzige Protokoll seiner Klasse, bei dem die View eines fehlgeschlagenen Leaders selbst finalisiert, im Gegensatz zu Protokollen wie Minimmit (welches solche Views nullifiziert) oder Raptr (welches Präfix-Voting für die Verfügbarkeit nutzt, jedoch innerhalb eines einzelnen Leader-Proposals).