💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes is a two-round rotating-leader BFT protocol for $n=5f+1$ processes that eliminates tail-latency stalls caused by slow or crashed leaders by utilizing prefix consensus to finalize the heaviest common prefix from any $n-f$ votes, thereby ensuring progress even when views expire.

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

Published 2026-07-29

📖 7 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to decide on a movie to watch, but they are scattered across the world, some have spotty internet, and a few mischievous friends are trying to sabotage the decision by sending fake links or pretending to be offline. This is the world of Byzantine Fault Tolerant (BFT) consensus. In computer science, this is how a network of computers agrees on a single truth—like the order of transactions in a blockchain—without trusting a single central boss. The goal is to reach an agreement quickly (low latency) even when some computers crash or act maliciously.

For years, these systems have relied on a "leader" to propose the next step. If the leader is fast and honest, everyone agrees quickly. But if the leader is slow or crashes, the whole group has to wait for a timer to run out, give up on that leader, and pick a new one. This creates a painful trade-off: set the timer long, and you wait forever for a broken leader; set it short, and you waste time abandoning leaders who were just a little slow. This "timeout dilemma" is the bottleneck that slows down the tail end of the system, making the slowest requests take forever to finish.

This paper introduces Hermes, a new protocol designed to solve this specific headache. Instead of giving up when a leader is slow, Hermes lets the group finish the work they can agree on, even if the leader fails. It turns a wasted timeout into a productive decision, ensuring that no matter what happens, the system keeps moving forward without losing the progress it has already made.

The Problem: The "Timeout Trap"

Imagine a relay race where the team captain (the leader) is supposed to hand the baton to the next runner. If the captain is fast, the race goes smoothly. But if the captain trips or drops the baton, the whole team has to stop and wait for a referee's whistle (the timeout) before they can pick a new captain and start over.

In traditional systems, this whistle is a gamble. If the referee blows it too early, they might stop a captain who was just running a bit slow but would have made it. If they wait too long, the team sits idle for ages while a broken captain tries to recover. Either way, the time spent waiting is "dead time"—no progress is made, and the race is stalled. This is the "tail latency" problem: the worst-case scenarios drag the whole system down.

The Solution: Hermes and the "Common Ground"

Hermes changes the rules of the game. Instead of treating a slow leader as a total failure, Hermes treats the group's partial agreement as a victory.

Here is how it works with a creative analogy: Imagine the team is trying to build a long tower out of blocks.

The Old Way: The leader places a block. Everyone waits. If the leader stops, the team waits for the timeout, then throws away the whole tower and starts building a new one with a new leader.
The Hermes Way: The leader starts placing blocks, but everyone also starts placing their own blocks simultaneously. If the leader is fast, the team builds the leader's tower perfectly. If the leader gets stuck, the team doesn't throw the tower away. Instead, they look at all the blocks everyone placed, find the longest section where everyone agrees on the order of the blocks, and declare that section "finished."

This is the core innovation: Prefix Consensus. In the old days, if two people voted for slightly different towers, their votes were considered a disagreement and discarded. Hermes says, "Wait, they agree on the bottom 90% of the tower! Let's lock that in and move on."

How Hermes Works: The Two-Round Dance

Hermes operates in "views" (rounds), each with a designated leader. It uses a clever two-step dance:

Round 1 (The Proposal): Everyone broadcasts their own idea of what the next part of the tower should look like. The leader's idea is just one of many.
Round 2 (The Vote):
- If the leader is fast: Everyone sees the leader's proposal, agrees, and votes for it. The tower grows by the full leader's block in just two message delays (2δ).
- If the leader is slow or crashes: The timer runs out. Instead of voting to "cancel" the round, everyone votes for the best possible agreement they can find among the proposals they received. They look for the "Heaviest Common Prefix" (HCP)—the longest sequence of blocks that everyone agrees on, even if their proposals diverged at the very end.

This means that even if the leader fails, the group doesn't lose the view. They finalize the common part of the tower and immediately start the next round. The "timeout" path, which used to be a dead end, now produces a result.

The Magic of "Prefixes" and "Skips"

To make this work with multiple lanes of data (like a highway with many lanes of traffic), Hermes uses a special encoding called parent-relative delta tipcuts.

Think of it like a "Choose Your Own Adventure" book where every page references the previous one. If a lane of traffic is missing a car (a block), Hermes doesn't say "error." It explicitly marks that spot as "skipped" and moves to the next car. This allows the system to compare different proposals even if they are missing different pieces. It's like comparing two stories: even if one story skips a paragraph and the other includes it, they can still agree on the beginning and the end, and the system locks in that agreement.

The Results: Speed and Safety

The paper proves mathematically that Hermes is safe (no two honest people will ever disagree on the finalized part) and live (the system will always keep moving).

The Good Case: If the leader is honest and fast, Hermes is just as fast as the best existing systems, finalizing in 2δ (two message delays).
The Bad Case: If the leader is slow or crashes, Hermes finalizes the common agreement in 2∆ + δ (where ∆ is the timeout and δ is the network delay). Crucially, this is faster than the old way of waiting for a full view change, because it skips the "wasted" time of discarding the view.

The authors show that by using erasure coding (a way of breaking data into pieces so it can be reconstructed even if some pieces are lost), Hermes keeps the communication costs low, even when dealing with many lanes of data.

Why This Matters

Hermes solves the "timeout dilemma" by making the timeout itself productive. It turns a moment of failure into a moment of progress. Instead of asking, "Did the leader make it?" and waiting to see, Hermes asks, "What did we all agree on?" and moves forward.

For a curious teenager, think of it like a group chat where everyone is trying to agree on a plan. If the person who usually suggests the plan gets stuck, the old way is to wait for them to reply or start a new chat with a new leader. Hermes is like saying, "Okay, they didn't reply, but look at all the ideas we sent. We all agree on the first three steps. Let's lock those in and start planning step four." It's a smarter, more resilient way to keep the group moving, no matter who drops the ball.

Technical Summary: Hermes: Low Tail-Latency Via Prefix Consensus

1. Problem Statement

Leader-based Byzantine Fault Tolerant (BFT) protocols typically finalize transactions only when a designated leader is timely. If a leader crashes or is slow, the view must be terminated via a timeout, resulting in a "wasted" view where no progress is made. This creates a fundamental trade-off in timeout configuration:

Conservative timeouts: Tolerate slow leaders but convert every crashed leader into a long stall.
Aggressive timeouts: Skip crashed leaders quickly but void the views of leaders that are merely slow (a common occurrence in geo-distributed systems).

In both cases, the expired view is wasted, and the request must wait for a view change and the next leader's round trip to finalize. This trade-off, rather than the "good case" performance, governs the tail latency of the system. Furthermore, modern architectures often separate data dissemination (e.g., DAGs, lane-based designs) from consensus ordering. In these settings, proposals are prefixes of a stream, and honest proposals within a view often differ only in the suffix due to network jitter. Existing protocols discard these non-matching votes as disagreements, failing to utilize the common prefix they share.

2. Methodology

Hermes is a two-round rotating-leader protocol designed for $n = 5f + 1$ processes under partial synchrony. It introduces Prefix Consensus, a mechanism where votes carry values ordered by a prefix relation ( $\preceq$ ), and quorums require comparability rather than equality.

Core Mechanisms

Two-Round Structure:
1. Round 1 (Proposal): Every process broadcasts a justified proposal. The round-robin leader's proposal is one among $n$ .
2. Round 2 (Voting): Every process casts a single vote.
  - If the leader's proposal is delivered timely, processes vote for it.
  - If a timeout ( $2\Delta$ ) elapses and $n-f$ valid proposals are received, processes vote for a fallback proposal selected from the available set.
- Crucially, there are no nullify votes.
Quorum Definitions:
- M-notarization: A set of $2f+1$ pairwise comparable votes. This allows the view to advance to the next view.
- L-notarization: A set of $n-f = 4f+1$ valid votes (which need not be identical). This set finalizes the Heaviest Common Prefix (HCP) of the votes.
Handling Timeouts:
Instead of voiding a view when the leader is slow, Hermes utilizes the timeout path to finalize the HCP of the $n-f$ votes collected. An aggressive timeout now costs only the suffix where votes disagree, not the entire view. The HCP is finalized at $2\Delta + \delta$ .
Value Space Instantiations:
The protocol is instantiated over an abstract prefix-ordered space and applied to two specific scenarios:
1. Single-Lane (Finality Gadget): Over a dynamically available chain (e.g., Ethereum). Values are chain tips; the prefix relation is ancestry.
2. Multi-Lane (Autobahn-style): Orders concurrent lanes of data. This introduces three specific challenges addressed by:
  - Deterministic Interleaving: A global order for lane positions.
  - Parent-Relative Delta Tipcuts: A compact representation using parent identifiers and explicit skip markers to handle heterogeneous lane speeds without transmitting full values.
  - Sender-Indexed Erasure-Coded Amplification: To ensure availability without inflating communication complexity to $O(n^3 \hat{m})$ , proposals are amplified via erasure codes. Justifications carry identifiers, and fragments are reconstructed on demand.

3. Key Contributions

Hermes Protocol: A two-round rotating-leader protocol at $n=5f+1$ $n = 5 f + 1$ with no nullification path.
- Good Case: $2\delta$ finalization under a timely honest leader.
- Bad Case: Finalization of the HCP of any $n-f$ votes at $2\Delta + \delta$ .
- Safety & Liveness: Proven over an abstract prefix value space.
Single-Lane Instantiation: A finality gadget for available chains where values are chain tips.
Multi-Lane Instantiation: A design for Autobahn-style lanes featuring:
- Deterministic interleaving.
- Parent-relative delta tipcuts with explicit skip certification.
- Sender-indexed erasure-coded amplification.
- Complexity: $O(n^2 \hat{m} + \lambda n^3)$ bits and $O(n^2)$ messages per view (where $\hat{m}$ is the number of lanes and $\lambda$ is the security parameter).
Implementation and Evaluation: The paper includes an implementation and evaluation (Section 8), though specific numerical results are marked as "Add results" in the provided text.

4. Results and Performance

Latency:
- Timely Leader: Finalizes in $2\delta$ .
- Slow/Crashed Leader: Finalizes the HCP in $2\Delta + \delta$ . This is a significant improvement over traditional protocols where a slow leader results in a full view change and a subsequent $2\delta$ round, totaling $2\Delta + 3\delta$ or more before the first finalization.
Communication:
- In the multi-lane setting with amplification, the protocol avoids the quartic complexity ( $O(n^3 \hat{m})$ ) associated with forwarding full values.
- The good case maintains $O(n^2)$ messages. Under faults, message complexity may rise to $O(n^3)$ due to amplification traffic, but bit complexity remains controlled.
Tail Latency: By making the timeout path productive, Hermes eliminates the "wasted view" penalty. A request landing in a bad view pays the timeout and the HCP finalization, rather than waiting for a full view change cycle.

5. Significance

The paper claims that Hermes fundamentally alters the trade-off between responsiveness (how fast a view changes) and stability (how many view changes produce progress).

Productive Timeouts: Unlike previous designs where a timeout implies a voided view, Hermes ensures that even a view with a failed leader finalizes a useful prefix of the data stream.
Compatibility with Modern Architectures: It bridges the gap between available data dissemination layers (like DAGs or lane-based systems) and consensus, allowing the finality gadget to order blocks that have already been propagated but may have diverged slightly in the dissemination layer.
Optimality: Hermes achieves the theoretical lower bound of $2\delta$ for the good case while solving the tail-latency problem that has persisted in leader-based BFT, without requiring a separate recovery protocol or racing mechanisms.

The paper positions Hermes as the only protocol in its class where the view of a failed leader itself finalizes, contrasting it with protocols like Minimmit (which nullifies such views) and Raptr (which uses prefix voting for availability but within a single leader's proposal).