PROPERTY // 01
Commutativity
merge(A, B) = merge(B, A). Updates can arrive in any arbitrary order across network hops without altering the final converged state. Packet reordering by routers causes zero divergence.
Chapter 01 // Distributed Primitives
Synchronization & CRDT Topologies
When multiple independent nodes mutate document states concurrently without central lock orchestration, mathematical guarantees must ensure all peers reach identical states regardless of network latency, message interleaving, or packet drops.
Algebraic Foundations
The Bounded Semilattice Properties
For any two replicas to converge deterministically after merging incoming state updates, the merge function must satisfy three fundamental algebraic properties.
PROPERTY // 02
Associativity
merge(merge(A, B), C) = merge(A, merge(B, C)). Grouping of synchronization packets does not alter outcomes. Batched sync bundles compute identical values to single-message broadcasts.
PROPERTY // 03
Idempotence
merge(A, A) = A. Receiving the exact same update twice (duplicate packets, retry loops, dropped acknowledgments) does not duplicate data or trigger accidental state duplication.
State-Based vs. Operation-Based vs. Delta-State CRDTs
State-Based (CvRDT): Nodes transmit their entire monotonic state payload during sync. Extremely simple and fault tolerant, but payload sizes grow proportionally with history unless compaction runs.
Operation-Based (CmRDT): Nodes transmit discrete atomic operations (e.g., insert(char, id, origin)). Requires an underlying causal messaging transport.
Delta-State (d-CRDT): The modern standard used by Yjs and Automerge. Nodes track mutations since their peer's last known state vector, transmitting only compact binary diffs.
Topological Architectures
Network Topologies for Local Sync
How local nodes discover peers, stream binary deltas, and maintain partition resilience across varied network environments.
TOPOLOGY // A
Untrusted Star Relay (WebSocket Hub)
Clients connect to an ultra-lightweight, zero-knowledge WebSocket relay server (such as Cloudflare Workers or an Elixir cluster). The relay never executes application business logic or parses payloads; it simply echoes authenticated, encrypted binary deltas to matching room subscribers.
- • NAT Traversal: 100% reliable across cellular and corporate firewalls
- • Cloud Footprint: Negligible RAM/CPU overhead; byte streaming only
- • Failure Mode: Clients buffer locally if relay disconnects
TOPOLOGY // B
True Peer-to-Peer Mesh (WebRTC DataChannels)
Nodes discover peers on the local LAN using mDNS or broadcast beacons, or across the internet via transient STUN/TURN signaling. Once paired, data updates flow directly from machine to machine with zero intermediation.
- • Privacy: Complete transport sovereignty; packets never traverse third-party servers
- • Air-Gapped: Works seamlessly in offline disaster zones and local subnets
- • Constraint: Symmetric NAT pairs require TURN relays for signaling
Conflict Resolution Taxonomy
Data Structures & Resolution Behaviors
Different data domains demand different merge semantics. A collaborative text document requires character preservation, while an account balance requires scalar summation.
| Data Structure | Primitive Type | Resolution Strategy | Common Use Case |
|---|---|---|---|
| PN-Counter | Scalar Integer | Monotonically increasing Positive/Negative vector summation | Likes, upvotes, inventory tallies, page counters |
| LWW-Register | Atomic Value | Highest Lamport timestamp with client-UUID tiebreak | User profile avatar, title changes, toggle flags |
| MV-Register | Multi-Value | Preserves all concurrent conflicting values for user triage | Medical records, high-stakes accounting entries |
| OR-Set | Collection | Unique tag attached to each element; Add takes precedence over Delete | Tags, collaborative to-do items, multi-select lists |
| YATA / Fugue | Sequence / Tree | Deterministic interleaved character insertion tree without tombstone bloat | Rich text editors, source code, collaborative canvases |
| Merkle Search Tree | Key-Value Store | Content-addressed balanced prefix tree for logarithmic diff reconciliation | Syncing multi-gigabyte client databases efficiently |