A replica set (the same data kept on several of your devices at once) converges by adding. Two devices compare what they hold, and each ships what the other is missing. Both end up with the union: every row either one had. Deletion is the one operation that shape cannot express. From the outside, a row you deleted and a row you never saw look identical (both are simply absent), and the helpful answer to both is to send the row again. The fix is to stop deleting and start writing a row that says "deleted". That sounds like a dodge until you follow what it buys: a delete that only ever moves forward (monotonic), works whatever order updates arrive in (order-independent), and needs no new machinery at all.
Prerequisites: Clocks You Cannot Trust for the version vectors the editable namespaces merge with (per-device counters that record who has seen what), and Reconciling by Digest for the fingerprint-comparing pull round every tombstone rides.
Start with a trace, because the failure is not obvious until you watch it happen.
You have a phone and an iPad on the same account. Both hold the memory namespace, one of
the named buckets of synced data. This one is the append-only event log the agent reads:
append-only meaning rows are only ever added, never edited in place. (It is described in
Memory & the
Notebook.) One agent conversation in that log has four
MemoryEvent rows. Each row has a stable UUID (a random identifier minted once and never
changed), and each is tagged with the same conversationID.
On the phone you delete that conversation. The obvious implementation is exactly what you would guess: delete the rows. Four rows become zero on the phone while the iPad, asleep, still holds all four.
Later, both devices are awake and each advertises its digest, a short fingerprint of
everything it holds. The memory digests differ. The phone shares its (key, leafHash)
buckets: one entry per row, each row hashed down to a small fingerprint. The iPad compares
them against its own, finds four keys the phone lacks, and ships the four rows back. The
phone runs its merge (insert-if-absent), and the rows are on your screen again.
The phone's memory root (the top-level fingerprint over the whole namespace) now matches the iPad's. The system has converged. It has converged on the wrong value, and the conversation is back on your screen.
Notice who is at fault, because it is nobody. The iPad's responder does exactly the right thing: it compares its leaf set against the phone's, sees four keys the phone lacks, and ships them: the same code path that lets a sibling (another device on your own account) that was off for a week catch up. Re-shipping what a peer lacks is the responder's whole job.
The deeper point is that no amount of comparing the two sets can fix this. A comparison sees only what each side holds right now. "The phone lacks row r" is one fact, and two completely different histories produce it identically: the phone deleted r, or the phone has never heard of r. The interpretation lives in the history, and the history is not in the sets. The transport compares sets. So the information has to be put into the set, or it does not exist.
There is a second thing to see in that trace. The merge rule for this namespace is
insert-if-absent: in StateReconcile.applyMemory, an incoming row is dropped if its UUID
is already present, and inserted otherwise. That is the entire rule, because an append-only
log has no conflicts to resolve. Insert-if-absent means the merge computes a union.
Union is a beautiful operation to build a distributed system on. It is commutative, associative, and idempotent (order does not matter, grouping does not matter, and repeats do not matter), so it does not care which device pulls first, how many times a row arrives, or in what order. It has exactly one weakness. Union cannot shrink a set. A delete asks the system to do the one thing its merge operator is incapable of expressing.
If the only operation the transport implements is "add", then a delete has to be encoded as an addition. That is the whole idea, and everything else in this article is consequences.
A tombstone is an ordinary row whose meaning is "the thing named here is gone." In the
memory log it is a MemoryEvent like any other, with a kind the schema already had:
public static func tombstone(conversationID: UUID, at date: Date = Date()) -> MemoryEvent {
MemoryEvent(kind: .tombstone, body: "", occurredAt: date, conversationID: conversationID)
}
Empty body. Its own fresh UUID, so it is its own leaf, its own hashed entry in the digest
tree. The identifier of what it buries
travels in conversationID, the field the log already carries.
Now count what had to be built to make that sync. The digest builder, StateHash's
memoryLeaves, walks every MemoryEvent row and hashes it. It excludes message-kind and
calendar events; a tombstone is neither, so the marker is a leaf, and its arrival changes the
namespace root.
Divergence detection therefore notices it for free. The reconcile responder ships it as one more
row in a mismatched range. The applier inserts it if-absent, exactly like a journal entry. It
never touches the wire format: sync_delta carries the same reconcile_resp body it always
did.
So the answer to "what did the tombstone cost" is: one enum case that was already in
EventKind, and a reader. No new wire kind, no second merge operator, no branch in the
reconcile, and no redesign of the CRDT: the conflict-free
replicated data type, the merge structure that lets replicas combine their state without
coordinating.
The delete path in ChatView shows the ordering that matters:
modelContext.insert(MemoryTombstones.tombstone(conversationID: id))
let events = allEvents.filter { $0.conversationID == id && $0.kind != .tombstone }
for e in events { modelContext.delete(e) }
The marker goes in before the rows come out, and the filter is careful not to delete the marker it just wrote. The local deletes still run (they reclaim space), but they are no longer what makes the deletion real. The tombstone is.
Reading is a pure function over the log: the same log in, the same view out, nothing else
consulted. MemoryTombstones.live(_:) collects the buried
conversation ids, then returns the events minus the markers themselves and minus everything
they bury. Every consumer of the log goes through it rather than filtering by hand, so that
"deleted" means one thing everywhere: ChatView for what you see,
HuddleContextRetriever for what the agent packs into a huddle,
SagaService for what gets summarised.
Two properties fall out of that design, and together they are the proof that it works.
A tombstone is monotonic. Once inserted it is never un-inserted. No ordinary code path removes a memory tombstone event; the reconcile only ever inserts. Each device's tombstone set can therefore only grow, and it grows toward the union of everyone's, carried by the same insert-if-absent path as the data. There is no window in which the marker is absent again and the buried rows are visible again.
A tombstone is order-independent. live(_:) computes the buried set from the whole log
first, then filters. It never asks when a row arrived. So a row that a sibling re-ships
long after the tombstone converged is buried the moment it lands, and a tombstone that
arrives long after the rows it buries takes effect the moment it lands. The test suite
pins exactly this, in both directions:
#expect(MemoryTombstones.live([tombstone, resurrected]).isEmpty)
#expect(MemoryTombstones.live([resurrected, tombstone]).isEmpty)
Now the convergence argument, which you can do in your head. Let device A hold event set
E_A and device B hold E_B. The pull round is insert-if-absent and is run independently
from both ends, so after they exchange, both hold E_A ∪ E_B: union, so it does not matter
who pulled first or whether both pulled at once. The visible state is live(E), a pure
function of that set. Same set in, same view out. The two devices agree.
That is why the tombstone needs no coordination, no timestamp comparison, and no leader. It converts a request the merge operator cannot serve ("remove this") into one it serves natively ("add this"), and it moves the deletion semantics from the storage layer, where order and timing bite, to the read layer, where they cannot.
Follow the trace from §1 again with the marker in place. The phone tombstones and deletes its four rows. The iPad still holds them and re-ships them, and the phone still re-inserts them, because nothing in the applier consults the tombstone set. The rows come back to disk.
They do not come back to the screen, on either device, ever. And the iPad, which pulls the marker on its own next round, buries its copies too. §8 returns to what that means, because "converged and invisible" is not the same claim as "erased."
The memory log is append-only, so its rows are immutable and a marker row is a natural fit.
Four namespaces are not like that: notebook, saga, plans and contacts hold rows you
edit on more than one device, and they merge causally: each row carries a version vector in
a RowVersion bookkeeping row, and a merge asks whether one side's history dominates the
other's (has seen everything the other side saw, and more) or whether the two are
concurrent, neither having seen the other (this is
Clocks You Cannot Trust).
You cannot bury a note with another note. So the tombstone goes where the row's causal
history already lives: RowVersion outlives the row it describes. It is keyed by
(namespaceRaw, rowKey), holds the vector, and holds a tombstoned flag.
Detection does not live at every site that deletes. RowClock.observe runs at the ModelContext.didSave
chokepoint: the one notification the local store fires after a batch of writes commits,
whatever code made them. It diffs the live rows against the RowVersion entries and closes
with one loop:
for (key, e) in entries where !e.tombstoned && !liveKeys.contains(key) { // deleted
bump(e, deviceID); e.tombstoned = true; e.syncedAt = .distantPast; changed = true
}
A key with bookkeeping and no row is a deletion. Before the flag is set, the vector is bumped on the deleting device's own counter. That is what makes the tombstone dominate what the sibling holds: the sibling's copy carries the vector this device had just seen, and this device's is now strictly ahead of it. Deletion is a causal event like any other edit.
The transfer has a subtlety worth deriving, because it is the kind of thing that looks like
over-sending until you see why it is not. A reconcile response ships rows for the key ranges
whose Merkle fingerprints (hash-tree
summaries, one per range of keys) did not match. But it
attaches the entire tombstone set for the namespace, unscoped. The comment in
StateReconcile.respond explains: a tombstone's key is in no live leaf, so the range comparison
(computed over live leaves only) can never flag it.
Suppose you scoped the tombstones to the mismatched ranges instead. The keys deleted on both sides fall into ranges that match perfectly, because neither side holds them live. Their tombstones would never travel, and the two devices' vectors for those keys would stay permanently different. A third sibling that later re-ships a live copy of such a key could then resolve it differently on each device. Shipping the whole set closes that hole by construction, and it costs nothing real: applying a tombstone twice is the same as applying it once (it is idempotent), and deletes are rare.
On the receiving end, applyTombstones deletes a local row only when the incoming tombstone
causally dominates the local copy. Either way, it records the merged vector, so both sides'
histories converge whether or not the row went.
It is tempting to summarise all of this as "delete-wins." That is not what the code does, and the difference is the interesting part.
Where causality can decide, causality decides. VersionVector.resolveMerge returns .delete
only when the incoming tombstone's vector dominates the local vector. When the two are
genuinely concurrent (a device deleted a note while another device was editing it, neither
having seen the other), the rule is add-wins: the live value beats the tombstone, and the
note comes back.
case (false, true): return (.adopt, merged) // add-wins: live beats tombstone
case (true, false): return (.keep, merged) // add-wins: keep our live value
That is deliberate, and it is the weaker of the two available rules on purpose. A delete that happened after seeing your edit should destroy it: you deleted the thing you were looking at. A delete that happened without seeing your edit is not a decision about your edit at all, and silently discarding work nobody knew existed is the worse error. A surviving note is recoverable; a destroyed one is not.
Where causality cannot decide (a tie in a namespace that has no vectors), deletion is the side chosen. Three instances, all in the same shape:
peerDevices (a contact's roster of their own devices) merges last-writer-wins on the
owner's lastAdvertisedAt (the later write simply overwrites the earlier, with no causal
history consulted), and an exact tie resolves revoke-wins.fileIndex merges last-writer-wins on indexedAt, and an exact tie resolves delete-wins.And peerDevices records a rejected alternative worth reading twice. It is not causal, and
the architecture notes say why: causal add-wins would resurrect a device the owner deliberately
dropped, the instant a stale advertisement raced the drop.
That namespace has a single writer (the contact owns their own roster), so there is no concurrent-edit case to protect and nothing add-wins would buy, only a hole. The same rule that is right for your notebook is wrong for someone else's device list, and the deciding question is not "which rule is safer" but "who writes this row."
Messages get their own fold (a replay that rebuilds a message's current state by applying its
operations in order), and here deletion is absolute. MessageFold ranks delete scope
everyone (2) above me (1) above live (0), and the stronger scope always wins. And (the
line that matters) a row with any delete scope stops accepting edits entirely:
if row.deletedScope != nil { return changed }
// 2) Edit LWW.
Messages are event-sourced: what you see is not a stored value but the result of folding an
append-only set of
immutable MessageOp rows. Edits among themselves are last-write-wins on
(editedAt, editOpID): the newest edit wins, and the op id breaks a same-second tie by
comparing bytes the way words sort alphabetically, so every
device picks the same winner. Deletes do not join that ordering. They dominate it. Three
independent reasons force that direction, and any one of them alone would be enough.
The content is gone. A delete:everyone purges the plaintext: row.body = "",
row.mediaJSON = nil. If a later edit could win, the fold would have to converge on content
that no longer exists on the device that deleted it. An absorbing state (one a row can
enter but never leave) is the only consistent one once you have destroyed the material.
The digest would never converge. A deleted row's leaf is canonicalised (reduced to one
fixed form) down to identity alone:
messageID, directionRaw, postedAt, and the scope. MessageFold also clears
editedAt and editOpID on delete. Derive why: those fields are hashed into the messages
leaf. A device that edited a message and then deleted it would hold editedAt = T, while a
device that only ever saw the delete would hold editedAt = nil. Both agree the message is
deleted, yet their digests would differ forever, re-triggering a reconcile that can never
resolve anything. Making the delete absorbing and canonical is what stops a row everyone
agrees about from diverging on the details of how it got there.
Deletion has a second escape route that is not sync at all. An undelivered outbound
message keeps a cooperative-delivery duty: any device of yours that holds one keeps trying
to send it. If a delete did not dominate, deleting a message that had not yet gone out would
leave the retry machinery cheerfully delivering it. reconcileOutboxDuty closes that by
deriving the duty from the folded row rather than from independent per-device state:
if row.isDelivered || row.deletedForEveryone {
for item in existing { modelContext.delete(item) }
Because the duty is a pure function of the (already-converging) messages namespace, a
delete that converges to a sibling also cancels that sibling's obligation to send. The recall
rides the same convergence as the deletion.
One more property comes from the ops being immutable. An op can arrive before the message
it targets: routine when the relay, the server that forwards sealed frames between devices,
keeps no mailbox and every device retries
on its own. Such an op is stored as an orphan with applied == false and folded in when its
target lands, and pending ops are folded in (opTime, opID) order rather than the order they
arrived. Order-independence again, one layer down.
There is a class of state that tombstones cannot save, and the way it was handled is instructive.
Calendar events were once synced as memory events. Every device re-derives them from EventKit (the system calendar store, which every device already has its own copy of) on a schedule. Each pass, the ingester deletes its window of rows and re-inserts them with fresh UUIDs. Under insert-if-absent that is a machine for making duplicates: each device mints new ids every cycle, ships them, and receives everyone else's just-deleted rows back. The memory root never converged: a permanent reconcile storm.
A tombstone does not fix that. The identifiers being buried are regenerated with new values on every pass, so the marker set would grow once per ingest cycle and never catch what it was chasing.
The problem is not that deletion is hard to express; it is that this state is derived, and derived state that is cheap to recompute has no business in a replicated set at all. So calendar events were excluded from the memory digest outright, and each device owns its own view, with EventKit as the source of truth on each of them.
The rule that generalises: a tombstone is for state whose identity is stable and whose loss is real. For state that any device can regenerate from a local source, the correct move is to keep it out of the shared set.
Four limits, and none of them are small print.
A tombstone is a durable record that something existed. Deleting a conversation leaves a
row saying "a conversation with this UUID was deleted, at this time," on every device,
permanently. The marker carries no content (body is empty by construction), so what leaks
is existence, count, and timing, not substance. It is only reachable by someone who can read
a device's decrypted store, since the relay sees only ciphertext (encrypted bytes) that it
cannot attribute to anything. It is still
a real property, and it is the direct price of the design: the only way to make an absence
travel is to make it a presence, and a presence is a record.
In the memory namespace, deletion is invisibility, not erasure. As §3's trace showed, a
sibling that still holds the buried rows re-ships them and the deleting device re-inserts
them, because the applier does not consult the tombstone set. The source anticipates this
exactly: a resurrected row stays hidden because the tombstone converges too. So the
guarantee on offer is a read-time one, and it is honestly stated. The consequence is still
worth naming: the plaintext of a "deleted" agent conversation can persist on disk on every
device in the fleet, filtered out of every read. The causal namespaces do not behave this
way (applyTombstones genuinely deletes the local row), so how thoroughly a delete removes
data currently depends on which namespace you deleted from.
Deleting for everyone is best-effort at the peer. delete:everyone ships an op to a
person running their own copy of the software. The fold does the right thing on an honest
client, and there is no way to make it do the right thing on a dishonest one. delete:me
does not even try: it sends the op only to your own sibling devices (a self-echo), and the
peer keeps its copy, which
is the honest version of the same promise.
Tombstones accumulate without bound. Every one of them is retained indefinitely by
default, and the retention is not laziness: it is the safe baseline, because a delete cannot
resurrect while its tombstone is present. The RowVersion tombstones have exactly one
collection path, RowClock.dropAllTombstones, and it runs only as the terminal step of an
explicit fleet-wide agreement. Memory tombstone events and deleted message rows have no
collection path at all today.
Which sets up the question this chapter leaves open. Dropping a tombstone is only safe once every device has provably absorbed the delete. And "provably" is the hard word, because the obvious evidence (a digest that looks caught up, an ack that might be stale) is exactly what resurrects rows. That is The Convergence Barrier and the Cloud Anchor, and it is the hardest problem in this series.