Strong, Eventual, Bounded-Staleness, Session, and Tunable Consistency Models

Learning outcomes

“Strong” and “eventual” are not the only useful choices. AtlasMart can require a shopper to see their own profile edit without requiring every shopper worldwide to see it immediately; a search index can have an explicit freshness bound; an inventory reservation may require a single real-time order. This lesson names those contracts and uses histories to show which anomalies each permits.

1. A consistency model is a contract over histories

A history records operation invocations, responses, and their ordering. Consistency models constrain which histories are allowed. This viewpoint is powerful because clients care about what they can observe, not whether an internal dashboard says “replication healthy.”

2. Linearizability: one real-time order for the object

Herlihy and Wing define linearizability so each operation appears to take effect instantaneously at some point between invocation and response, while respecting real-time precedence. For a register, if write v8 completes before a later read starts, that later read cannot legally return v7. This property is stronger than “eventually replicas agree” and different from serializable transaction isolation, which orders transactions without necessarily respecting real-time order unless strengthened to strict serializability.

t1 client A: write address=v8 -------- OK
t2                                  client B: read address -> v8

INVALID after t1 completed:
t2                                  client B: read address -> v7

3. Eventual consistency: convergence is not a freshness guarantee

Eventual consistency says, roughly, that if updates stop and communication continues, replicas converge. It does not say how stale a read may be at a particular moment, whether a user sees their own write immediately, or whether a sequence of reads moves monotonically forward. Those stronger user-experience properties require additional guarantees.

4. Session guarantees: improve one user’s experience without global ordering

The classic Bayou session-guarantees work separates several useful guarantees. Read your writes means a session’s reads reflect its earlier writes. Monotonic reads means once the session has observed version 8 it does not later observe version 7. Monotonic writes preserves the session’s write order, and writes follow reads preserves dependencies from values the session observed.

A practical implementation may carry a session token, minimum version, logical timestamp, or causal context. If the preferred replica is too old, the client can wait, reroute, or fail instead of silently violating the session contract.

5. Bounded staleness and causal consistency

Bounded staleness makes freshness quantitative: for example, “no more than 30 seconds behind” or “no more than 100 versions behind,” depending on the system. The bound only means something if version/time metadata and monitoring can enforce it. Causal consistency preserves cause-before-effect relationships: if a product review refers to a newly created product, a client should not observe the review without the product version on which it depends. Concurrent independent updates need not have one universal order.

6. Tunable consistency is an API surface, not one universal model

Some databases allow a client to choose read/write acknowledgement levels per operation. That can change stale-read risk, latency, and failure behavior. But “QUORUM,” “majority,” or “strong” are product terms whose exact semantics depend on replication topology, read/write protocol, version selection, failover, and repair. Chapter 06 will analyze quorum overlap in detail; for now, never translate a setting name directly into a theorem-level guarantee without the protocol assumptions.

7. AtlasMart lab — enforce a session minimum version

from dataclasses import dataclass

@dataclass
class VersionedValue:
    value: str
    version: int

replicas = {
    "A": VersionedValue("old-address", 7),
    "B": VersionedValue("old-address", 7),
}

# User writes through A; B is intentionally left behind to model replication lag.
replicas["A"] = VersionedValue("new-address", 8)
session_min_version = 8

print("replica state after write:", replicas)
print("eventual read from B:", replicas["B"])

# Read-your-writes / monotonic-read style client rule:
def session_read(preferred):
    candidate = replicas[preferred]
    if candidate.version >= session_min_version:
        return preferred, candidate
    return "A", replicas["A"]  # reroute/wait/fail are all possible real implementations

print("session read preferring B:", session_read("B"))

# B catches up later.
replicas["B"] = VersionedValue("new-address", 8)
print("after convergence:", replicas)

Expected output

replica state after write: {'A': VersionedValue(value='new-address', version=8), 'B': VersionedValue(value='old-address', version=7)}
eventual read from B: VersionedValue(value='old-address', version=7)
session read preferring B: ('A', VersionedValue(value='new-address', version=8))
after convergence: {'A': VersionedValue(value='new-address', version=8), 'B': VersionedValue(value='new-address', version=8)}

The first read from B demonstrates an allowed stale observation under plain eventual consistency. The session_read rule refuses to move the same session behind its acknowledged version and reroutes to A. A real system could wait instead, return an error, or use a consistency token; the mechanism and failure mode must be documented.

8. Deliberately wrong approach — call every useful guarantee “strong”

If the architecture document says “profile reads need strong consistency,” the team may over-coordinate globally when the actual requirement is only “the editing user must see their own update.” Conversely, calling a payment ledger “eventual” because replicas converge can be dangerously weak if clients are allowed to observe reversals or duplicate effects that violate financial invariants. Precision lowers both correctness risk and unnecessary latency.

9. Production judgment and bridge

Write consistency requirements as forbidden histories: “after my profile update succeeds, my session cannot see the previous profile,” “search may be at most 30 seconds behind the catalog,” or “once an inventory reservation succeeds, later reservations must observe the reduced stock.” That language is testable and maps cleanly to routing, session tokens, freshness monitors, or stronger coordination.

The next lesson turns these model definitions into architecture decisions by starting from business invariants. The goal is not the weakest consistency label for its own sake; it is the least coordination that still makes unacceptable histories impossible or explicitly compensatable.

Authoritative references

• Herlihy & Wing — Linearizability — foundational global real-time consistency condition
• Terry et al. — Session Guarantees for Weakly Consistent Replicated Data — read-your-writes, monotonic reads, writes-follow-reads, and monotonic-writes guarantees
• Daniel Abadi — Consistency Tradeoffs / PACELC — context for latency/consistency choices beyond partitions