99 lines
3.8 KiB
Python
99 lines
3.8 KiB
Python
#!/usr/bin/env python3
|
|
"""evidence_run.py -- reproducible evidence for orcrdt; exit 0 iff all claims hold.
|
|
|
|
Prints, in one pass:
|
|
[A] random-gossip convergence over every seed, per CRDT family
|
|
[B] mutation teeth: each deliberately broken merge must be caught, and the real
|
|
class must pass exactly the seeds where its mutant failed
|
|
[C] differential agreement with an independently written reference model
|
|
|
|
Nothing here trusts the library: every line is recomputed from the simulation
|
|
harness in test_crdt.py, and the script's own exit code is the verdict.
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
import os
|
|
import platform
|
|
import random
|
|
import sys
|
|
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
|
|
import test_crdt as T # noqa: E402
|
|
from orcrdt import LWWRegister, ORSet, PNCounter # noqa: E402
|
|
|
|
FAMILIES = ((ORSet, T.ORSetDropsForeignTombstones),
|
|
(PNCounter, T.PNCounterDropsDecrements),
|
|
(LWWRegister, T.LWWLastArgumentWins),
|
|
(ORSet, T.ORSetNoOpMerge),
|
|
(PNCounter, T.PNCounterSumMerge))
|
|
|
|
|
|
def main():
|
|
failures = []
|
|
print("orcrdt evidence run")
|
|
print("python %s on %s" % (platform.python_version(), platform.system()))
|
|
print("seeds 0..%d, 3 replicas x 80 ops x 4 gossip rounds (5x150 for the big one)"
|
|
% (max(T.SEEDS),))
|
|
print()
|
|
|
|
print("[A] convergence: every replica equals the join of all pre-gossip states")
|
|
for real in dict.fromkeys(real for real, _ in FAMILIES):
|
|
passed = sum(1 for s in T.SEEDS if T.check_convergence(real, s))
|
|
big = all(T.check_convergence(real, s, n=5, ops=150, rounds=6)
|
|
for s in (0, 1, 2))
|
|
print(" %-12s %2d/%d seeds 5-replica ensemble: %s"
|
|
% (real.__name__, passed, len(list(T.SEEDS)),
|
|
"converged" if big else "DIVERGED"))
|
|
if passed != len(list(T.SEEDS)) or not big:
|
|
failures.append("convergence %s" % real.__name__)
|
|
print()
|
|
|
|
print("[B] mutation teeth: a broken merge must be caught by the same check")
|
|
for real, mutant in FAMILIES:
|
|
hits = T.mutant_detected(mutant)
|
|
real_ok = all(T.check_convergence(real, s) for s in hits)
|
|
value_wrong = any(not T.check_convergence_detail(mutant, s)["value_ok"]
|
|
for s in hits)
|
|
print(" %-32s caught at %2d/%d seeds; semantic divergence: %-3s; "
|
|
"real class green on those seeds: %s"
|
|
% (mutant.__name__, len(hits), len(list(T.SEEDS)),
|
|
"yes" if value_wrong else "no", "yes" if real_ok else "NO"))
|
|
if not hits or not real_ok:
|
|
failures.append("teeth %s" % mutant.__name__)
|
|
print()
|
|
|
|
print("[C] differential vs independent reference model (OR-Set)")
|
|
agree = 0
|
|
for seed in range(16):
|
|
rng = random.Random(seed * 31 + 5)
|
|
live = [ORSet("r%d" % i) for i in range(3)]
|
|
ref = [T.RefORSet("r%d" % i) for i in range(3)]
|
|
for _ in range(120):
|
|
i, elem = rng.randrange(3), rng.choice(T.ELEMS)
|
|
if rng.random() < 0.55:
|
|
live[i].add(elem)
|
|
ref[i].add(elem)
|
|
else:
|
|
live[i].remove(elem)
|
|
ref[i].remove(elem)
|
|
for dst, src in [(rng.randrange(3), rng.randrange(3)) for _ in range(60)]:
|
|
if dst == src:
|
|
continue
|
|
live[dst] = live[dst].merge(live[src])
|
|
ref[dst] = ref[dst].merge(ref[src])
|
|
if live[0].elements() == ref[0].elements() == live[1].elements() == live[2].elements():
|
|
agree += 1
|
|
print(" %d/16 seeds agree (both implementations, all replicas)" % agree)
|
|
if agree != 16:
|
|
failures.append("differential")
|
|
|
|
print()
|
|
print("FAILURES: %s" % (", ".join(failures) if failures else "none"))
|
|
return 1 if failures else 0
|
|
|
|
|
|
if __name__ == "__main__":
|
|
sys.exit(main())
|