The question this answers
Why does making every node see the same order cost so much more than making them see a causally correct order?
Total order broadcast (atomic broadcast) guarantees: validity — a message broadcast by a correct node is eventually delivered by all correct nodes; integrity — no message is delivered twice, and only broadcast messages are delivered; total order — if any correct node delivers m1 before m2, every correct node delivers m1 before m2. It does not guarantee that the delivered order matches real time, or even causality, unless the protocol adds that separately.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A node knows the prefix of the sequence it has delivered, and that this prefix is identical at every other node that has delivered that many messages. It does not know whether more messages will be inserted before ones it has not yet delivered, and it does not know whether other nodes have progressed further. The prefix is agreed; the future is not, and a node that has stopped receiving cannot tell whether the system has stalled or it has been partitioned away.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
The equivalence, in both directions
Consensus is: a set of nodes must agree on one value, and all correct nodes decide the same value. Total order broadcast is: a set of nodes must agree on a sequence of messages, and all correct nodes deliver the same sequence. The claim is that these are the same problem, and the constructions are short enough to see immediately.
Total order broadcast gives you consensus. Every node broadcasts its proposed value. Every node decides the value in the *first* message delivered. Because all nodes deliver the same first message, all nodes decide the same value — and because a broadcast value is eventually delivered, they decide. That is consensus, in three lines, with no extra machinery.
Consensus gives you total order broadcast. Run a sequence of consensus instances, one per position: instance k decides which message occupies slot k. Deliver slots in order. Every node sees the same decisions in the same slots, so every node delivers the same sequence. This is not a curiosity — it is literally how Multi-Paxos and Raft are built, one consensus instance per log index (The Raft Log: Commit Index, Divergence and Reconciliation).
The consequence is unavoidable: anything that costs consensus costs total order broadcast, and vice versa. You cannot engineer your way to cheap total ordering while consensus remains expensive, because a cheap total order would be a cheap consensus. Any product claiming otherwise is either weakening the guarantee (usually to causal or per-partition) or relying on assumptions it has not stated.
1// consensus <- total order broadcast2propose(v):3 TOB.broadcast(v)4on TOB.deliver(m):5 if not decided:6 decided = true7 return decide(m) // all nodes deliver the same first message8 9// total order broadcast <- consensus10broadcast(m):11 pending.add(m)12loop k = 1, 2, 3, ...:13 chosen = Consensus[k].propose(pick_from(pending))14 deliver(chosen) // slot k is agreed; deliver in slot orderWhat the equivalence buys, and why it is worth paying for sometimes
If total ordering is this expensive, why is it everywhere? Because it makes replication trivial in a way nothing else does.
Take a deterministic state machine — a key-value store, a counter, a lock service. Feed every replica the identical sequence of operations. Every replica ends up in the identical state, with no merge logic, no conflict resolution, no version metadata, and no possibility of divergence. That is state machine replication, and it is the foundation under nearly every strongly-consistent distributed system: the replicated log is the total order, and the state is a fold over it (The Raft Log: Commit Index, Divergence and Reconciliation; the storage-side mechanics of shipping that log are Database’s subject, linked below).
The value is that it converts a distributed correctness problem into a single-machine one. You reason about your state machine as if it were a program on one box, and the log handles distribution. That is an enormous simplification, and it is why teams reach for it even knowing the cost. The mistake is not using it — the mistake is using it for *everything*, when only a subset of operations needs it (Do You Actually Need Consensus?).
The impossibility that sets the floor
The FLP result says: in an asynchronous system where even one node may crash, there is no deterministic algorithm that always reaches consensus. No bound on message delay means you cannot distinguish a crashed node from a slow one (Crashed or Just Slow: The Distinction You Cannot Make), and that single ambiguity is enough to make a guaranteed decision impossible.
Real systems obviously do reach consensus, so what gives? They escape by weakening one of the assumptions, and knowing which one your system weakened tells you exactly how it will behave badly. Partial synchrony: assume timing bounds eventually hold, so timeouts are eventually accurate — this is Raft and Paxos, and the consequence is that the system may make no progress during periods when the bounds do not hold. Randomisation: terminate with probability one rather than certainly. Failure detectors: assume an oracle that eventually stops suspecting correct nodes (No Heartbeat Does Not Mean Dead).
The practical translation of FLP is not "consensus is impossible" — it is "consensus cannot guarantee both safety and liveness under asynchrony, so every real protocol keeps safety and sacrifices liveness." Raft never produces two conflicting committed entries; it may fail to commit anything at all while elections keep timing out. That is the correct trade, and it is why your ordered system goes *unavailable* rather than *wrong* under network trouble.
| Assumption added | Consequence when it does not hold | |
|---|---|---|
| Partial synchrony (Raft, Paxos)assumption | Timing bounds eventually hold long enough to elect a leader | Repeated elections, no progress, writes stall while safety is preserved |
| Randomised timeoutsassumption | Termination with probability 1 | Occasional long tails on decision latency |
| Eventually-strong failure detectorassumption | Correct nodes eventually stop being suspected | A flapping network keeps suspicion alive and leadership churns |
| Majority reachableprotocol | Quorum intersection guarantees a single history | Minority side accepts nothing — deliberate unavailability |
The practical shape: pay for it once, narrowly
Given that the cost is irreducible, the engineering move is to buy total order in as small a scope as you can, and get maximum leverage from it. Three patterns do this well.
Order per partition, not globally. A partitioned log gives total order within a partition and no order across partitions (A Topic Is Not One Log: Ordering Lives Inside a Partition, Hash Partitioning and the Modulo Trap). If entities that share an invariant also share a partition, you get the guarantee where it matters and linear scalability everywhere else. This is by far the most common answer, and it is why Kafka-style systems scale while offering ordering at all.
Order the metadata, not the data. Use consensus for the small, low-volume decisions — who is the leader, what is the current configuration, which node owns which shard — and let the high-volume data path run without it (Coordination Services: The Primitives, Not the Product). A few hundred ordered decisions per second can safely govern a system doing millions of unordered operations.
Order lazily. Accept writes without ordering, and impose an order only when an invariant is about to be violated (Coordination Avoidance: Restructuring the Problem Instead of Paying for It). Most operations never touch a global invariant, so most never pay.
And the honest last option: do not order at all. If your operations commute, the sequence does not matter and every node converges regardless (CRDTs: Deterministic Merge, Not Correct Merge, What "Eventually Converges" Actually Requires). Designing for commutativity is the only way to make ordering genuinely free, because it removes the requirement rather than paying for it.
Key points
- Total order broadcast and consensus are equivalent: each can be implemented from the other in a few lines.
- Therefore total ordering cannot be made cheaper than consensus — a cheap total order would be a cheap consensus.
- Its value is state machine replication: identical deterministic replicas fed an identical sequence, with no merge logic at all.
- FLP says no deterministic algorithm guarantees consensus under asynchrony with one crash; real protocols keep safety and give up liveness.
- That is why ordered systems go unavailable rather than wrong when the network misbehaves.
- The engineering move is to scope total order narrowly: per partition, over metadata only, or lazily — or to avoid it by making operations commute.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • A message is submitted for broadcast and buffered rather than delivered.
- • The protocol runs one agreement per position in the sequence, assigning messages to slots.
- • A slot is committed once a quorum has durably accepted it, so no future leader can assign a different message to that slot.
- • Nodes deliver committed slots strictly in order, holding back any slot whose predecessors are not yet committed locally.
- • Each replica applies delivered messages to a deterministic state machine, so all replicas converge to identical state.
- • The leader crashes after a slot is accepted by some nodes but committed by none, leaving the slot's fate undetermined until the next term resolves it.
- • A partition leaves the leader on the minority side; it continues to believe it leads until it learns otherwise (Split-Brain: Two Nodes, Both Certain They Are In Charge).
- • Elections repeatedly time out under a flapping network, so no leader is stable long enough to commit anything.
- • A slow follower falls arbitrarily far behind, and delivery on that replica lags without any error.
- • A non-deterministic operation in the state machine (a random value, a wall-clock read, map iteration order) makes replicas diverge despite identical input.
- • Writes stall with no error: elections keep timing out, so the cluster has no leader and every ordered operation blocks. The operator sees rising term numbers, zero commits, and healthy processes on every node.
- • Minority-side unavailability: one zone is partitioned off and accepts no writes at all while its hosts and processes are perfectly healthy. Availability drops by exactly the fraction of traffic routed to that zone.
- • Head-of-line blocking: one expensive operation occupies the head of the sequence and every subsequent operation waits behind it. The operator sees latency rise across unrelated keys that share the log.
- • A follower silently drifts: replication lag on one node grows without bound and reads served from it become arbitrarily stale Performance covers the read-side consequence of that lag, linked below.
- • Replica divergence from non-determinism: identical logs produce different state because the state machine read a clock or iterated a map. The operator sees two replicas disagreeing on a key while both report a fully-applied log — the most confusing failure in this list, because the log is provably identical.
- • One agreement per delivered message (or per batch), each requiring a durable majority acceptance. This is the price, stated plainly.
- • Latency is bounded below by the round trip to the furthest quorum member, which in a multi-region deployment is physics (The One Number You Cannot Optimise).
- • Throughput is bounded by the sequencing point, since assigning positions is inherently serialised — batching and pipelining raise the constant but do not change the shape.
- • Availability is bounded by majority reachability. A three-node group tolerates one failure; five tolerates two. That is the entire fault-tolerance story, and it is why group size is an availability decision, not a performance one.
- • Safety holds absolutely: two nodes never deliver different messages at the same position, regardless of how the network behaves.
- • Liveness does not: with no reachable majority, the system delivers nothing. This is a deliberate, correct choice.
- • Committed prefixes remain committed and durable across leader changes; a new leader cannot rewrite them.
- • Uncommitted entries at a deposed leader may be discarded, which is why a client that saw no response must treat the outcome as unknown (A Timeout Tells You Nothing About Whether It Happened).
- • Detect: alert on term/epoch churn and on time-since-last-commit, which together distinguish "no traffic" from "cannot commit".
- • Contain: keep the consensus group small and its workload small; do not put the high-volume data path through it.
- • Recover: restore majority connectivity — that is the only real fix. Everything else is a workaround with a correctness cost.
- • Reconcile: catch up lagging followers by log shipping, or by snapshot transfer when the gap exceeds retention (Recovered State Is a Checkpoint Plus the Log After It).
- • Verify: after recovery, confirm every replica has applied the same committed index and that state hashes match — this is the check that catches non-determinism.
- • Commit latency at p99, separated from apply latency — the first is agreement cost, the second is state-machine cost, and conflating them hides the diagnosis.
- • Term or epoch number over time. A monotonic slow climb is healthy; rapid increase means elections are failing.
- • Time since last successful commit, per group. The single best "are we actually ordered and progressing" signal.
- • Per-follower replication lag in log entries and in seconds, alerting on the maximum.
- • A periodic state hash comparison across replicas at a common applied index, which is the only way to catch divergence from non-determinism.
- • Enforcing invariants that span nodes: uniqueness, non-negative balances, exclusive ownership (Start From the Invariant, Not From the Architecture, Distributed Uniqueness: One Name, Many Shards).
- • Replicating a state machine where divergence is unacceptable and merge logic would be error-prone.
- • Configuration, membership and leadership decisions — low volume, high consequence, exactly the right shape for consensus (Coordination Services: The Primitives, Not the Product).
- • High-volume, commutative operations where the order is irrelevant and the coordination is pure cost.
- • Multi-region write paths, where the quorum round trip adds cross-continent latency to every operation (Three Ways to Accept a Write in More Than One Place).
- • Anything that must remain writable during a partition — total order and partition-tolerant availability are mutually exclusive by construction.
- • Large groups: adding members increases fault tolerance slowly and increases commit latency immediately.
- • Order within a partition only, so each partition has a cheap local total order and cross-partition operations are handled explicitly: A Topic Is Not One Log: Ordering Lives Inside a Partition, Cross-Partition Operations: Paying for What the Split Took Away.
- • Use consensus for metadata and leave the data path unordered: Coordination Services: The Primitives, Not the Product.
- • Design operations to commute so no order is needed at all: CRDTs: Deterministic Merge, Not Correct Merge, What "Eventually Converges" Actually Requires.
- • Use a single non-replicated sequencer where a brief outage is acceptable — dramatically simpler, and honest about its failure mode.
- • Impose order lazily, only when an invariant is at risk: Coordination Avoidance: Restructuring the Problem Instead of Paying for It.
- • Accept causal order instead, which is free of agreement and sufficient for most user-visible correctness: Happens-Before: The Only Ordering You Actually Have.
Total order broadcast is consensus wearing a different hat
| Assumption added | Consequence when it does not hold | |
|---|---|---|
| Partial synchrony (Raft, Paxos)protocol | Timing bounds eventually hold long enough to elect a leader | Repeated elections, no progress, writes stall while safety is preserved |
| Randomised timeoutsprotocol | Termination with probability 1 | Occasional long tails on decision latency |
| Majority reachableprotocol | Quorum intersection guarantees a single history | The minority accepts nothing — deliberate unavailability |
What people believe, and what is true
Total order broadcast is a messaging feature; consensus is a database thing.
They are the same problem. A broker offering global total ordering is running a consensus protocol, whether or not its documentation says so.
A faster network makes total ordering cheap.
It lowers the constant. The availability cost — no majority, no progress — is unchanged, and that is the cost that shows up in incidents.
FLP means consensus does not work in practice.
It means no algorithm can guarantee termination under full asynchrony. Real protocols keep safety unconditionally and give up liveness during bad periods, which is exactly what you want.
Replicas with identical logs must have identical state.
Only if the state machine is deterministic. A single Date.now() in an applied operation is enough to diverge replicas that agree perfectly on the log.
Adding nodes to a consensus group makes it more available.
It raises the number of tolerated failures and raises commit latency at once. Beyond five members the availability gain is usually smaller than the latency and reconfiguration cost.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Delivering the same messages in the same order everywhere is exactly as hard as agreeing on a value — they are the same problem. That is why total ordering costs a round trip to a majority and stops when the majority is unreachable.
Practical
Use it for invariants and for metadata; keep the group small and the ordered workload small. Monitor time-since-last-commit and term churn. Make your state machine deterministic and verify with periodic state-hash comparison — divergence from a now() call is the failure that wastes the most time.
Advanced
Both reductions are short: consensus from TOB by deciding the first delivered message; TOB from consensus by running one instance per log slot. FLP then transfers directly to TOB, so no deterministic total-order protocol can guarantee progress under asynchrony. Deployed protocols add partial synchrony and preserve safety while sacrificing liveness — which is precisely why the observable failure is a stall, not a corruption.
Internals
In a Raft-style implementation each slot is a log index, and the "one consensus instance per slot" reduction is collapsed: a stable leader skips the proposal phase and appends directly, so the steady state costs one round trip rather than two. Safety rests on quorum intersection — any two majorities share a member — plus a term number that makes a stale leader's appends rejectable. Commitment is the leader observing durable acceptance by a majority; a leader that commits without that can be superseded and its entry replaced, which is the exact scenario the majority rule exists to prevent.
Apply it
- 🔧 Implement consensus on top of a total-order-broadcast primitive in under ten lines, then the reverse.
- 🔧 Audit a replicated state machine for non-determinism: clock reads, randomness, map iteration, floating point, and locale-dependent comparison.
- ⚡ A cluster stops accepting writes. Every process is healthy, CPU is low, and the term number is increasing rapidly. Diagnose.
- ⚡ A team wants global ordering across all events in a system doing 500k events/second. What do you propose instead, and how do you justify it?
- 💬 Show that total order broadcast and consensus are equivalent. Both directions.
- 💬 Two replicas have byte-identical logs and applied the same index, yet disagree on a key. How is that possible?
- 💬 What does FLP actually rule out, and how does Raft live with it?
- 💬 Your consensus group is doing 200 commits per second and the p99 is 40 ms. Where would you look to improve it, and what would you refuse to change?