Consistency & Reconciliation

Why this module exists

Replication gives availability and low latency, but it introduces divergence: replicas may temporarily disagree on value, order, and freshness.

This module teaches how to:

• classify what a read guarantee actually means,
• quantify acceptable staleness,
• reconcile conflicting versions,
• enforce per-client session expectations.

Failure and timing model

Assume:

• messages can be delayed/reordered/dropped,
• replicas can lag independently,
• clocks are not perfectly synchronized,
• clients can retry and roam across replicas.

Design implication: "latest" depends on model and metadata, not intuition.

Three consistency lenses

For a single-key read, we reason with three models (strongest to weakest):

1. Linearizable Read observes the value of the latest completed write in real-time order.
2. Causal Read respects happens-before dependencies (causal context), but may miss unrelated concurrent writes.
3. Eventual No immediate ordering guarantee; replicas converge only over time.

Important: a read can be causal but not linearizable.

Worked intuition: linearizable vs causal

Suppose latest write at time t=20 has VC [4,1]. A read at t=22 returns VC [3,1].

• Not linearizable (misses latest visible write).
• Still causal if [3,1] dominates read context (dependencies satisfied).

Takeaway: causal protects dependency order, not recency.

Bounded staleness as an SLO

Bounded staleness converts consistency into a numeric policy.

Given:

• latestWriteTime
• allowed lag window
• replica AppliedTime

A replica is eligible if: latestWriteTime - AppliedTime <= window

Then select by latency among eligible replicas.

Operational nuance:

• if no replica is eligible, either fail fast or escalate to stronger path,
• when latest-write info is stale, your bound may be optimistic.

Anti-entropy reconciliation

Replicas exchange version metadata and repair divergence. Two common decision tracks:

1. Vector-clock relation
   • A dominates B
   • B dominates A
   • equal
   • concurrent conflict
2. LWW fallback Select by timestamp (with deterministic tie-break).

Vector clocks preserve causality; LWW preserves simplicity. Many systems combine both: detect conflict with VC, resolve deterministically via policy when needed.

Multi-version read repair

A quorum read can return multiple versions. Repair logic should:

• keep all non-dominated versions (multi-value register semantics),
• mark dominated replicas for repair,
• deterministically collapse exact VC duplicates when policy requires one winner.

Pitfall: treating concurrent versions as stale causes lost updates.

Session guarantees (client perspective)

Even with weak global consistency, client experience can be strong if session rules hold.

Core session guarantees:

• Read Your Writes (RYW): after I write, my reads never go backwards.
• Monotonic Reads (MR): my read sequence never regresses.
• Monotonic Writes (MW): my writes are applied in session order.
• Writes Follow Reads (WFR): writes reflect dependencies from prior reads.

These guarantees are often enforced via sticky routing + per-session metadata.

How these pieces fit in production

A common architecture pattern:

• fast regional reads with bounded staleness,
• anti-entropy repair in background,
• conflict detection via vector clocks,
• per-session guarantees at API gateway.

This gives low latency while preserving user-visible correctness.

Common implementation mistakes

• conflating causal with linearizable,
• comparing vector clocks without handling missing dimensions as zero,
• resolving VC conflicts purely by timestamp without explicit policy,
• repairing concurrent versions as if dominated,
• checking session guarantees without tracking dependency floor.

What you will build (progressive sequence)

1. Consistency model classifier Label each read with strongest satisfied model.
2. Bounded staleness planner Pick best low-latency eligible replica under a staleness budget.
3. Anti-entropy reconciler Produce VC relation + deterministic merge choice for each key.
4. Multi-version read repair planner Select surviving versions and stale replicas for repair actions.
5. Session guarantees analyzer (capstone) Evaluate whether a client trace satisfies RYW/MR/MW/WFR end-to-end.

By the end, you should be able to reason about both system-wide and client-local consistency behavior under realistic replication lag and conflicts.