Answer

Verified end-to-end. The complete self-contained markdown solution is saved at ~/SOLUTION.md (44 KB, with both source files embedded byte-for-byte), and the working code is at ~/mvcc_ssi.py with tests at ~/test_mvcc_ssi.py.

Below is the solution write-up.

---

MVCC Serializable-Snapshot-Isolation Validator with Predicate Anti-Dependency Cycle Resolution

Root-cause analysis

Snapshot isolation is not serializable. Its anomalies come from anti-dependencies (rw): T reads a version and a concurrent W later writes that key/range. A history is serializable iff the serialization graph (wr, ww, rw) is acyclic. Naive implementations fail because:

1. Heuristic SSI over-aborts — the dangerous structure T1 →rw T2 →rw T3 is necessary but not sufficient for a cycle. Aborting on it rejects acyclic histories. You must detect actual cycles.
2. Predicates are intervals, not keys — scan([lo,hi)) conflicts with any overlapping write; per-key tracking explodes or misses overlaps under adversarial ranges.
3. Wrong wr visibility — a reader sees the latest committed writer per sub-range at its snapshot. Painting every overlapping writer invents edges and false cycles.
4. Commit races — two transactions can each pass validation yet together close a cycle; validation + edge insertion must be atomic.
5. Serial wraparound — fixed-width IDs/timestamps need modular comparison and a live-window invariant < half the space.
6. Vacuuming — a committed record may only be dropped once commit_ts <= min(active start_ts); otherwise cycles are missed.
7. Bounded memory — coalesce intervals exactly; cap per-txn intervals and retained transactions, aborting deterministically under pressure.

The fix

The validator keeps read/write interval sets (RangeSet, exact normalized unions), a serial clock with modular comparison, and a committed-transaction graph. At commit it computes, against every retained committed transaction:

• wr predecessors using a RangeMap that paints the latest visible writer over each read sub-range,
• rw successors (committing txn read a version; the other wrote later) and rw predecessors (the other read; the committing txn wrote),
• ww predecessors (overlapping writes).

A cycle exists iff some successor can already reach some predecessor. Commits are serialized by a re-entrant lock; the deterministic victim is the committing transaction (or the oldest active transaction under memory/window pressure). Vacuuming uses the watermark min(active start_ts); wraparound maintains a live span below 2**(bits-1).

Key interface:

v = MVCCValidator(bits=64)
t = v.begin()
v.read(t, 0, 10)          # predicate read of [0, 10)
v.write(t, 5, 6)          # write key 5
v.commit(t)               # True (committed) / False (aborted on cycle)

The full implementation (module, interval primitives, serial clock, GC, fuzzer harness) is in ~/SOLUTION.md §2 and in ~/mvcc_ssi.py.

Verification

$ python3 -m pytest test_mvcc_ssi.py -q
418 passed in 0.31s

The strongest check is test_differential_fuzz: random schedules are run through the real validator and compared decision-by-decision against an independent point-based oracle that rebuilds the graph from explicit per-key sets and independently DFS-checks acyclicity.

over 5000 fuzz schedules: {'calls': 42653, 'commits': 39929, 'aborts': 2724}
5000 seeds OK (no validator/oracle mismatches, all committed graphs acyclic)
gc=True:  mismatches=0
gc=False: mismatches=0

So 2,724 genuine cycle aborts were reproduced exactly, with zero false positives and zero false negatives. Targeted tests cover write skew, range overlaps, unbounded predicates, a cycle containing a wr edge, an acyclic dangerous structure that must not abort, concurrent commit races, 8-bit wraparound, vacuumed versions, adversarial interval coalescing, and bounded memory.

Reproduce:

cd ~
python3 -m pytest test_mvcc_ssi.py -q
python3 - <<'FUZZ'
import sys; sys.path.insert(0, '~')
from test_mvcc_ssi import _run_schedule
for s in range(5000):
    assert not _run_schedule(s), s
print("5000 seeds OK")
FUZZ

Artifacts: ~/SOLUTION.md (self-contained markdown), ~/mvcc_ssi.py, ~/test_mvcc_ssi.py.

# Evidence
- Problem class: python-mvcc-ssi-predicate-lock-cycle-resolution-20261013
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-13T10:14:10.739Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement an MVCC transaction validator that tracks read and write intervals across range scans, detects serialization cycles involving predicate anti-dependencies, and aborts a deterministic victim without rejecting acyclic histories. Handle concurrent commit races, transaction-ID wraparound, vacuumed versions, and bounded memory while preserving correctness under adversarial range overlap.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-mvcc-ssi-predicate-lock-cycle-resolution-20261013", "provider": "openrouter", "solved_at": "2026-10-13T10:14:10.741Z", "version": "3.11"}