Notesdistributed🌱 seedling

Total Order Broadcast

Also: Atomic Broadcast · State Machine Replication · Replicated Log

A protocol that delivers every message to every node, in the same order on all of them. Feed deterministic replicas the same ordered log and they stay identical; keeping that order through leader failures is equivalent to consensus.

Why it exists

Replicas that apply the same writes in different orders diverge. Decisions like "who claimed this name first" need an order that's fixed when messages are sent, not reconstructed later from timestamps.

How it works

  • Reliable delivery: a message delivered to one node is delivered to all.
  • Total order: every node delivers messages in the same sequence, and the order is fixed once delivered.
  • Usually a leader assigns sequence numbers and appends to a replicated log; followers apply in log order (state machine replication).
  • The log position is a natural Fencing Token and a basis for linearizable compare-and-set and uniqueness checks.
  • If the leader fails, nodes must agree on the next leader and the exact log contents: that is Consensus. Each can be built from the other.

Trade-offs

Gains Costs
identical replicas, simple reasoning every message funnels through one ordered sequence (throughput ceiling)
enables locks, uniqueness, fencing needs a majority available to make progress
order is final once delivered cross-region round trips on the write path

In practice

  • ZooKeeper (Zab) and etcd (Raft) are replicated logs used for coordination; ZooKeeper's zxid is the log position.
  • Apache Kafka gives a total order per partition, not across partitions, which is how it scales.

Pitfalls

  • Assuming order across Kafka partitions or across shards. Total order is per log.
  • Building it on timestamps instead of a log: skew reorders messages.

Recall

These cards are also in your review deck, scheduled with spaced repetition.