FA-75122 / CRDT convergence / Member archive
Tombstone garbage collection by causal stability: one acknowledgement suffices to purge · case 02
Tombstones are purged while some replicas have not yet seen the deletion, so those replicas later resurrect the element.
Case contract
Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.
Why this case matters
Sequence and set CRDTs can only discard tombstones once every replica is guaranteed to have seen the deletion.
One recorded failure
Sample boundary fixtureThis sample comes from the broken implementation of a controlled reproducer.
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| one lagging member blocks | {"kept": [], "purged": ["x", "y", "z"]} | {"kept": ["z"], "purged": ["x", "y"]} | Failed |
MEMBER ARCHIVE
The complete case is available to members.
This record includes three runnable implementations, regression fixtures, execution results, and source hashes.
Member access is invitation-based. Sign in with your invited account to inspect the sources.
Sign in to the archive ↗