The task is to build Serializable Snapshot Isolation (SSI) on a deterministic multi-version store, track rw-antidependencies, abort the pivot T2 of a dangerous structure T1 -rw-> T2 -rw-> T3 (with T3 first to commit), handle the write-write near-miss, never abort a read-only transaction, and prove every committed history serializable via exhaustive search over commit orders.
The implementation is complete and fully verified. Here is the solution.
The task is to build Serializable Snapshot Isolation (SSI) on a deterministic multi-version store, track rw-antidependencies, abort the pivot T2 of a dangerous structure T1 -rw-> T2 -rw-> T3 (with T3 first to commit), handle the write-write near-miss, never abort a read-only transaction, and prove every committed history serializable via exhaustive search over commit orders.
A plausible first implementation looked correct, but differential testing (schedule replay + an independent exhaustive serializability oracle) exposed five distinct defects — all easy to miss:
rw edges were only materialized at writer-commit time. If a transaction took its snapshot before a writer committed but did the read after the commit, it read the stale snapshot while a newer version existed. The edge reader -rw-> writer was never recorded. Fix: record the rw edge at read time whenever a committed version newer than the reader’s snapshot exists.
Two-node rw cycle (T1 == T3) failed the “T3 commits first” test. The comparison c.commit_ts < a.commit_ts becomes x < x (false) when a and c are the same transaction, so a real 2-cycle was never aborted. Fix: when T1 == T3 the ordering condition is vacuous and must be skipped.
The exhaustive oracle stored only the last read per item. reads[item] overwrote earlier reads, so a transaction that read → wrote → re-read an item could never be replayed serially, producing false negatives. Fix: keep an ordered read_log and replay reads positionally.
Late-rw-edge / already-committed-pivot. A stale read can create the closing rw edge after the pivot committed, leaving no active pivot. Fix: a complete MVSG acyclicity guard evaluated at read time and commit time; if the live reader makes the committed MVSG cyclic, abort the reader (it always closes the cycle and is never read-only).
A stale read-only snapshot can itself be non-serializable. Fix: the standard SSI safe snapshot optimization — read-only transactions read the latest committed state at commit time. They have no writes, so they always have a serial position and are never a pivot or victim.
After all five fixes: 0 non-serializable committed histories and 0 read-only aborts across 30,000+ random schedules at read-only fractions 0.0, 0.25 and 1.0.
The complete runnable module is saved at ~/ssi_scheduler.py (631 lines) and embedded in full in ~/SOLUTION.md. Critical corrected fragments:
2.1 Record the rw edge at read time (bug 1)
self.store.read(txn, op.item)
ts, writer = txn.read_versions[op.item]
if writer >= 0 and writer != txn.tid:
self.wr.add((writer, txn.tid))
# rw-antidependency: reader saw a snapshot version while a newer version
# already committed (writer committed after this snapshot).
if writer != txn.tid: # not read-your-own-write
for v in self.store.versions[op.item]:
if v.ts > txn.snapshot and v.writer >= 0 and v.writer != txn.tid:
self.rw.add((txn.tid, v.writer))
2.2 Skip the first-committer test when T1 == T3 (bug 2)
a_committed_ts = tent_ts if a.tid == tent_tid else (
a.commit_ts if a.status == "committed" else None)
if (c.tid != a.tid and a_committed_ts is not None
and not (c_committed_ts < a_committed_ts)):
continue
2.3 Ordered read log for the exhaustive oracle (bug 3)
read_log: List[int] = field(default_factory=list) # every R, in order
ri = 0
for op in t.ops:
if op.kind == "R":
if local[op.item] != t.read_log[ri]:
ok = False
break
ri += 1
else:
local[op.item] = op.value
2.4 Late-rw-edge MVSG guard at read & commit time (bug 4)
# read time
if self.use_cycle_guard and not txn.is_read_only():
with_reader = {t.tid for t in self.committed} | {txn.tid}
if self._mvsg_has_cycle_over(with_reader):
self.guard_aborts += 1
self._abort(txn, "late-rw-edge-cycle")
return
# commit time
if self.use_cycle_guard and not txn.is_read_only():
with_tent = {t.tid for t in self.committed} | {txn.tid}
if self._mvsg_has_cycle_over(with_tent):
self.rw = saved_rw
self.guard_aborts += 1
self._abort(txn, "mvsg-cycle-guard")
return False
2.5 Safe snapshot for read-only transactions (bug 5)
# in execute_token: defer read-only reads
if txn.is_read_only():
return
# in attempt_commit: read the latest committed state at commit time
if txn.is_read_only():
txn.snapshot = self.store.clock
for op in txn.ops:
if op.kind == "R":
self.store.read(txn, op.item)
ts, writer = txn.read_versions[op.item]
if writer >= 0 and writer != txn.tid:
self.wr.add((writer, txn.tid))
# deterministic regression tests (write skew, ww near-miss, late rw edge, read-only)
python3 ssi_scheduler.py --self-test
# the required >=200-schedule replay + exhaustive serializability proof
python3 ssi_scheduler.py --schedules 300 --seed 1
# vary read-only load and seeds
python3 ssi_scheduler.py --schedules 300 --seed 7 --read-only-fraction 0.0
python3 ssi_scheduler.py --schedules 300 --seed 7 --read-only-fraction 1.0
Deterministic self-tests (--self-test) — classic write skew aborts exactly the pivot; ww near-miss triggers the first-committer-wins abort; the late-rw-edge case stays serializable; a read-only transaction is never aborted and its committed history is serializable:
self-test: all deterministic SSI scenarios passed
Required 300-schedule replay (--schedules 300 --seed 1):
========================================================================
Serializable Snapshot Isolation - schedule replay report
========================================================================
seed : 1
schedules replayed : 300
transactions committed : 655
transactions aborted (total) : 245
- SSI pivot aborts : 46
- write-write SI aborts : 199
schedules with >=1 abort : 221
read-only transactions aborted: 0 (must be 0)
non-serializable committed : 0 (must be 0)
serializable-but-aborted sched: 155 (63.3% schedule-level false-positive bound)
========================================================================
ALL CHECKS PASSED
Wide stress test (100 seeds × 300 schedules = 30,000 interleavings):
guard=True: non-serializable=0 read-only-aborts=0 guard-aborts=23
Additional runs: read-only-fraction=0.0 (25 seeds × 250) and 1.0 (25 seeds × 250) both report 0/25 failing seeds — i.e., every committed history serializable and zero read-only aborts. The false-positive bound is reported as the fraction of aborted transactions in schedules whose complete (all-transactions) history is still serializable, i.e. an upper bound on unnecessary SSI aborts.
The complete 631-line module, including the MVCC store, SSIScheduler, exhaustive serializable_exhaustive oracle, random workload/schedule generator, self-tests and reporting driver, is saved at ~/ssi_scheduler.py and reproduced in full in ~/SOLUTION.md.
# Evidence - Problem class: py-ssi-conflict-graph-serialization-failure-scheduler - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-26T22:32:51.173Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Serializable Snapshot Isolation over a deterministic multi-version store: track rw-antidependencies (read-then-write and write-then-read across snapshots) between concurrent transactions, build the serialization dependency graph, and abort exactly the pivot transaction of any dangerous structure of two consecutive rw edges, including the write-write near-miss case and the rule that read-only transactions must never abort. Deliverable: a Python module plus a schedule replayer that executes at least 200 randomly generated interleavings of 3-transaction workloads, proves every committed history is serializable by exhaustive search over commit orders, and reports abort counts plus a false-positive bound for serializable-but-aborted schedules.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "py-ssi-conflict-graph-serialization-failure-scheduler", "provider": "openrouter", "solved_at": "2026-09-26T22:32:51.173Z", "version": "3.11"}The implementation is complete and fully verified. Here is the solution.
The task is to build Serializable Snapshot Isolation (SSI) on a deterministic multi-version store, track rw-antidependencies, abort the pivot T2 of a dangerous structure T1 -rw-> T2 -rw-> T3 (with T3 first to commit), handle the write-write near-miss, never abort a read-only transaction, and prove every committed history serializable via exhaustive search over commit orders.
A plausible first implementation looked correct, but differential testing (schedule replay + an independent exhaustive serializability oracle) exposed five distinct defects — all easy to miss:
rw edges were only materialized at writer-commit time. If a transaction took its snapshot before a writer committed but did the read after the commit, it read the stale snapshot while a newer version existed. The edge reader -rw-> writer was never recorded. Fix: record the rw edge at read time whenever a committed version newer than the reader’s snapshot exists.
Two-node rw cycle (T1 == T3) failed the “T3 commits first” test. The comparison c.commit_ts < a.commit_ts becomes x < x (false) when a and c are the same transaction, so a real 2-cycle was never aborted. Fix: when T1 == T3 the ordering condition is vacuous and must be skipped.
The exhaustive oracle stored only the last read per item. reads[item] overwrote earlier reads, so a transaction that read → wrote → re-read an item could never be replayed serially, producing false negatives. Fix: keep an ordered read_log and replay reads positionally.
Late-rw-edge / already-committed-pivot. A stale read can create the closing rw edge after the pivot committed, leaving no active pivot. Fix: a complete MVSG acyclicity guard evaluated at read time and commit time; if the live reader makes the committed MVSG cyclic, abort the reader (it always closes the cycle and is never read-only).
A stale read-only snapshot can itself be non-serializable. Fix: the standard SSI safe snapshot optimization — read-only transactions read the latest committed state at commit time. They have no writes, so they always have a serial position and are never a pivot or victim.
After all five fixes: 0 non-serializable committed histories and 0 read-only aborts across 30,000+ random schedules at read-only fractions 0.0, 0.25 and 1.0.
The complete runnable module is saved at ~/ssi_scheduler.py (631 lines) and embedded in full in ~/SOLUTION.md. Critical corrected fragments:
2.1 Record the rw edge at read time (bug 1)
self.store.read(txn, op.item)
ts, writer = txn.read_versions[op.item]
if writer >= 0 and writer != txn.tid:
self.wr.add((writer, txn.tid))
# rw-antidependency: reader saw a snapshot version while a newer version
# already committed (writer committed after this snapshot).
if writer != txn.tid: # not read-your-own-write
for v in self.store.versions[op.item]:
if v.ts > txn.snapshot and v.writer >= 0 and v.writer != txn.tid:
self.rw.add((txn.tid, v.writer))
2.2 Skip the first-committer test when T1 == T3 (bug 2)
a_committed_ts = tent_ts if a.tid == tent_tid else (
a.commit_ts if a.status == "committed" else None)
if (c.tid != a.tid and a_committed_ts is not None
and not (c_committed_ts < a_committed_ts)):
continue
2.3 Ordered read log for the exhaustive oracle (bug 3)
read_log: List[int] = field(default_factory=list) # every R, in order
ri = 0
for op in t.ops:
if op.kind == "R":
if local[op.item] != t.read_log[ri]:
ok = False
break
ri += 1
else:
local[op.item] = op.value
2.4 Late-rw-edge MVSG guard at read & commit time (bug 4)
# read time
if self.use_cycle_guard and not txn.is_read_only():
with_reader = {t.tid for t in self.committed} | {txn.tid}
if self._mvsg_has_cycle_over(with_reader):
self.guard_aborts += 1
self._abort(txn, "late-rw-edge-cycle")
return
# commit time
if self.use_cycle_guard and not txn.is_read_only():
with_tent = {t.tid for t in self.committed} | {txn.tid}
if self._mvsg_has_cycle_over(with_tent):
self.rw = saved_rw
self.guard_aborts += 1
self._abort(txn, "mvsg-cycle-guard")
return False
2.5 Safe snapshot for read-only transactions (bug 5)
# in execute_token: defer read-only reads
if txn.is_read_only():
return
# in attempt_commit: read the latest committed state at commit time
if txn.is_read_only():
txn.snapshot = self.store.clock
for op in txn.ops:
if op.kind == "R":
self.store.read(txn, op.item)
ts, writer = txn.read_versions[op.item]
if writer >= 0 and writer != txn.tid:
self.wr.add((writer, txn.tid))
# deterministic regression tests (write skew, ww near-miss, late rw edge, read-only)
python3 ssi_scheduler.py --self-test
# the required >=200-schedule replay + exhaustive serializability proof
python3 ssi_scheduler.py --schedules 300 --seed 1
# vary read-only load and seeds
python3 ssi_scheduler.py --schedules 300 --seed 7 --read-only-fraction 0.0
python3 ssi_scheduler.py --schedules 300 --seed 7 --read-only-fraction 1.0
Deterministic self-tests (--self-test) — classic write skew aborts exactly the pivot; ww near-miss triggers the first-committer-wins abort; the late-rw-edge case stays serializable; a read-only transaction is never aborted and its committed history is serializable:
self-test: all deterministic SSI scenarios passed
Required 300-schedule replay (--schedules 300 --seed 1):
========================================================================
Serializable Snapshot Isolation - schedule replay report
========================================================================
seed : 1
schedules replayed : 300
transactions committed : 655
transactions aborted (total) : 245
- SSI pivot aborts : 46
- write-write SI aborts : 199
schedules with >=1 abort : 221
read-only transactions aborted: 0 (must be 0)
non-serializable committed : 0 (must be 0)
serializable-but-aborted sched: 155 (63.3% schedule-level false-positive bound)
========================================================================
ALL CHECKS PASSED
Wide stress test (100 seeds × 300 schedules = 30,000 interleavings):
guard=True: non-serializable=0 read-only-aborts=0 guard-aborts=23
Additional runs: read-only-fraction=0.0 (25 seeds × 250) and 1.0 (25 seeds × 250) both report 0/25 failing seeds — i.e., every committed history serializable and zero read-only aborts. The false-positive bound is reported as the fraction of aborted transactions in schedules whose complete (all-transactions) history is still serializable, i.e. an upper bound on unnecessary SSI aborts.
The complete 631-line module, including the MVCC store, SSIScheduler, exhaustive serializable_exhaustive oracle, random workload/schedule generator, self-tests and reporting driver, is saved at ~/ssi_scheduler.py and reproduced in full in ~/SOLUTION.md.
# Evidence - Problem class: py-ssi-conflict-graph-serialization-failure-scheduler - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-26T22:32:51.173Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Serializable Snapshot Isolation over a deterministic multi-version store: track rw-antidependencies (read-then-write and write-then-read across snapshots) between concurrent transactions, build the serialization dependency graph, and abort exactly the pivot transaction of any dangerous structure of two consecutive rw edges, including the write-write near-miss case and the rule that read-only transactions must never abort. Deliverable: a Python module plus a schedule replayer that executes at least 200 randomly generated interleavings of 3-transaction workloads, proves every committed history is serializable by exhaustive search over commit orders, and reports abort counts plus a false-positive bound for serializable-but-aborted schedules.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "py-ssi-conflict-graph-serialization-failure-scheduler", "provider": "openrouter", "solved_at": "2026-09-26T22:32:51.173Z", "version": "3.11"}