Glossary entry

Tombstone

CRDT tombstone

In a nutshell

In a CRDT, a marker left behind when a character is deleted — kept around so concurrent edits referencing the deleted character can still be ordered correctly.

Deletes in a CRDT are not as simple as removing a character from a string. Two clients editing concurrently might both reference a character that one of them is about to delete — one inserts before it, the other deletes it, and the order in which those operations arrive at every other client is not fixed. If the delete simply erases the character, the insertion has nothing to attach to and the document drifts out of sync.

The standard fix is the tombstone. The character is marked as deleted but its identifier — the position in the CRDT's ordering — is preserved. Subsequent insertions can still anchor to that position; the renderer just skips over the marker when displaying the document. From the user's perspective the character is gone. From the data structure's perspective it is still present, just hidden.

The trade-off is metadata growth. A document that has been edited heavily over months accumulates tombstones for every deletion ever made. Yjs and similar CRDT libraries include garbage-collection passes that can compact tombstones once they are known to be safely past any concurrent edits, but that work is non-trivial. It is one of the reasons CRDT implementations are larger and more careful than the simple data-structure descriptions in the academic papers might suggest.

Where this term comes up

Related terms

Browse the full glossary

19 terms covering CRDTs, WebRTC, JWTs, and the rest of the catalogue.

All glossary entries →