Two families, by how replicas sync
CRDTs fall into two families, depending on what replicas send each other.
- State-based CRDTs send their whole state, and the receiver merges it with its own. The merge must be commutative, associative and idempotent.
- Operation-based CRDTs send each change as an operation, and every replica applies it. Concurrent operations must commute, and the network must deliver each operation once and in causal order.
A third variant, the delta CRDT, is state-based but sends only the part of the state that changed. The CRDT glossary notes that the old names, convergent (CvRDT) and commutative (CmRDT) replicated data types, have given way to “state-based” and “operation-based”. The merging article explains why each family converges.
The more practical question is what kind of data the CRDT holds. The comprehensive study by Shapiro, Preguiça, Baquero and Zawirski sets out a portfolio of types, from simple to complex.
Counters and registers
A counter is a number that replicas increment and decrement. The value should end up equal to all increments minus all decrements, wherever they happened.
- A G-Counter (grow-only) keeps one entry per replica. Each replica increments only its own entry, a merge takes the larger value per entry, and the value is the sum.
- A PN-Counter combines two G-Counters, one for increments and one for decrements, and reports the difference.
A register holds a single value that is replaced on each write. Two concurrent writes cannot both stand, so the type has to choose.
- A last-writer-wins (LWW) register attaches a timestamp to each write and keeps the higher one. The study suggests a per-replica counter combined with a unique replica identifier, so ties break the same way everywhere.
- A multi-value (MV) register keeps every concurrent value and lets the application or a person reduce them to one with a later write.
Sets
Adding and removing items do not commute, so the study shows that a replicated set can only approximate an ordinary set. Each design states what wins when one replica adds an item while another removes it.
- G-Set: add only. Merging is set union.
- 2P-Set (two-phase): a removed item goes into a tombstone set and can never be added again.
- LWW-element-Set: each add and remove carries a timestamp, and the later one decides.
- OR-Set (observed-remove), also called an add-wins set: each add gets a unique tag, and a remove deletes only the tags it has seen, so a concurrent add survives.
- Remove-wins set: the opposite choice, where a concurrent remove takes precedence.
Maps and JSON documents
A map holds keys whose values can themselves be CRDTs. Kleppmann and Beresford describe a JSON CRDT with arbitrarily nested maps and lists, where each leaf value is a multi-value register. In their design, two replicas that create the same key with values of different types, such as a map on one side and a list on the other, keep both rather than forcing one into the other.
The same paper shows a limit of keeping every edit. If one replica deletes a to-do item while another marks it done, the merge brings back an item with no title, because the “done” field survived the deletion.
Automerge, which grew out of this research, models a document as a root map containing maps, lists, text, counters and simple values. Offline Protocol’s replicated documents offer four collection types: Map (last writer wins per key), List (concurrent insertions survive in deterministic order), Text (character-level merging) and Counter (increments accumulate).
Sequences for lists and text
A sequence is an ordered list in which people insert and delete elements at any position. Collaborative text is a sequence of characters. Positions shift as others type, so sequence CRDTs give each element a unique identifier and place new elements relative to existing ones instead of by index.
- RGA (Replicated Growable Array) stores the sequence as a linked list. Each element’s identifier is a timestamp, and concurrent inserts at the same spot are ordered by timestamp. Automerge’s lists use an RGA sequence.
- Treedoc and Logoot place elements in a dense identifier space, held as a tree, where a new identifier can always be made between two existing ones.
- WOOT, a design for concurrent editing, corresponds to the study’s add-remove partial order.
- YATA is the algorithm that Yjs adapts for its shared types.
Automerge builds its text type on Peritext, which adds formatting marks such as bold to a character sequence.
In RGA, deleting an element leaves a tombstone, so that an insert made concurrently next to it still has a reference point. The study reports that tombstones accumulate over time, and they can only be collected safely once every concurrent update has been delivered.
| Type | Example designs | When two replicas change it concurrently |
|---|---|---|
| Counter | G-Counter, PN-Counter | All increments and decrements count |
| Register | LWW, multi-value | One value wins, or all values are kept |
| Set | G-Set, 2P-Set, OR-Set | The design says whether add or remove wins |
| Map | JSON CRDT maps | Different keys merge; the same key follows the value type’s rule |
| Sequence | RGA, Treedoc, YATA | Both insertions are kept, in an order every replica agrees on |
Real applications compose these types, which is why a merge function for a whole document is built from the merge rules of its parts.