Consistency & Reconciliation

A read can be fresh, satisfy a client's dependencies, or preserve concurrent versions. Those are different questions. Work with componentwise vector comparison first: [2,1] strictly dominates [1,1], but [2,0] and [1,1] are concurrent. Missing dimensions are zero; equality is not strict dominance.

What the classifier can establish

StrongestConsistency uses a deliberately small, single-key trace model: write times stand in for completed writes, and read times for observation points. There are no invocation/response intervals, overlapping operations, or object semantics. The labels classify each read by the exercise's rules; they do not certify an implementation or prove eventual convergence from a finite trace.

Actual linearizability asks whether an entire concurrent history admits a legal sequential order respecting completed-before-started operations. See the original linearizability paper. Here, the eventual label is simply the fallback when stronger checks fail.

Use writes in this input order:

Input index	Time	VC	Role
0	20	[3,0]	valid
1	10	[1]	valid; input is unsorted
2	20	[2,1]	wins the equal-time tie
3	25	[-1,5]	invalid; never visible

For a read at time 22, latestVC=[2,1]. A returned [2,1,0] is therefore linearizable in this model. Returning [3,0] with context [1,0] is causal: it is an actual visible version and covers the dependency floor. Returning [2,0] with that same context is eventual: dominance alone does not prove the value ever existed. Returning [3,0] with context [2,1] also fails: the second dependency is missing.

The classifier tests equality with latest first. Do not silently change that priority when a synthetic read context is inconsistent with the write history. Malformed read vectors always take the fallback. In a real history, such inconsistent inputs would need validation before drawing consistency conclusions.

Choose freshness before latency

BoundedStalenessRead takes a shared logical timestamp scale, not independently trusted wall clocks. With latest write 100 and window 5:

Replica	Applied	Latency	Staleness	Eligible
1	94	2	6	no
2	96	12	4	yes
3	98	12	2	yes
4	110	20	0	yes, lag is clamped

Choose replica 3: among eligible replicas, latency wins first, then staleness, then ID. Replica 1's attractive latency cannot override the bound. If the window becomes 1 and replica 4 is unhealthy, fallback chooses replica 3 by staleness first, then latency and ID. With fallback disabled, return the none plan. A negative window admits no bounded candidates.

If mathematical lag exceeds MaxInt, report MaxInt but keep the candidate ineligible for bounded mode, even with a MaxInt window. Saturation is an output representation rule, not permission to weaken the bound. Compare the full mathematical lag when ordering fallback candidates.

Detect a conflict before resolving it

ReconcileKeys returns both a causal relation and a policy decision. Suppose A has (VC=[2,0], timestamp=8, node=a, value=red) and B has (VC=[1,1], timestamp=10, node=b, value=blue). Neither dominates. Relation is conflict; the course's timestamp/node policy selects B and repairs A if their payloads differ. Choosing B does not retroactively make B causally newer.

With equal timestamp/node tuples and different payloads, return merge-required. With equal normalized VCs, this exercise returns equal without automatic repair, even if payloads disagree. That is a deliberate boundary of this planner; it is not a general corruption-resolution policy. A tombstone is part of the payload and must participate in those comparisons.

Preserve the non-dominated frontier

The multi-version task uses a different policy: preserve concurrent winners. Do not transplant LWW from ReconcileKeys into MultiVersionReadRepair.

Replica	VC	Value	Outcome
0	[1,0]	old	dominated by 1 and 2
1	[2,0]	red	winner
2	[1,1]	blue	winner
3	[2,0,0]	red	duplicate of winner 1

Winners are [1,2]; repairs are (0,1) and (3,1). In this API, FromReplica names the stale/duplicate replica and ToReplica names the winner it should fetch from. The names describe a request direction; copying bytes runs from the winner back to the stale replica.

If replica 3 instead contains green, it survives alongside 1 despite equal VCs: equal metadata does not authorize discarding different payloads. A repair action to one dominating winner also does not by itself install the full multi-version frontier. This is a planning exercise, not a complete replica store.

Keep session high-water marks

SessionGuarantees uses scalar versions per key. Keep the maximum prior read and maximum prior write, with separate presence flags because versions can be negative. Check before raising the relevant floor.

Index	Operation on cart	Read floor after	Write floor after	First new failure
0	write 7	absent	7	none
1	write 3	absent	7	MW at 1
2	read 5	5	7	RYW at 2
3	read 2	5	7	MR at 3
4	write 4	5	7	WFR at 4

A failed write must not lower the earlier write floor. Once a guarantee fails, its first violation index is permanent. Operations on another key do not inherit cart's floors. This scalar model omits cross-key causal dependencies.

Reconstruct and transfer

Before opening the continuation, classify a read at time 15 returning [1,0] with context [1] in the first history. Then add replica 5 with VC [3,1] to the repair history and predict the winner set.

Check the reasoning

At time 15 only the write at 10 is visible, so the read receives the course's linearizable label. Replica 5 strictly dominates every original repair candidate, so it becomes the sole winner. This follows from componentwise comparison, not from comparing sums of components.

Implement the five tasks in order. For independent transfer, construct a history where a read passes RYW but fails MR, and explain why sticky routing alone cannot prove either guarantee after a replica restart. Revisit with a two-key dependency: identify what metadata this scalar session API cannot express.