State Sync and CRDTs
P2P systems are inherently eventually consistent: there is no central authority to serialize writes. This document covers the techniques for synchronizing mutable state across peers without conflicts.
The Consistency Challenge
In a centralized system, a database serializes all writes. In P2P, concurrent writes from disconnected peers are normal—in fact, the offline-first design pattern embraces it. Two fundamental approaches:
Avoid conflicts structurally: design data types so concurrent operations always commute—CRDTs.
Detect and resolve conflicts: use operational transform (OT), last-writer-wins (LWW), or manual resolution. Simpler to implement initially, but conflict resolution logic grows with application complexity.
Most mature P2P systems choose CRDTs or append-only logs (which avoid conflicts by construction).
CRDTs (Conflict-free Replicated Data Types)
CRDTs guarantee strong eventual consistency: all replicas that have seen the same set of operations (in any order) converge to the same state. No coordination needed—no locks, no consensus, no leader.
State-based CRDTs (CvRDTs)
Replicas exchange full state snapshots; a merge function (join of a semilattice) combines them idempotently. Merging is associative, commutative, and idempotent, so it doesn't matter how many times or in what order you merge.
Common state-based CRDTs:
GCounter (grow-only counter): each node increments its own entry in a map; the total is the sum. Used for distributed counters, view counts.
PNCounter (positive-negative counter): a pair of GCounters, one for increments and one for decrements.
GSet / 2P-Set: GSet is grow-only (add-only set); 2P-Set adds a tombstone set for removals (but elements can never be re-added after removal).
OR-Set (Observed-Remove Set): tracks unique tags per add operation, enabling add-wins semantics. The most practical set CRDT—elements can be added and removed freely.
LWW-Register (Last-Writer-Wins Register): each write carries a timestamp; the latest wins. Simple but relies on clock quality. Used by Syncthing for file conflicts.
LWW-Map: a map where each key is an LWW-Register.
Operation-based CRDTs (CmRDTs)
Replicas exchange operations (which must be delivered reliably, often causally ordered via PubSub). More bandwidth-efficient than exchanging full state, but the delivery requirements are stricter.
RGA (Replicated Growable Array): a sequence CRDT for collaborative text, using unique IDs per character and a causal tree structure. Enables real-time collaborative editing.
WOOT (WithOut Operational Transforms): another sequence CRDT that predates RGA.
Yjs, Automerge, Diamond types: modern CRDT libraries optimized for text editing and JSON-like document structures, combining ideas from RGA with practical engineering optimizations.
Delta CRDTs
Send only the delta (change) rather than full state, combining the efficiency of op-based delivery with the simplicity of state-based merging. Particularly useful for large data structures where full state exchange would be expensive.
Log Shipping and Anti-Entropy
Many P2P systems use a simpler primitive than general CRDTs: append-only logs where each peer has a single-writer log and conflicts are impossible within a log.
Append-only logs: each peer maintains an immutable, signed log of operations. Hypercore and SSB are built on this model. Conflicts only arise when combining multiple logs, which requires application-level merge logic.
Anti-entropy sync: peers exchange digests (e.g., Merkle tree roots, set-reconciliation sketches) to identify and transfer missing entries efficiently. This is how SSB gossip replication and IPFS Bitswap wantlists work.
Snapshotting and compaction: periodically collapse log history into a snapshot to bound storage. Hypercore's truncate operation trims old entries while preserving the Merkle integrity chain.
Multi-writer merging: Hypercore's Autobase combines multiple single-writer logs into a causally ordered multi-writer view, approaching CRDT semantics from the log-first direction.
State Sync in Practice
Matrix State Resolution v2: resolves conflicting room state events using authorization chains and power levels—a domain-specific conflict resolution algorithm.
Nostr: uses replaceable events (NIP-16) where the latest event by timestamp wins—effectively LWW-Register semantics.
Syncthing: file-level LWW with conflict copies created for simultaneous edits.
How State Sync Connects to Everything Else
CRDTs rely on Content Addressing for integrity of operations and state snapshots. Real-time Messaging provides the dissemination layer for operations and state. Identity attributes operations to authors and governs who can write. Design Patterns discusses offline-first and edge-first architectures that CRDTs enable. Storage must handle unbounded growth of operation logs. Security must protect against malicious operations that exploit CRDT merge semantics. Compliance faces the tension between append-only logs and data erasure requirements.
Do you like what you are reading? Subscribe to receive updates.
Unsubscribe anytime