Articles

In systems interviews the consistency question is usually answered with a word: “strong” or “eventual.” That binary is a trap. Stronger models cost round-trips on the critical path. Weaker ones admit histories a single machine would never produce. This article names the models from linearizability down to eventual, shows what CAP and PACELC actually constrain, and walks the three mechanisms that implement them: Raft and Paxos, quorum intersection, and CRDTs.

A model is a contract over histories

A consistency model is not a product flag. It is an invariant over execution histories: the interleaved reads and writes of many clients, as seen by many replicas. Herlihy and Wing’s 1990 definition of linearizability is the template the others follow:

Linearizability provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response.

The cost is coordination. A stronger guarantee requires a network round-trip on the critical read path, the critical write path, or both. A replica that answers from local memory is fast, and it is also the replica that can lie.

The lattice, strictest first

Linearizability     real-time global total order; needs consensus
        |
Sequential          some global order; each process's program order is kept
        |
Causal              happens-before is kept; concurrent ops may be reordered
        |
   +----+----+
   |         |
RYW      monotonic reads / writes     session-scoped, not system-wide
   |         |
   +----+----+
        |
Eventual            if updates stop, replicas converge

Linearizability

If write $W_1$ returns before read $R_1$ begins, $R_1$ must observe $W_1$ or a later write. Wall-clock real time is part of the contract. Stale reads, time-travel reads, and non-monotonic reads are forbidden. This is the model etcd, ZooKeeper (with sync), Spanner (via TrueTime), and CockroachDB advertise.

Sequential consistency

Lamport’s 1979 rule is weaker on time and still total on order:

The result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

Two clients can disagree about which write happened “first” in real time, as long as each client’s own program order is respected. Process-local reordering is forbidden. Cross-process real-time order is not.

Causal consistency

Operations related by Lamport’s happens-before relation must be seen in the same order everywhere. Concurrent operations - neither is a cause of the other - may be observed in different orders on different replicas. The forbidden anomaly is seeing an effect without its cause: a reply before the original message, a like-count before the post.

Session guarantees

These are weaker still, because they are scoped to one client session, not to the whole system.

Read-your-writes (RYW): a client always sees its own writes.
Monotonic reads: once a client has seen version $v_1$ , it never later sees $v_0$ .
Monotonic writes: a single client’s writes are applied in the order it issued them.

Sticky sessions, session tokens, and “read from the node you just wrote” are how stores buy these without buying causal consistency for everyone.

Eventual consistency

Werner Vogels’s restatement is the whole contract:

If no new updates are made to the object, eventually all accesses will return the last updated value.

Until quiescence, a replica may serve an arbitrarily stale value, invert cause and effect, and hold a write that conflicts with a concurrent write on another replica. Dynamo, Cassandra, Riak, and DNS live here. Convergence is the promise. The path is not.

Model	What it forbids	What it costs
Linearizability	stale reads against real-time order	consensus, or TrueTime-style bounded clocks
Sequential	per-process reordering	a global order, not a real-time one
Causal	effect before cause	version vectors / dependency tracking
RYW / monotonic	session-local time travel	sticky sessions or session tokens
Eventual	nothing until silence	anti-entropy, hinted handoff, CRDT merge

CAP is not a menu of three

$P$ is not a design choice. Networks drop packets. Switch ASICs fail. A garbage-collection pause isolates a node as thoroughly as a cut cable. Gilbert and Lynch proved Brewer’s conjecture in 2002: you cannot implement a read/write register that is available and atomically consistent in every execution of a network that can partition.

So CAP reduces to one sentence. Under a partition, choose availability or consistency: $P \Rightarrow A \lor C$ . A system that keeps serving on both sides of a split cannot also keep a single linearizable copy. A system that keeps a single linearizable copy must refuse work on the minority side.

The FLP result sits next to CAP, not inside it. Fischer, Lynch, and Paterson showed that in a fully asynchronous network, even one crash-stop failure makes consensus impossible. Raft and Paxos escape that impossibility by assuming partial synchrony: timeouts, election deadlines, heartbeat intervals. The timeout is not an implementation detail. It is the extra assumption the proof requires.

PACELC: the other 99.99 percent of the time

Most of a system’s life is not a partition. Daniel Abadi’s PACELC (2012) names the trade that actually shows up in latency budgets:

If there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

Four letters, two questions. Under a split, $A$ or $C$ . When the network is fine, $L$ or $C$ . Spanner is PC/EC: minority partitions become unavailable, and healthy-path reads still wait for TrueTime. Cassandra is PA/EL: both sides of a split keep taking writes, and a healthy-path read can be one replica. MongoDB can be PA/EC or PC/EC depending on write concern and read concern. “We picked AP” is not a PACELC answer. The else-clause is the one your p99 will notice.

Three mechanisms

Consensus: Raft and Paxos

A linearizable replicated state machine runs a consensus protocol. Paxos is the family; Raft is the one most stores ship. The leader sequences every write. Followers accept a log entry only when a quorum has persisted it. That is how a write becomes a single point on the real-time line.

Reads are the easy place to cheat. A naive Raft leader that answers from local memory can lie: a partitioned former leader still thinks it is leader and serves values the new majority has already overwritten. Honest linearizable reads wait for a heartbeat round-trip to a quorum (Raft’s Read Index) or hold a leader lease so a local read is still inside the lease interval. The lease is a bound on clock drift, not a feeling.

Quorum intersection

In an $N$ -node replica group with read quorum $R$ and write quorum $W$ , the pigeonhole principle does the work. If $R + W > N$ , the read set and the write set overlap: $|R \cap W| \ge 1$ . The overlapping node holds the latest version, provided versions are comparable (a monotonic timestamp, a version vector).

defmodule QuorumOverlap do
  def overlap?(n, r, w), do: r + w > n

  def latest(replicas, ids) do
    ids
    |> Enum.map(&Map.fetch!(replicas, &1))
    |> Enum.max_by(& &1.vclock)
  end
end

replicas = %{
  1 => %{val: :a, vclock: 2},
  2 => %{val: :a, vclock: 2},
  3 => %{val: :a, vclock: 2},
  4 => %{val: nil, vclock: 0},
  5 => %{val: nil, vclock: 0}
}

# N=5, W=3 wrote to 1,2,3. R=3 reading 3,4,5 overlaps at 3 and sees :a.
QuorumOverlap.overlap?(5, 3, 3)
# => true
QuorumOverlap.latest(replicas, [3, 4, 5])
# => %{val: :a, vclock: 2}

# R=1, W=1: a read of node 5 misses the write.
QuorumOverlap.overlap?(5, 1, 1)
# => false
QuorumOverlap.latest(replicas, [5])
# => %{val: nil, vclock: 0}

The trap is the sloppy quorum. When a preferred node is down, Dynamo-style stores accept the write on a fallback node and hint it home later. That keeps availability. It also drops the overlap invariant on the primary replica set: $R + W > N$ no longer holds for the nodes a later read will actually contact. Strict $R + W > N$ only promised a non-empty intersection so a later read can pick the latest comparable version. A sloppy quorum drops even that, and the store has silently become eventually consistent. Hinted handoff and anti-entropy are how it hopes to catch up. They do not restore the overlap.

CRDTs: converge without a coordinator

Conflict-free replicated data types get eventual consistency from algebra, not from a leader. A state-based CRDT is a join-semilattice: states, plus a merge that computes a least upper bound. Merge has to be commutative, associative, and idempotent:

$a \sqcup b = b \sqcup a$
$(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
$a \sqcup a = a$

Any replica can merge any other replica’s state, in any order, any number of times, and the result is the same. No election. No lock. A PN-counter (positive-negative counter) is the small example: each actor keeps its own increment total and decrement total; merge takes the per-actor maximum; the value is the difference of the sums.

defmodule CRDTPNCounter do
  defstruct positive: %{}, negative: %{}

  def new, do: %__MODULE__{}

  def inc(%__MODULE__{positive: pos} = counter, actor, delta \\ 1)
      when delta >= 0 do
    %{counter | positive: Map.update(pos, actor, delta, &(&1 + delta))}
  end

  def dec(%__MODULE__{negative: neg} = counter, actor, delta \\ 1)
      when delta >= 0 do
    %{counter | negative: Map.update(neg, actor, delta, &(&1 + delta))}
  end

  def value(%__MODULE__{positive: pos, negative: neg}) do
    Enum.reduce(pos, 0, fn {_actor, v}, acc -> acc + v end) -
      Enum.reduce(neg, 0, fn {_actor, v}, acc -> acc + v end)
  end

  def merge(
        %__MODULE__{positive: p1, negative: n1},
        %__MODULE__{positive: p2, negative: n2}
      ) do
    %__MODULE__{
      positive: Map.merge(p1, p2, fn _k, v1, v2 -> max(v1, v2) end),
      negative: Map.merge(n1, n2, fn _k, v1, v2 -> max(v1, v2) end)
    }
  end
end

a = CRDTPNCounter.new() |> CRDTPNCounter.inc(:a, 3) |> CRDTPNCounter.dec(:a, 1)
b = CRDTPNCounter.new() |> CRDTPNCounter.inc(:b, 2)
merged = CRDTPNCounter.merge(a, b)
CRDTPNCounter.value(merged)
# => 4
CRDTPNCounter.value(CRDTPNCounter.merge(merged, a))
# => 4

An observed-removed set (OR-Set) is the same idea with identities: adding an element tags it with a unique id; removing it tombstones those ids; merge unions both sets. Two replicas can add and remove the same member while partitioned and still agree once they meet.

What “strong” and “eventual” actually buy you

Name the model, the stale-read bound, and the failure domain. “Eventual” is not an answer. “Causal, with read-your-writes in a session, and a 50 ms p99 when the network is healthy” is an answer. Linearizability is what you want for a lock, a leader election, or a unique-id generator. Eventual is what you can afford for a view count, a shopping cart, or DNS. The hash-table fine print is the same shape: the slogan is true, and the conditions are the skill.

On one node the BEAM already made the other bet. Processes share no memory and communicate by messages; there is no linearizable shared heap to argue about. The BEAM article is that model. Cross-node, the same isolation becomes a replica set, and the question is which histories you will tolerate when a message is late. The dining developers problem is the local version of that question: five processes, five forks, no global clock, and a plan that deadlocks because every participant’s local view is consistent with a global state that does not exist. Backpressure is the other local lesson that survives distribution: a replica that cannot say no will accept itself to death.

Where to go next

Dining Philosophers - coordination with no shared clock, as an exercise. The story is in the dining developers.
Process Ring - message order around a ring of BEAM processes.
What the BEAM actually is - isolation and mailboxes, the single-node version of “no shared memory.”
Backpressure - the local “no” that keeps a replica from drowning.
Hash tables - another slogan whose conditions are the actual claim.
Let it crash - failure as a signal, which is what a minority partition has to do under PC.
Publish-subscribe - delivery guarantees, the cousin of consistency on the event path.

Consistency models: what "strong" vs "eventual" actually buys you