Reclaiming tombstones: deletion needs stable knowledge

In the simple retained-history OR-Set, an old add tag remains harmless because every receiver that knows its tombstone treats it as removed. If a replica drops the tombstone but still accepts the old add from another participant, the element can become visible again. Deleting the local add record as well does not solve the general problem: an offline peer or delayed message may retain it. Before compacting, account for every allowed source of stale history, including durable queues, restored snapshots, and clients that synchronize after a long absence.

A safe design can retain compact causal context that proves the old event was observed and removed, establish a stable delivery boundary under fixed membership, or fence old histories through an epoch and require returning replicas to resynchronize. These are different mechanisms. A compressed representation without explicit tombstones is not automatically one without historical knowledge. Likewise, dropping a replica from the current membership list is unsafe if its old messages remain admissible under the same identities and protocol rules.

Under fixed membership, suppose each replica reports a prefix frontier of operations it has durably applied. Taking the componentwise minimum gives a frontier known to have been applied by every member, provided acknowledgments are truthful, monotone, and scoped to the same history. An event below that frontier has reached all those members. Message stability, meaning every member applied an event, is weaker than causal stability in some operation-based protocols, where no future delivered operation is concurrent with that event. Whether its tombstone can be removed additionally depends on the type’s protocol: delayed messages must be rejected or interpreted using retained context so that forgetting one record cannot reenable a removed event.

A minimum over only reachable members gives a different claim. An offline member omitted from the calculation may still have an old add and no corresponding removal. Dynamic membership therefore needs a defined reconfiguration and state-transfer protocol. A rejoining actor that lost its counters must not silently reuse its previous identity. Epoch fencing can prevent old state from participating, but the fence has to be checked on messages and restored storage, not merely documented in an operator runbook.

Database tombstone grace periods are practical policies that depend on repair, outage, and restoration assumptions. Cassandra documents the need to coordinate tombstone removal with repair to avoid deleted data returning. This is not a claim that every CRDT uses Cassandra’s mechanism. For your own protocol, specify the maximum supported offline interval, repair coverage, accepted snapshot epochs, and the rule for rejecting or rebuilding stale replicas. Monitor violations of those assumptions rather than treating the configured number of seconds as a correctness theorem.

Use the reliability lab to separate reachable majorities from universal knowledge. Reset, set replica count n=3 and unavailable count k=1, predict two up with a majority threshold of two, then Step. A majority is available, but the absent third replica may still hold old state. The lab counts availability only; it has no tombstones, acknowledgments, epochs, or reclamation algorithm. Changing k does not prove that everyone learned a deletion. The worked frontier calculation supplies the stronger evidence required under its stated membership model.