quorum-read-witness-repair

Answer

The bug is in the read path of the W=2/R=2 coordinator, in two places. Both live in read(), and the write path is unchanged (broadcast to all 3 replicas, commit when ≥ W ack — a partitioned replica silently misses writes, which is how it falls behind).

Bug 1 — winner selection. The coordinator returns the first R responses (arrival order) instead of the highest-version response. When a read quorum lands on the primary (fresh) and one stale replica, and the stale replica answers first, the stale value is returned even though the fresh value was sitting in the R responses:

# BUG: responses[0] is first *arrival*, not highest version
winner_replica, (winner_value, winner_version) = responses[0]

Bug 2 — repair predicate. Repair only rewrites replicas whose version vector is exactly equal to the winner's — a no-op. The lagging replica's version {A:1} is a strict prefix (dominated) of the winner's {A:3}, never equal, so it is never repaired and serves stale reads indefinitely. Concurrent writes keep the leader's counter ahead, so the version never becomes equal "by chance" either:

# BUG: equality-only — fires only when there is nothing to fix
if ver == winner_version:
    r.put(key, winner_value, winner_version)

The fix (in FixedCoordinator):

def _highest(responses):
    """Maximal element of the version-vector partial order."""
    best = responses[0]
    for r, (val, ver) in responses[1:]:
        if ver.dominates(best[1][1]):      # FIX 1: highest version wins
            best = (r, (val, ver))
    return best

def read(self, key, response_order=None):
    responses = self._collect(key, response_order)   # up to R responses
    if len(responses) < self.R:
        raise RuntimeError("read quorum not reached")
    winner_replica, (winner_value, winner_version) = self._highest(responses)
    repaired = []
    for r, (val, ver) in responses:
        # FIX 2: repair on dominance (strict prefix), not equality
        if ver != winner_version and winner_version.dominates(ver):
            r.put(key, winner_value, winner_version)
            repaired.append(r.name)
    return winner_value

with the version-vector predicate:

def dominates(self, other):
    """self >= other componentwise and self != other  (other is a strict prefix)."""
    if self == other:
        return False
    return all(self.counters.get(k, 0) >= v for k, v in other.counters.items())

{A:3}.dominates({A:1}) is true, so the fresh primary is the witness proving C stale, and C is overwritten with the winner's value/version. An absent key responds with an empty version vector — a strict prefix of everything — so it is backfilled too. Concurrent versions (neither side dominates) are deliberately not overwritten, so read repair never clobbers a divergent write.

Demo (partition C during v2/v3, heal, read with C answering first):

[BUGGY coordinator]  read returned 'v1'  (winner=C)   C stays VV{'A':1}  -- stale forever
[FIXED coordinator]  read returned 'v3'  (winner=A, repaired=['C'])  C -> VV{'A':3}  -- converged