CRDTs (Real-time Collaboration)

Merge rules are part of the data model

A conflict-free replicated data type defines updates and merges so replicas that receive the same information converge under the algorithm's assumptions. “Conflict-free” means the merge has a defined outcome; it does not mean that outcome satisfies every business rule or preserves every user's intention.

A shared set of bookmarks is a useful example. Two people can add different bookmarks offline, then union the sets on reconnect. Reserving the last seat on a flight is different: two independent reservations can exceed capacity even if their records merge perfectly.

A grow-only set you can reason about

class GrowOnlySet:
    def __init__(self, values=()):
        self.values = set(values)

    def add(self, value):
        self.values.add(value)

    def merge(self, other):
        self.values |= other.values

left = GrowOnlySet(["paper-a"])
right = GrowOnlySet(["paper-b"])
left.merge(right)
right.merge(left)
assert left.values == right.values == {"paper-a", "paper-b"}

Set union is commutative, associative, and idempotent: order, grouping, and repeating the same merge do not change the set membership. Python's display order is not part of that guarantee. The example works for hashable values and intentionally has no removal operation.

Why a normal delete breaks the design

If one replica simply deletes an element while another still has it, the next union brings it back. An observed-remove set records unique add identifiers and which identifiers a removal observed. The removal suppresses those additions; a concurrent, previously unseen addition can survive under add-wins semantics.

That is why a map that deletes a key and later unions maps is not an observed-remove CRDT. Tombstones or an equivalent causal representation carry information that an ordinary delete discards. Removing that metadata safely requires additional knowledge about replica progress.

State-based and operation-based designs

There is no universal rule that all CRDTs require causal delivery or that all ignore ordering. Read the chosen algorithm's assumptions and the library's update protocol.

A grow-only counter is another state-based design: each replica increments its own component, merges by component-wise maximum, and sums components for the visible count. Replica identifiers must be unique and increments nonnegative. Sharing an identifier or allowing arbitrary negative increments breaks that model.

Collaborative text needs more than a linked list

Concurrent inserts need stable identifiers and a deterministic placement rule. Deletions must survive later merges. Cursor positions, undo, rich-text marks, and deleting a parent object introduce further semantics. A linked list with timestamps and an empty “rebuild order” function does not implement a convergent text CRDT.

Yjs documentation describes shared types and synchronization updates. A library helps with the merge algorithm, but authentication, persistence, transport, and recovery remain application responsibilities. A public room name is not an access-control policy.

Test the merge, then test the product behavior

For a small set, generate additions and repeat updates in several orders. Every replica should end with the same membership. For an observed-remove set, separately test an observed add followed by a removal and an unobserved concurrent add. They need different expected outcomes.

For text, simulate two offline editors, reconnect them in both orders, and compare document state. Then ask whether users can understand the result. Technical convergence does not decide whether two conflicting edits should both be shown or one should be flagged for review.

Sources and related concepts

The research-maintained CRDT introduction links the underlying studies and distinguishes decentralized CRDTs from centrally coordinated collaboration systems. A familiar product name alone is not evidence that the product uses a particular CRDT.

See database replication, distributed transactions, and WebRTC for the surrounding storage and transport decisions.