CAP and Consistency Models

Consistency models specify which execution histories a client is allowed to observe. Before discussing "reading new data," we must clarify objects, operations, client ordering, and completion times; before discussing "availability," we must clarify whether we are referring to the termination property in a mathematical model or the actual service success rate and latency targets.

CAP: Conflicts Arise Between Specific Failure Models and Guarantees

The "C" in CAP usually refers to linearizability of atomic read/write registers; "A" requires that operations reaching non-faulty nodes eventually complete; "P" indicates that the model allows messages between nodes to be blocked by partitions. "A" does not have a uniform millisecond latency upper bound, nor is it satisfied by simply returning an error page to fulfill the completion contract of service operations.

If arbitrarily long network partitions are allowed, it is impossible to guarantee both such "C" and "A" simultaneously. This does not mean architects can arbitrarily choose two letters, nor does it imply that all real-world networks will inevitably experience some fixed form of partition on a certain day. Perspectives on the CAP Theorem

Assuming x is initially 0 and there are no other writes, the write of 1 on A has succeeded, and subsequently B receives a read request. B cannot distinguish via messages between the world where "the other side finished writing 1" and the world where "the other side never wrote," yet it must provide an answer consistent with the history. Waiting indefinitely also fails to satisfy the termination requirement in a partition that never recovers.

A system may continue to complete certain strong consistency operations on the majority side while rejecting or waiting on the minority side; or it may allow local updates for specific business logic and merge them after recovery. CAP does not require the entire product to permanently select the same letter label across all interfaces.

Linearizability: Operations Appear to Take Effect Instantaneously Between Call and Return

For an object's operation history, if each completed operation can be placed at a specific point between its call and return such that the resulting execution order conforms to the object's specification, the history is linearizable. If A has returned before B calls, A must precede B; operations that overlap in time can be arranged in any valid order.

For example, if read(x) is called only after write(x=1) returns, and there are no other writes, the read must return 1. If the read and write overlap, returning either the old value 0 or the new value 1 may be legal, depending on the position of the linearization point. Therefore, saying "reads always return the latest value in terms of wall-clock time" is inaccurate.

Linearizability is a constraint on observable behavior; it does not mandate the use of a leader, a specific number of network round-trips, or that all physical replicas complete the application at the exact same instant. Implementations can provide this behavior through different replication and read protocols.

Sequential Consistency: Preserves Per-Client Order, Does Not Necessarily Preserve Real-Time Order Across Clients

Sequential consistency requires the existence of a global order that conforms to object semantics and preserves the order of operations for each process, but it does not require preserving the order produced solely by real-time completion relationships between different clients.

For example, Client A sequentially writes x=1, then x=2; Client B subsequently reads 1 in real time. Looking only at this history, it might be interpreted as the logical order "write 1, read 1, write 2," which satisfies sequential consistency but violates the linearizability requirement that reads occurring after the second write has completed must see the new value.

This does not mean messages in reality can travel backward in time, nor does it imply that any asynchronous replica read satisfies sequential consistency. If the same client reads 2 first, then reads 1, with no other writes, this cannot be explained by a monotonically written history that preserves its read order.

Turning the Definition into a Small History Checker

Record four pieces of information for a register initially set to 0: client, operation type, written value or read result, and the event positions of the call and return. These positions come from a known sequence of events on the same machine, not from directly sorting uncalibrated wall-clock times from different machines. Each client has only one in-flight operation at a time, and all records have successful returns.

During checking, first sort the operations, then perform two filters: whether the order satisfies the required precedence relationships; and when executing in this order, whether each read equals the register's current value. Sequential consistency only adds precedence constraints within the same client; linearizability also adds all non-overlapping constraints across clients.

from dataclasses import dataclass
from itertools import permutations

@dataclass(frozen=True)
class Op:
    client: str
    kind: str
    value: int
    start: int
    end: int

def witness(history, linear=True):
    assert all(o.kind in ("W", "R") and o.start < o.end for o in history)
    # Teaching input requires serial calls from the same client, with unambiguous event positions.
    for i, a in enumerate(history):
        for b in history[i + 1:]:
            if a.client == b.client:
                assert a.end < b.start or b.end < a.start
    edges = [(i, j) for i, a in enumerate(history)
             for j, b in enumerate(history)
             if a.end < b.start and (linear or a.client == b.client)]
    for order in permutations(range(len(history))):
        position = {op: rank for rank, op in enumerate(order)}
        if any(position[i] >= position[j] for i, j in edges):
            continue
        value = 0
        for i in order:
            op = history[i]
            if op.kind == "W":
                value = op.value
            elif op.value != value:
                break
        else:
            return order
    return None

stale = [Op("A", "W", 1, 0, 1), Op("A", "W", 2, 2, 3),
         Op("B", "R", 1, 4, 5)]
assert witness(stale, linear=False) == (0, 2, 1)
assert witness(stale, linear=True) is None

# Read/write overlap: both return values have legal explanations, but this doesn't mean any value can be returned.
for result in (0, 1):
    overlap = [Op("A", "W", 1, 0, 5), Op("B", "R", result, 2, 3)]
    assert witness(overlap) is not None
assert witness([Op("A", "W", 1, 0, 5), Op("B", "R", 2, 2, 3)]) is None

# B reads 2 then 1, which cannot fit into a single valid total order with A's monotonically increasing writes.
backward = stale[:2] + [Op("B", "R", 2, 4, 5), Op("B", "R", 1, 6, 7)]
assert witness(backward, linear=False) is None
assert witness([]) == ()

The first group returns (0, 2, 1), placing B's read between A's two writes. It preserves A's program order but ignores the fact that the second write had already returned in reality. The last group has no solution even allowing such rearrangement: reading 2 requires it to be placed after writing 2, while the subsequent read of 1 requires going back before writing 2, forming a cycle in the constraints.

The number of permutations checked by this checker grows factorially, so it is only used for understanding small histories with a few operations. The existence of a witness is sufficient to show that this complete history satisfies the selected constraint; passing the check does not prove that all executions of the implementation are correct. Real testing also needs to handle unknown results after timeouts, operations that have not yet returned, object specifications, and history collection errors. In particular, timed-out writes should not be directly deleted from the history, as they may have already taken effect. Herlihy & Wing: Linearizability

Which orders can explain this history?

Turn consistency into a concrete question: does any operation order satisfy both precedence and register semantics? Keep A’s two writes ordered, and vary B’s read interval and result below. A sequential-consistency witness explains a history; it does not move physical events into the past. Switching constraints leaves the actual timeline unchanged.

Causal Consistency: See Dependencies Before Seeing Their Dependent Results

A publishes an article, B reads the article and replies; the reply depends on the article. If an observer can see the reply, the system should satisfy the corresponding causal visibility requirements, avoiding scenarios where the reply is seen but the version of the article it depends on is not. Concurrent operations with no causal relationship do not necessarily need to adopt the same order for all observers.

Causal relationships stem from process ordering, reading a specific write, and their transitive closure. Whether cross-service messages or user session switches are included in the causal context is part of the API and implementation contract. Simply attaching Lamport timestamps or using version vectors does not automatically create a complete causally consistent read service.

Session Guarantees: First Protect a Single User's Continuous Experience

Read-your-writes requires that subsequent reads in a session do not miss related writes that the user has already completed; monotonic reads require that the state observed by a session does not regress to an older history; other session guarantees also constrain the propagation order of continuous writes and read-then-write sequences.

These guarantees have clear scopes. Ensuring a browser session satisfies read-your-writes does not mean all other users immediately see its modifications. When a session migrates to another node, it may need to carry a progress token and wait for the target to catch up.

Eventual Consistency: Describes Convergence, Does Not Promise Intermediate Behavior

Under conditions where updates have stopped and necessary information can continue to propagate and merge, replicas eventually converge. This promise alone does not specify how long convergence takes, nor does it dictate whether prior reads regress, how conflicts are resolved, or whether business updates might be overwritten.

Eventual consistency can be provided alongside session guarantees and causal guarantees; it should not be mechanically arranged into a single scale of strength. Whether to use Last-Writer-Wins (LWW), CRDTs, or application-level merging also requires additional explanation; see Conflict Resolution.

Transaction Isolation and Object Consistency Are Different Problems

Serializable requires that the effect of multiple transactions be equivalent to some serial transaction order. Strict serializability further requires that this order respect real-time precedence. Having single-key operations be linearly consistent does not automatically compose a "read balance, then transfer" across keys into an atomic transaction.

Similarly, an API option named "serializable" should be read according to its product definition. For example, etcd's serializable read option allows stale reads and cannot be directly inferred based on SQL isolation level names.

Even If Every Operation Is Linearly Consistent, an Increment Can Still Be Lost

Suppose two clients both want to increment a counter by 1, but implement it using independent read, local addition, and write. The service can execute all single operations in the order shown in the table below, with each return satisfying the register specification.

There is no violation of linear consistency for single read/write operations here, but the two business increments have resulted in only 1. The solution is to make the increment itself an atomic operation, or use CAS/transactions with version conditions and re-read/calculate after conflicts. Adding retry counts to normal writes does not automatically turn them into atomic increments.

If CAS is used, both A and B initially carry version v0; after A succeeds, the version becomes v1, and B's v0 condition must fail. B then reads the value 1 and v1, recalculates to get 2, and attempts to commit again. This also illustrates that the object being checked must align with business promises: verifying only the underlying register history does not yet verify the composite operation constructed by the caller.

Quick Reference and Engineering Trade-offs

PACELC reminds us to also look at latency and consistency choices when no partition occurs, but it is not a law that "all strong consistency operations add a fixed 1–2 RTT." Geographic layout, leases, caching, batching, and read paths all change the actual cost.

It is best to write out specific histories during review: which write has succeeded, when the read started, which connections failed, and what can be returned. This guides interface design better than labeling the entire database as CP or AP.

References

• Perspectives on the CAP Theorem.
• etcd API Guarantees.
• Time and Clocks, Fault Models.

Keywords: CAP, PACELC, linearizability, sequential consistency, causal consistency, eventual consistency, serializability