To keep a critical service running when machines fail, you replicate it across copies that all process requests in the same order — easy if failures are clean crashes (a majority of 2f+1 copies survives), but real failures can be arbitrary or malicious (a "Byzantine" copy that lies and tells different copies different things), and tolerating that classically costs 3f+1 copies and milliseconds of latency from rounds of signed voting; this paper (MPI-SWS and collaborators) builds uBFT, the first Byzantine-fault-tolerant replication to run at MICROSECOND latency with only 2f+1 copies, by leaning on a tiny trusted component — DISAGGREGATED MEMORY (remote memory written and read directly over the network with no remote CPU) whose single-writer hardware regions stop a Byzantine copy from telling two stories — plus a fast path that skips all cryptography in the common case (about 10 microseconds) and only falls back to signatures and the shared memory when something actually goes wrong, making it over 50x faster than the previous smallest-footprint BFT system.
The argument in one glance
-
Problem
Surviving arbitrary failures normally costs extra copies and lots of latency
To make a critical service reliable, you replicate it: run several identical copies that execute the same client requests in the same order, so if some copies fail, the others carry on. This is state machine replication (SMR). If copies can only CRASH — stop cleanly — a majority survives any minority failure, so 2f+1 copies tolerate f crashes, as in Paxos and Raft. But real failures are not always clean. A software bug, a bit-flip, or a security compromise can make a copy BYZANTINE: it behaves arbitrarily, even maliciously, and crucially it can tell DIFFERENT copies DIFFERENT things about the same request. Byzantine fault tolerance (BFT) guards against exactly this, and modern datacenter services — banking, trading, search — want it without giving up their microsecond-scale speed.
-
What people did
Run a classic Byzantine agreement protocol
The textbook answer is a protocol like PBFT: the copies exchange several rounds of cryptographically signed messages, vote on each request, and agree on a single order despite up to f of them lying. After enough matching signed votes, every honest copy is convinced it has the same value as the others, so the malicious copies cannot force a divergence. This is correct and well understood, and it underpins real Byzantine systems.
-
Why it fell short
Classic BFT is expensive on both copies and latency
Classic BFT pays on two axes. First, COPIES: it needs 3f+1, half again as many as crash tolerance. The reason is EQUIVOCATION — a Byzantine copy telling one thing to some copies and a contradictory thing to others for the same slot. To stay safe against that, the protocol's voting quorums must always intersect in at least one HONEST copy, and guaranteeing that overlap requires 3f+1 rather than 2f+1. Second, LATENCY: the multiple message rounds, the all-to-all communication, and a signature check at nearly every step add up to MILLISECONDS. That is fine for many systems but disastrous for a datacenter service whose own request latency is measured in microseconds — BFT would multiply its latency a thousandfold. Before this work, microsecond-scale BFT simply did not exist.
-
This paper's idea
Add a tiny trusted memory to stop lying, and skip crypto in the common case
This paper (MPI-SWS with collaborators — Aguilera, Ben-David, Guerraoui, and others) builds uBFT, the first microsecond-scale BFT, using only 2f+1 copies. The key is to prevent equivocation with a small, simple TRUSTED component rather than with extra copies: DISAGGREGATED MEMORY — remote memory that copies read and write directly over the network via RDMA, without involving the remote CPU. The hardware supports SINGLE-WRITER regions: one copy can write a region and all others can only read it. A Byzantine copy writes its statement into its OWN region, everyone reads it there, and because the memory faithfully stores just ONE value that the copy alone can write, the copy CANNOT tell two different stories. Preventing equivocation this way drops the requirement from 3f+1 to 2f+1 — the same count as crash tolerance — and the trusted component is minimal (it only stores data and enforces access control, unlike a full trusted enclave). For latency, uBFT uses a FAST PATH that in the common case runs with no signatures and no memory access at all — just quick RDMA messages, about 10 microseconds — and only falls back to signatures and the shared memory when a failure or network delay is actually detected. Its core primitive, Consistent Tail Broadcast, keeps only the most recent messages so the trusted memory stays under 1 MiB. uBFT is over 50x faster than the previous smallest-footprint BFT.
Why this problem is worth solving
Datacenters run the services that money and safety depend on, and those
services increasingly need BOTH strong fault tolerance AND microsecond
latency — a combination that Byzantine tolerance had never delivered.
Understanding what BFT is guarding against comes first. A
STATE MACHINE
REPLICATION (SMR) keeps a service alive through failures by running
several identical copies (replicas) that process the same requests in the
same order, so their states stay identical and any survivor can answer.
The question is what kind of failure the copies might suffer. In the CRASH
model, a faulty copy simply stops — it never sends wrong information — so a
majority is always trustworthy and 2f+1 copies tolerate f failures
(Paxos, Raft). In the BYZANTINE model, a faulty copy can do ANYTHING: it
can compute wrong answers, forge messages, collude, and — most damagingly
— EQUIVOCATE, sending contradictory statements to different copies about
the same request. Byzantine faults cover software bugs, hardware
corruption, and outright compromise, so tolerating them (BFT) is what you
need when a single arbitrary fault could otherwise corrupt the whole
replicated service
The specific reason it is costly, and the lever uBFT pulls, is the
equivocation problem. A
EQUIVOCATION is a Byzantine
copy telling different things to different peers for the same slot — for
example, telling half the copies that the next request is A and the other
half that it is B — which can split the replicas into two groups that
proceed with different histories. Classic BFT defeats this by sheer
redundancy: with 3f+1 total copies, any two voting quorums of size 2f+1
must overlap in at least f+1 copies, and since at most f are faulty, that
overlap always contains an honest copy that will not vote for two
conflicting values — so divergence is impossible. That extra f copies,
beyond the 2f+1 that crash tolerance needs, is the price of defending
against lying by counting alone. The alternative, which uBFT takes, is to
prevent equivocation DIRECTLY with a trusted mechanism: if there is a
tamper-proof place where each copy must record its statement and everyone
reads the same record, a copy cannot say two different things, and the
extra copies are no longer needed
What people did before, and where it broke
- Crash-fault SMR (Paxos, Raft, Mu). Tolerate f crashes with 2f+1 copies, and RDMA-based versions (Mu) reach microsecond latency. Fast and lean — but a single arbitrary fault (a bug, a bit-flip, a compromise) can corrupt them, because they assume copies never lie.
- Classic BFT (PBFT). Tolerate f Byzantine faults with 3f+1 copies and rounds of signed voting. Correct against arbitrary faults, but needs 50% more copies and runs in milliseconds — far too slow for a microsecond service.
- Trusted-hardware BFT (MinBFT with Intel SGX). Use a trusted counter in an SGX enclave to prevent equivocation, cutting copies to 2f+1. But SGX enclaves run arbitrary logic (a large, complex trusted base and a history of attacks), and entering the enclave is slow, so latency stays high (hundreds of microseconds).
- Consistent Broadcast primitives. Prevent equivocation in theory, but standard consistent broadcast must remember every message forever — unbounded memory — which is impractical.
- The gap. No system offered Byzantine tolerance with crash-tolerance’s copy count (2f+1), microsecond latency, a tiny trusted base, and bounded memory all at once. That is the gap uBFT closes.
How uBFT gets microsecond BFT with 2f+1 copies
Prevent lying with trusted memory, skip crypto in the common case, and bound the memory
-
The replication setup and BFT's cost
Replicas execute the same requests in the same order. Crash tolerance needs 2f+1 copies; Byzantine tolerance classically needs 3f+1 because a lying copy can equivocate, plus rounds of signed voting that cost milliseconds. The goal is Byzantine safety at crash-tolerance's copy count and microsecond latency.
-
Add a tiny trusted primitive: disaggregated memory new
uBFT introduces remote memory accessed directly over RDMA (no remote CPU) as a small, non-Byzantine trusted component. It only stores data and enforces access control — far simpler than a trusted enclave — and the memory nodes are themselves replicated for reliability and shared across applications.
-
Stop equivocation with single-writer regions new
The memory supports single-writer, multiple-reader regions: one copy writes a region, all others read it. A Byzantine copy must record its statement in its own region, where everyone reads the same value, so it cannot tell two different stories. This direct anti-equivocation drops the requirement from 3f+1 to 2f+1.
-
Run a fast path with no cryptography new
In the common case — synchronous network, all copies cooperating — uBFT skips signatures and memory access entirely: a broadcaster sends a best-effort LOCK, receivers commit and confirm with LOCKED, and once all commit to the same message it is delivered safely. This costs about 10 microseconds.
-
Fall back to the slow path only on failure new
When a failure or network delay is detected, uBFT switches to a safe slow path: broadcasters send SIGNED messages, receivers write them to their single-writer memory registers and cross-read all others, and a three-phase consensus (prepare, certify, commit) proceeds. Correct despite Byzantine faults, at higher latency.
-
Bound memory with Consistent Tail Broadcast new
Standard consistent broadcast needs unbounded memory. uBFT's Consistent Tail Broadcast guarantees delivery of only the most recent t messages (a tunable "tail" trading memory for latency), so the trusted disaggregated memory stays under 1 MiB per node while still preventing equivocation.
The idea
Replace redundancy with a small trusted primitive. The defining cost of Byzantine tolerance is the extra copies you buy to outvote liars — 3f+1 instead of 2f+1 — and uBFT’s central move is to buy an anti-lying mechanism instead of the extra copies. A tamper-proof, single-writer shared memory forces each copy to commit to one statement everyone reads, so equivocation is impossible and the redundancy that guarded against it is no longer needed. Crucially, that trusted component is kept MINIMAL: it only stores data and enforces access control, so it is small enough to actually be trustworthy, unlike a general trusted enclave that runs arbitrary logic and carries a large attack surface. This shrink-the- trusted-base, add-a-minimal-anchor discipline is one the site’s security pages return to — keeping the piece you must trust tiny and dumb so it can be made correct — and here it is what converts a 3f+1 protocol into a 2f+1 one without weakening the guarantee.
Optimize the common case and guard it with a correct fallback. Classic BFT pays for signatures and rounds on EVERY request, even though almost every request runs when the network is healthy and every copy is honest. uBFT splits into a fast path and a slow path: the common case runs with no cryptography and no shared-memory access at all, just quick RDMA messages, and only when a failure or delay is actually detected does it fall back to the expensive signed, memory-backed slow path. This optimize-the-common- case-with-a-safe-guard discipline is one the site rewards repeatedly — the approximate-query and adaptive-instrumentation pages run a cheap path and fall back to an exact one when a check fires, and the DRAM-defense page takes the cheap action in the common case and the costly one only on the rare trigger. The safety never depends on the fast path; the slow path is always correct, so the fast path is free to be aggressive.
Use the memory fabric directly, and remember only the tail. Two enablers make the microsecond target reachable. First, the trusted memory is reached by ONE-SIDED RDMA — the writer or reader touches the remote memory without waking the remote CPU — the same bypass-the-CPU, talk-to- the-memory-fabric-directly idea the site’s coherent-NIC page builds on to cut latency, and it is why accessing the shared record costs microseconds rather than a round trip through a remote process. Second, the primitive that prevents equivocation, Consistent Tail Broadcast, refuses to remember history forever: it guarantees only the last t messages, trading a tunable window for bounded memory, so the trusted store stays under 1 MiB instead of growing without limit. Keeping only the recent tail rather than the whole log is what makes the trusted component small enough to trust and cheap enough to be fast.
Byzantine tolerance at the price of crash tolerance
From 3f+1 and milliseconds to 2f+1 and microseconds
Building microsecond-scale BFT over disaggregated memory. Numbers from the paper's RDMA-cluster evaluation.
Step 1 of 5
Why BFT costs more
A Byzantine copy can equivocate — tell some copies the next request is A and others that it is B — splitting the replicas into divergent histories. Classic BFT defeats this by using 3f+1 copies so voting quorums always overlap in an honest copy, plus rounds of signed messages, which together cost milliseconds.
the extra f copies beyond crash tolerance's 2f+1 exist purely to outvote liars by counting signature checks at nearly every step and all-to-all rounds are the latency tax
Why it works
- A Byzantine copy defeats replication by equivocating → a trusted single-writer memory forces it to record one statement everyone reads → it cannot tell two stories, so equivocation is prevented directly rather than by extra copies.
- Preventing equivocation removes the reason BFT needed 3f+1 → uBFT tolerates f Byzantine faults with 2f+1 copies → the same footprint as crash tolerance, not 50% more.
- Almost every request runs with a healthy network and honest copies → a fast path with no signatures and no memory access handles it → the common case costs about 10 microseconds instead of milliseconds.
- The fast path never affects safety; a correct signed, memory-backed slow path always exists → the system can be aggressive in the common case → it only pays the expensive path when a failure is actually detected.
- Standard consistent broadcast needs unbounded memory → Consistent Tail Broadcast guarantees only the last t messages → the trusted disaggregated memory stays under 1 MiB, small enough to trust and keep fast.
What it costs (trade-offs and scope)
- It trusts the disaggregated memory to be non-Byzantine. The entire 2f+1 result rests on the memory nodes and their access-control logic never lying, only crashing. uBFT keeps that component minimal and replicates it for reliability to make the assumption credible, but it is still an added trust anchor and extra hardware.
- It needs RDMA hardware with single-writer access control. The design assumes datacenter RDMA NICs (Mellanox ConnectX-class InfiniBand) with per-writer memory permissions — it is not for the open internet or commodity clusters without such fabric.
- The microsecond figure is the good-case number. The fast path assumes a synchronous network and cooperating copies; under real Byzantine disruption or asynchrony the system drops to the slow path (signatures plus memory), which is roughly 8 to 9 times slower (about 86 versus 10 microseconds).
- The tail parameter bounds memory but limits how far behind a copy may fall. Only the last t messages are guaranteed delivered, so a copy that lags beyond the tail window must recover via a checkpoint; and the non-trusted local replica memory is still gigabyte-scale (preallocated).
- Evaluated at small scale, with BFT’s usual overheads. The experiments tolerate one Byzantine fault with three replicas and small requests; quorum sizes and constants grow with f, and throughput (about 91 kops) is modest next to non-replicated systems — the standing price of Byzantine safety.
The evaluation
A 4-node cluster (three replicas plus a client, tolerating one Byzantine fault) with Intel Xeon Gold 6244 CPUs and 100 Gbps Mellanox ConnectX-6 InfiniBand, running Memcached, Redis, and a financial order-matching engine, comparing uBFT against Mu (crash-fault RDMA SMR) and MinBFT (SGX-based 2f+1 BFT), measuring latency, throughput, and memory.
Making a replicated service Byzantine-fault-tolerant
| Property | Crash tolerance (Paxos/Raft/Mu) | Classic or SGX BFT | uBFT (this work) |
|---|---|---|---|
| Failures tolerated | |||
| Copies needed | |||
| Anti-equivocation | |||
| Common-case latency | |||
| Trusted base |
Check yourself
Check your understanding
1. Classic Byzantine fault tolerance needs 3f+1 copies while crash tolerance needs only 2f+1. Predict the specific reason for the extra copies, and how uBFT avoids them.
2. uBFT relies on a trusted disaggregated memory, but deliberately makes that memory do almost nothing — just store data and enforce access control. Predict why keeping the trusted component minimal matters.
3. uBFT runs a fast path with no signatures at all, using cryptography only on a slow path. Predict why this is safe and why it helps.
4. uBFT's Consistent Tail Broadcast guarantees delivery of only the last t messages rather than all messages. Predict why this restriction is important.
Sources
- uBFT: Microsecond-scale BFT using Disaggregated Memory (arXiv:2210.17174, extended version) — ASPLOS 2023 (full text read via ar5iv).
- ar5iv HTML rendering — the version read for this explainer.
- arXiv PDF — full paper.