Atomic Broadcast — Consensus 4.3

This article ties together a thread that's been running quietly since Phase 3: State Machine Replication (3.1), log replication (3.2), and a formal problem called Total Order (Atomic) Broadcast are, provably, three different framings of the exact same underlying computational problem. This isn't a loose analogy — it's a formal equivalence result, and understanding it explains something genuinely useful: why a consensus algorithm, an SMR system, and a totally-ordered multicast system can all be built from each other, and why research and production systems freely borrow techniques across all three framings without loss of generality. This is also the last purely conceptual article before Phase 4 turns to the two historical protocols (2PC, 3PC) that directly motivated real consensus research.

Total order broadcast, defined

A Total Order Broadcast (also called Atomic Broadcast) primitive lets any process broadcast(m) a message m, and guarantees two properties across every correct process that receives messages via deliver(m):

Atomicity (agreement): if any correct process delivers message m, then every correct process eventually delivers m — no message is delivered to some correct processes but silently dropped for others.
Total order: if two correct processes both deliver messages m1 and m2, they deliver them in the same relative order — no process sees m1 before m2 while another sees m2 before m1.

Read those two properties again next to article 3.1's SMR requirement ("every replica applies the same commands in the same order") and article 3.2's log requirement ("every replica's log agrees on entry order at every committed position") — they're not similar, they're the same statement, just using "broadcast/deliver" vocabulary instead of "propose/commit" or "append/replicate" vocabulary.

Fig 1 — Different vocabulary, formally identical underlying problem.

The equivalence with consensus, sketched

The formal result (well-established in the distributed systems literature, notably formalized by Chandra and Toueg among others) is that Total Order Broadcast and Consensus are equivalent — each can be built from the other, meaning a solution to one gives you a solution to the other with only modest additional machinery. Both directions are worth sketching, because each direction illuminates a different, useful engineering pattern.

Consensus → Atomic Broadcast

Given a working consensus primitive (agree on one value at a time — this is literally what single-decree Paxos, covered in Phase 5.2, does), you can build atomic broadcast by running a sequence of independent consensus instances, one per log position: instance 1 decides which message goes at position 1, instance 2 decides position 2, and so on. This is, precisely, what Multi-Paxos (Phase 5.3) and Raft's log replication (Phase 5.6) actually are — a sequence of consensus decisions, one per log slot, which is exactly why article 3.2's log replication and this article's atomic broadcast were flagged as "the same problem" above.

Atomic Broadcast → Consensus

Given a working atomic broadcast primitive, you can solve single-value consensus: every process broadcasts its proposed value, and whichever value is delivered first (by the total-order guarantee, every correct process agrees on which one that is) becomes the decided value. This direction is arguably the more surprising one on a first read — it shows that "agree on an order of many things" and "agree on one single thing" are not actually different-difficulty problems, just different framings of the same underlying difficulty.

Why this equivalence is practically useful, not just theoretically tidy: it means research and engineering effort spent on any one of these three framings (consensus algorithms, SMR systems, atomic broadcast protocols) directly transfers to the other two. A performance improvement discovered for atomic broadcast protocols in the message-passing literature can be applied to log-replication systems, and vice versa — this cross-pollination is a real, recurring pattern in the field, and it's part of why some of the algorithms in Phase 7 (the modern Paxos family) borrow ideas that originated in the atomic-broadcast research literature rather than the "consensus" literature specifically.

Why the field still uses three separate names, given the equivalence

If they're formally equivalent, why hasn't the field simply standardized on one term? Because each framing highlights different, useful engineering emphases even though the underlying mathematical problem is identical:

"Consensus" emphasizes the single-decision moment — useful when reasoning about safety proofs and the FLP-style impossibility results (article 2.5), which are most naturally stated in terms of a single agreed value.
"State Machine Replication" emphasizes the application-facing outcome — useful when reasoning about what a system built on top of consensus actually delivers to its users (article 3.1's framing).
"Atomic/Total Order Broadcast" emphasizes the messaging-and-delivery semantics — useful when reasoning about network protocols, message ordering guarantees, and multicast-style system design, and it's the framing most naturally connected to the pub/sub and event-streaming systems that show up later in this series (Kafka's KRaft, Phase 8.4, is essentially an atomic-broadcast system by construction).

Knowing all three names — and knowing they're the same thing — is genuinely useful for reading the literature broadly: a paper framed around "atomic broadcast" and a paper framed around "state machine replication" might be solving, and improving on, the identical underlying problem, and missing the connection means missing directly-relevant related work.

FAQ

Is atomic broadcast the same thing as reliable broadcast?

No, and the distinction matters — reliable broadcast only guarantees the atomicity property (every correct process delivers the same set of messages) without the total-order property (they might deliver those same messages in different relative orders). Reliable broadcast alone is a strictly weaker, easier primitive than atomic broadcast; it's atomic broadcast's total-order guarantee specifically that makes it equivalent in power to consensus.

Does the consensus-to-broadcast direction (running a sequence of consensus instances) have any real downsides compared to running one big consensus decision?

It introduces its own coordination overhead per log slot if done naively (a full leader-election-style negotiation for every single entry) — which is exactly the performance problem Multi-Paxos (Phase 5.3) specifically solves, by electing a stable leader once and then only running the lightweight "propose a value" phase repeatedly, rather than re-running full leader election for every log position. This optimization is a direct, practical answer to the overhead this equivalence direction would otherwise imply.

Is Kafka's KRaft mode literally implementing atomic broadcast?

In spirit and in formal characterization, yes — a Kafka partition's ordered, durably-replicated log of messages, agreed upon by the KRaft consensus layer (itself Raft-based), is functionally an atomic broadcast channel: every consumer that reads the partition sees the same messages in the same order. Full treatment of Kafka's specific architecture is in Phase 8.4.

Why introduce this equivalence now, in Phase 4, rather than back in Phase 3 alongside SMR?

Because appreciating the equivalence fully requires having already seen both SMR (3.1) and the safety/liveness framework (4.1) — this article deliberately sits right before Phase 5's classical algorithms specifically so readers approach Paxos and Raft already knowing that "consensus," "replicated log," and "atomic broadcast" are one problem wearing three names, which makes the algorithms' design choices (especially Multi-Paxos's optimization, mentioned above) immediately legible rather than mysterious.

Takeaways

Total Order (Atomic) Broadcast requires two properties: atomicity (every correct process delivers the same messages) and total order (every correct process delivers them in the same relative order).
This is formally equivalent to consensus — a sequence of consensus instances builds atomic broadcast (this is literally what Multi-Paxos and Raft's log replication are); atomic broadcast can conversely be used to solve single-value consensus by taking the first-delivered value.
SMR, log replication, and atomic broadcast are three names for the same underlying problem, each emphasizing a different useful engineering angle — application outcome, storage mechanics, and messaging semantics respectively.
This equivalence means techniques and results transfer freely across all three framings in the research literature — missing the connection means missing directly-relevant work.
Multi-Paxos's key optimization (elect a stable leader once, avoid re-running full negotiation per log slot) is a direct, practical answer to the naive overhead the consensus→broadcast reduction would otherwise imply.

References & further reading

Défago, Schiper & Urbán — Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey (2004) — comprehensive survey of atomic broadcast approaches and their relationship to consensus.
Chandra & Toueg — Unreliable Failure Detectors for Reliable Distributed Systems (1996) — includes the consensus/atomic-broadcast equivalence formalization.
cvam.sight — Consensus 3.1: State Machine Replication — the same underlying problem, application-outcome framing.
cvam.sight — Consensus 3.2: Log Replication — the same underlying problem, storage-mechanics framing.

Atomic broadcast.