When working with distributed systems, it’s easy to confuse Total Order Broadcast (TOB) and Linearizability. After all, both seem to talk about order. However each serve different purposes and operate at different layers of a system’s design. Let's unpack!
If every replica delivers the same messages in the same order, surely we must be consistent, right?
Not quite.
A system where everyone agrees can still be out of sync. That’s the paradox at the heart of distributed replication.
When Everyone Agrees: Total Order Broadcast
Total Order Broadcast (TOB) ensures that all nodes in a distributed system deliver messages in the same order. If one server delivers message m1 before m2, every other server does the same.
This is how consensus protocols like Paxos and Raft maintain replicated logs, each node applies the same sequence of events.
But consensus gives us agreement, not simultaneity. It says nothing about when each replica applies that decision or when clients observe it. Some replicas might lag, some clients might read stale data, yet the system remains “consistent” in its internal sense of order.
When Everyone’s in Sync: Linearizability
Bridging that gap - turning shared history into shared experience - is what linearizability adds on top of consensus.
Linearizability ensures that clients observe operations as if each took effect at a single, instantaneous moment, in real-time order. All observers must see a consistent view of the system as if there were no replication or concurrency. The basic idea is to make a system appear as if there were only one copy of the data, and all operations on it are atomic. It’s the strongest consistency model we can provide and the one that makes a distributed system feel like a single, well-behaved machine. Linearizability adds a real-time constraint: once a write completes, every later read (by anyone) must see it.
The Soccer Score Analogy
Martin Kleppmann captures this distinction beautifully in Designing Data-Intensive Applications.
Imagine a replicated store for a live football score.
score = 1–0
score = 2–0
score = 2–1
Two fans read from different replicas. One replica has processed 2–0, another is still catching up.
• With TOB, both replicas will eventually apply updates in the same order. Yet, in the meantime, one fan might see 1–0 while the other already sees 2–0. They agree on the order, not the moment.
• With Linearizability, once 2–0 is acknowledged, every subsequent read must return 2–0. The system ties internal order to real-time visibility.
That’s the difference between a consistent history and a consistent reality.
Two Worlds of Linearizability
Linearizability isn’t tied to one implementation style. It’s a property that a system can achieve through different mechanisms.
There are two main families of systems that implement it:
1. Leader-based systems (e.g. Raft, Paxos, Viewstamped Replication)
• The leader imposes a total order on all operations (that’s effectively TOB via consensus).
• A write is only acknowledged once it’s replicated and committed by a majority quorum.
• Reads go through the leader (or a consistent follower) to ensure they see the latest committed entry.
2. Leaderless quorum systems (e.g. Dynamo-style quorum reads/writes)
In leaderless systems, you don’t have a leader sequencing all writes. Instead, you rely purely on quorum overlap for consistency. Writes go to W replicas; reads query R replicas; if R + W > N, read and write quorums overlap.
In principle, this can yield linearizability (the read hits at least one up-to-date replica and chooses the newest version). However, in practice, systems prioritise availability/latency: they return quickly, then repair lazily (read repair, anti-entropy). They reconcile over time, not in real time, so defaults are typically eventual or quorum consistency, not strict linearizability.
Why Control Plane Systems Need Linearizability
In my previous post, I discussed how Consensus gives a cluster of nodes a shared, ordered view of reality. But what really needs to be emphasised here is the phrase - "view of reality".
Consensus protocols guarantee Total Order Broadcast, not linearizability by default. In other words, with consensus, cluster nodes may share an ordered history but may not necessarily be in sync when observed through reads.
Control plane systems like ZooKeeper, etcd, or Consul manage coordination state: who’s the leader, which partition is assigned where, what configuration version is current, what membership view is valid, etc. In these systems:
• Clients rely on reading fresh state (e.g. current leader, config version).
• Multiple clients may act based on that state (e.g. a scheduler assigning resources, a controller deciding failover).
If the control plane were merely TOB-consistent, replicas could momentarily disagree on “who’s the leader” or “what’s the latest config” even though they’d eventually converge. That’s unacceptable. Those decisions must appear instantaneous and globally visible.
That’s why control-plane coordination stores are deliberately linearizable:
• etcd uses Raft and only serves reads after confirming leadership or commit index freshness.
• ZooKeeper provides linearizable writes and reads (if you read from the leader or via sync).
• Consul follows similar rules, linearizable KV reads for control-plane semantics.
This ensures the control plane behaves like a single source of truth at any moment. If it weren’t linearizable, race conditions would leak upward and you’d get double leaders, conflicting partition assignments, or out-of-date configs controlling live data-plane systems.