Autobahn: Seamless BFT — Lanes, f+1 Proofs of Availability, and Committing a Whole Backlog in One Cut

BFT consensus benchmarks are almost always run on the happy path: a fault-free, synchronous network where the leader never times out. That is exactly the regime partial synchrony says you cannot count on. Autobahn (Giridharan, Suri-Payer, Abraham, Alvisi, Crooks — SOSP '24, arXiv:2401.10369) starts from an uncomfortable observation: practical BFT protocols assume partial synchrony but are inefficient when deployments are actually partially synchronous. The interesting metric isn't steady-state throughput. It's what happens in the seconds after a disruption ends.

Blips and hangovers

The paper names the phenomenon. A blip is any event that temporarily interrupts progress — a leader crash, a transient partition, a burst of packet loss. A hangover is performance degradation that persists after the blip is over, i.e. after the network is behaving again.

View-based protocols (PBFT, HotStuff and descendants) have brutal hangovers. During a blip, client transactions keep arriving but nothing commits; when the view change finally lands, the new leader must push the entire accumulated backlog through the ordering path — proposing, disseminating, and certifying data it never sent. In the paper's experiments, vanilla HotStuff's hangover lasts 1.2–1.6× the blip duration beyond the blip itself; with a 5-second timeout that's up to ~7 extra seconds of degraded service after the network has healed.

DAG-based protocols (Narwhal/Bullshark, and the lineage leading to Mysticeti) fixed this by decoupling data dissemination from ordering — dissemination continues during consensus stalls, so there's no backlog to replay. But they pay for that resilience every single day: Bullshark's commit latency is ~10.5 message delays on average because ordering rides on top of the DAG's reliable-broadcast rounds, versus ~7 for HotStuff.

Autobahn's claim is that this is a false trade-off. The paper defines a protocol as seamless if (i) it experiences no protocol-induced hangovers, and (ii) it introduces no new mechanisms that themselves widen the window of vulnerability to blips (liveness timeouts excepted). The result is a protocol that matches Bullshark's throughput while cutting its latency roughly in half — and recovering from a 20-second partition in about one second.

Lanes: dissemination with f+1 votes, not 2f+1

Standard setup: n = 3f+1 replicas, at most f Byzantine, partial synchrony (safety always, liveness during synchronous intervals).

Every replica runs its own lane — an append-only chain of data proposals it disseminates at its own pace, independent of every other lane and of consensus. Each hop in the lane is a car (Certification of Available Request): a single propose-and-vote exchange.

lane_i:  P0 <- P1 <- P2 <- ...          # replica i's chain of proposals

car(P_k):
  replica_i  -> all:  Propose{ batch, hash(P_{k-1}), PoA(P_{k-1}) }
  replica_j  -> i:    Vote{ hash(P_k) }        # only if j already voted for P_{k-1}
  PoA(P_k) = f+1 matching votes

The load-bearing decision is the quorum size. A Proof of Availability (PoA) needs only f+1 matching votes — just enough to guarantee at least one correct replica stores the data and can serve it later. Compare DAG protocols, which use reliable broadcast (2f+1 = n−f votes) for every vertex because the DAG's structure doubles as the ordering substrate, so equivocation must be prevented at dissemination time. Autobahn's insight is that non-equivocation is not a data-layer property: a Byzantine replica can fork its lane, and the protocol simply doesn't care — consensus will later pick one branch and garbage-collect the rest. Availability is the only thing dissemination must guarantee.

Two consequences fall out of the small quorum:

1. Lanes progress through partitions. A lane needs only f+1 reachable replicas to keep certifying cars. In the paper's partial-partition experiment, Bullshark (needing 2f+1) could not advance its DAG at all, while Autobahn's lanes kept absorbing and certifying transactions for the full 20 seconds.
2. In-order voting makes certification transitive. A replica votes on car k only if it voted on car k−1. So a PoA for position k transitively proves availability of positions 0..k−1 — you never need per-proposal certificates for history.

That transitivity is what makes the consensus layer cheap.

Consensus on cuts: constant cost, arbitrary backlog

Consensus in Autobahn never touches transaction data. A leader proposes a cut: a vector of n certified lane tips, one per lane.

Cut = [ tip_0, tip_1, ..., tip_{n-1} ]     # tip_i = latest PoA-certified proposal in lane i

commit(Cut) => commit every proposal transitively referenced by each tip,
               in a deterministic order (e.g., round-robin across lanes)

Committing one cut commits everything behind the tips — because in-order voting already proved all of it is available. The cost of a consensus slot is independent of how much data sits behind the cut. This is the anti-hangover mechanism: after a blip, lanes have grown fat (dissemination never stopped), and the first successful slot commits the entire backlog in one shot. Replicas that missed data fetch it with one message exchange from any of the f+1 PoA signers — in parallel with consensus, off the timeout-critical path, so syncing stragglers can never trigger the next view change. That last property is condition (ii) of seamlessness: DAG protocols and batched HotStuff both put data sync on the critical voting path, which converts one blip into the next.

The agreement protocol itself is deliberately boring — slot-based linear PBFT, two phases (Prepare → PrepareQC from 2f+1 votes; Confirm → CommitQC), 5 message delays, with a fast path of 3: if the leader collects all n Prepare votes, it upgrades directly to a commit certificate. Slots run in parallel (slot s may start once the first Prepare for s−1 is seen, bounded to k in-flight slots), so consensus itself pipelines.

Two latency refinements matter in practice:

• Optimistic tips. Waiting for a tip's PoA before proposing it costs 3 extra message delays of inclusion latency. Leaders may instead reference uncertified tips from historically well-behaved lanes. End-to-end, a client transaction commits in 4 message delays on the fast path (6 otherwise) — versus ~7 for HotStuff and ~10.5 for Bullshark.
• Reliable inclusion. A cut always contains all n lanes, so a slow-but-correct replica's transactions are never censored by being "too slow for the DAG round" — a real fairness problem in round-based DAG protocols.

The numbers

On GCP (n=4, 512-byte transactions, intra-US regions): Autobahn sustains ~234K tx/s at 280 ms commit latency — the same throughput as Bullshark, which needs 592 ms (2.1×). Batched HotStuff manages 189K tx/s at 333 ms, but its throughput collapses as n grows (−41% at n=20) because the leader disseminates all data itself; vanilla HotStuff sits near 15K tx/s. Under a leader-failure blip, Autobahn resumes full-speed commits immediately at the first good view; under the 20-second partition it commits the whole backlog in one slot, with only ~1 s of bandwidth-bound residual — a hangover no protocol could avoid, because the bits genuinely have to move.

Why this matters beyond BFT

Strip away the Byzantine machinery and the design reads as a general systems pattern: decouple the availability quorum from the ordering quorum, and make ordering reference data by certified pointer, not by value. Raft-family systems rediscovered pieces of this (leader-decoupled log replication, witness replicas); Autobahn is the cleanest articulation I've seen of why the dissemination quorum can be minimal (f+1: one honest holder suffices) while the ordering quorum stays classical (2f+1: intersection for safety). The same asymmetry shows up in erasure-coded storage (write availability vs. metadata consensus) and in disaggregated shared logs.

The follow-on work suggests the framing stuck: Hermes (2026) builds prefix consensus over Autobahn-style multi-lane dissemination to attack leader-timeout tail latency, and AutoPilot applies RL to tune Autobahn's knobs at runtime. "Seamlessness" — judging a protocol by its worst minute, not its best — is the metric that deserves to travel.