temporal-join-frontier-retraction

Answer

Done. The complete solution is at ~/temporal-join/SOLUTION.md, with the verified implementation and tests in the same directory.

Summary

Root cause (the real bug I found and reproduced): the B-record eviction frontier was derived only from the watermark/horizon (wm - W - H), ignoring not-yet-finalized A records. A pending A can sit as low as wm - W, so its matching B can be as low as wm - 2W. The naive rule evicts that B one step before the A finalizes, silently losing a valid match. TestPendingAMatchRetention fails on the naive version and passes after the fix.

Exact fix: keep all retained collections sorted by (TS, id), and compute the B frontier over all live A sources:

bMin = min( wm - H - W,          // future accepted A
            pending[0].TS - W,   // oldest un-finalized A
            final[0].TS  - W )   // oldest retained finalized A

Verified properties: - go vet clean, go test -race passes (10 tests). - Randomized tests compare against an independent brute-force batch join for W∈{0,1,3,7} × H∈{0,1,5,30}, so no valid match is lost. - Late corrections emit deterministic retract(old) → insert(new); beyond-horizon records are rejected before touching state. - TestBoundedState shows 10,000 events leave O(W+H) state.

Proof (in the doc): any B arriving after A's finalization must be late (b.TS < wm_f); acceptance gives b.TS ≥ wm_f − H, which forces a.TS + W + H ≥ wm_f, so a is still retained for correction. Evicted A/B records are provably more than W away from every future accepted record.