Consistency Models in Distributed Systems
Linear consistency (also called linearizability) is a formal correctness condition for concurrent systems. It guarantees that all operations appear to execute atomically in some sequential order, with each operation taking effect instantaneously between its invocation and response.
In practical terms: once an operation completes and a client receives acknowledgment, every subsequent operation sees the effects of that completed operation. There’s no window where one client sees a result but another doesn’t.
Core Guarantees
Atomicity: Each operation appears indivisible—it either fully completes or doesn’t execute at all. No partial states are visible.
Real-time Ordering: If operation A completes before operation B starts (in wall-clock time), then A must appear before B in the logical order. This respects causality.
Total Order: All operations across all clients are totally ordered. There’s a single sequence that explains all observed behavior.
This differs from weaker consistency models like eventual consistency (where replicas converge over time) or causal consistency (where only causally-related operations have ordering guarantees).
Why It Matters
Data correctness in critical systems: Banking transfers, distributed transactions, and medical records require that no two clients ever see conflicting states. Linear consistency prevents race conditions and double-spends.
Easier reasoning: Developers can write distributed code as if operating against a single machine—simpler logic, fewer subtle bugs.
Regulatory compliance: Many industries (finance, healthcare) legally require strong consistency guarantees that linear consistency provides.
The Performance Cost
Achieving linear consistency requires coordinating writes across replicas. Every write must be acknowledged by enough replicas to guarantee that reads see consistent state. This introduces latency:
- Synchronous replication: All replicas must acknowledge before clients receive response
- Quorum writes: Writes hit a majority; reads also hit quorums to ensure consistency
- Single-leader bottleneck: Some systems route all writes through one node to establish order, creating latency and availability risks
For latency-sensitive applications (game servers, real-time analytics), the coordination overhead is often unacceptable. This is where the CAP theorem comes in: you can’t simultaneously guarantee consistency, availability, and partition tolerance. Most production systems sacrifice one.
Consensus Protocols
Raft is the modern standard for achieving linearizability in distributed systems. It’s simpler than Paxos and widely implemented in etcd, Consul, and many databases. Raft elects a leader that sequences all writes; followers apply them in order.
Paxos was the original rigorous consensus algorithm but is harder to understand and implement correctly. Still used in systems like Google Chubby.
Both protocols work by having replicas agree on the order of operations. When a partition occurs (split-brain), the algorithm ensures that only one partition can accept new writes, preventing divergence.
Time-Based Ordering
Some systems use hardware-assisted clock synchronization:
Google Spanner uses TrueTime (GPS and atomic clocks on multiple datacenters) to assign each transaction a timestamp. Since TrueTime bounds clock uncertainty, Spanner can guarantee that a transaction with timestamp T is linearizable with respect to all transactions with higher timestamps.
CockroachDB uses similar principles with the HLC (Hybrid Logical Clock) to provide linearizability without relying on perfectly synchronized physical clocks. HLC combines physical time with a logical counter to handle clock skew.
These approaches are effective for geo-distributed systems but require infrastructure most organizations don’t have.
Trade-offs and Alternatives
For read-heavy workloads, some systems offer read-after-write consistency: your own writes are immediately visible to you, but other users’ recent writes might not be. This relaxes global ordering while maintaining per-client causality. Redis with replication and eventual-consistency-with-read-repair is an example.
Eventual consistency drops the ordering guarantee entirely. All replicas eventually converge to the same state, but clients may see stale data temporarily. DynamoDB, Cassandra, and S3 use this model for high availability and throughput.
The choice depends on your workload. A stock exchange needs linearizability. A social media feed doesn’t.
Real-World Implementations
etcd: A distributed key-value store that guarantees linearizability for reads and writes through Raft consensus. Used by Kubernetes for state management.
PostgreSQL with streaming replication: Synchronous replication mode provides linearizability by waiting for replica acknowledgment before committing.
DynamoDB: Offers eventual consistency by default; strong consistency is available per-request but at higher latency cost.
When designing systems, measure whether linearizability is actually required for your use case. Many teams over-engineer consistency guarantees and pay the latency penalty unnecessarily.