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.