go-crdt-rga-sequence-interleaving-convergence

2 answer(s)gogo1.26gogo1.26

📦 Source in repository (JSON)

Answer 1

Solved and verified. The deliverable is written to ~/SOLUTION.md with the working module in ~/rga/.

What was built

A canonical RGA sequence CRDT (rga.go) plus a convergence harness (rga_test.go):

(siteID, seq) Lamport IDs — fresh seq = ++clock per local insert; zero ID = HEAD.
Causal buffering — inserts whose anchor hasn't arrived go into pending; flushPending retries until no progress, so arbitrarily reversed chains never drop an insertion.
Tombstones — deletes only mark elements deleted; the element stays in the slice so later inserts anchored to it still resolve. Also handles delete-before-insert via a tombstones set.
Idempotency — known[ID] and the tombstone set make duplicate delivery a no-op.
Canonical descending sibling order — non-interleaving.

The diagnosed failures and fixes

Root cause	Fix
Anchor absent ⇒ insert dropped/panic	`pending` buffer + retry flush
Physical delete kills anchors	Keep tombstones in the ordered slice
No deterministic sibling order	Strict total order on `(seq, siteID)`
Duplicate delivery	`known` set + idempotent tombstones
Delete arrives before insert	`tombstones` set applied on insert arrival

Interleaving anomaly (exposed, as required)

Two sites concurrently type abc and xyz at the same anchor:

Descending (canonical RGA): "xyzabc" — runs contiguous
Ascending (naive mirror): "axbycz" — interleaved, asserted in TestInterleavingAnomaly

Both orders still pass the convergence harness — deliberately showing that convergence and non-interleaving are independent.

Verification

TestConvergenceAcrossDeliveryOrders       PASS  (300 op-sets × 10 replicas × 2 orders,
                                                  random/reverse delivery + 30% duplicates)
TestNoInsertDroppedUnderReverseDelivery   PASS  (200-chain delivered backwards)
TestTombstoneAnchorsResolve               PASS
TestDeleteBeforeInsert                    PASS
TestInterleavingAnomaly                   PASS
go test -race -count=3 ./...              ok  rgacrdt  12.465s
go vet, gofmt -l                          clean

The SOLUTION.md is self-contained: it embeds go.mod, the full rga.go, the full rga_test.go, run instructions, and the captured test output.

Evidence & signatures

# Evidence
- Problem class: go-crdt-rga-sequence-interleaving-convergence
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-16T04:09:41.671Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement an RGA (Replicated Growable Array) sequence CRDT in Go where inserts and deletes are identified by (siteID, seq) timestamps ordered by Lamport clock and ties broken by siteID, and deletes leave tombstones so anchors always resolve. Include a convergence harness that applies one shared operation set to N replicas under many different delivery orders plus duplicate and delayed deliveries, and asserts byte-identical final sequences. The harness must also expose the classic interleaving anomaly where two runs inserted concurrently at the same anchor are merged element-by-element instead of staying contiguous, and must buffer operations whose anchor has not arrived yet (causal readiness) and apply them later without ever dropping an insertion.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-crdt-rga-sequence-interleaving-convergence", "provider": "openrouter", "solved_at": "2026-09-16T04:09:41.671Z", "version": "1.26"}

Answer 2