CRDTs

What It Is

CRDTs (Conflict-free Replicated Data Types) are data structures designed so that conflicts are machine-resolvable -- when two nodes make different changes simultaneously, deterministic rules resolve the disagreement without human intervention. The merge is mathematically guaranteed to converge to the same result on all nodes, regardless of the order operations are received.

"Conflict-free" doesn't mean conflicts don't happen. It means the data structures carry enough context (vector clocks, operation history) that pre-defined rules can always determine the right outcome. No leader election. No locking. No coordination. Each node modifies its local copy freely. When copies meet (via gossip, direct sync, or any other channel), they merge and the result is identical everywhere.

Why It Matters

In a distributed system, you have two options when nodes disagree:

Prevent disagreement: Use a consensus protocol (Raft, Paxos) to ensure all nodes agree before any change. Requires a majority to be reachable.
Resolve disagreement automatically: Let nodes change freely and merge later. Requires data structures with well-defined merge semantics.

CRDTs are option 2. They're essential for systems that must operate during network partitions -- both halves of a split org can continue making changes, and when they reconnect, the CRDTs merge cleanly.

How It Works

The Key Insight

A CRDT defines a merge operation that is:

Commutative: merge(A, B) = merge(B, A) (order doesn't matter)
Associative: merge(merge(A, B), C) = merge(A, merge(B, C)) (grouping doesn't matter)
Idempotent: merge(A, A) = A (merging with yourself changes nothing)

These three properties mean that no matter how many times, in what order, or through what path merges happen, the result is the same. This is what makes CRDTs "conflict-free" -- there's no state where merge produces an ambiguous result.

CRDTs as a Class, Not a List

"CRDT" is a property of a data structure, not a specific implementation. Any data structure whose merge operation is commutative, associative, and idempotent IS a CRDT. The types below are well-known examples, but you can design your own: if it merges correctly, the label applies. If your merge has a caveat that breaks one of the three properties (e.g., "merge only works if applied in order"), it's not a CRDT -- it's something else that needs additional coordination.

Some common CRDT types:

G-Counter (Grow-only Counter): Each node has its own counter. To increment, a node increments its own entry. The value is the sum of all entries. Merge takes the max of each entry. Can only grow -- no decrement.

PN-Counter (Positive-Negative Counter): Two G-Counters: one for increments, one for decrements. The value is increments minus decrements. Merge applies G-Counter merge to both.

G-Set (Grow-only Set): Elements can be added but never removed. Merge is set union. FortrOS uses this for revocation lists -- once revoked, always revoked.

Orswot (Observed-Remove Set Without Tombstones): Elements can be added and removed. Uses causal context to track which additions a removal has observed. If an element is added on one node and removed on another concurrently, the add wins (add-wins semantics). FortrOS uses this for org membership.

MVReg (Multi-Value Register): Stores a single value that can be overwritten. If two nodes write different values concurrently, both values are preserved (like a git conflict). The application decides how to resolve. FortrOS uses deterministic resolution (sort values, pick the first) for node metadata.

Map: A key-value map where each value is itself a CRDT. FortrOS uses Map<String, MVReg<HostMeta>> for per-node metadata -- each node's metadata is an MVReg that merges independently.

Example: Concurrent Edits

Two nodes (A and B) are disconnected. Both modify the org membership:

Node A: adds "node-X" to membership
Node B: removes "node-Y" from membership

-- reconnect --

Merge result: membership contains "node-X" (added by A)
              and does NOT contain "node-Y" (removed by B)

No conflict. The Orswot tracked both operations independently and the merge is deterministic. If both had added the same node, the Orswot deduplicates. If both had removed the same node, the Orswot handles it idempotently.

How FortrOS Uses It

OrgOperational (tree 0x01):

Orswot<String> for membership (add/remove nodes)
Map<String, MVReg<HostMeta>> for per-node metadata (status, zone, endpoints)
GSet<String> for revocations (irreversible)

OrgConfig (tree 0x02):

Org-wide settings (replication factor, policies, feature flags)
Precondition-based conflict resolution

WorkloadDesired (tree 0x03):

What workloads should run, their specs, placement constraints

WorkloadObserved (tree 0x04):

Actual workload status reported by reconcilers on each node

All state trees use StateTree<T> which wraps the CRDT with a Merkle tree for efficient divergence detection.

Alternatives

Raft consensus: Total ordering, strong consistency, but requires a majority. Used by etcd, CockroachDB. FortrOS rejected this because the org must survive arbitrary partitions.

Operational Transformation (OT): Used by Google Docs for collaborative editing. Transforms operations based on concurrent operations. More complex than CRDTs and harder to prove correct.

Last-Writer-Wins (LWW): Simplest "conflict resolution" -- the write with the highest logical counter wins. Easy to implement but loses data (concurrent writes are silently discarded). Depends on a total ordering, which in many systems means wall-clock timestamps -- fragile in distributed environments where clocks drift. FortrOS avoids LWW for shared state. For self-authoritative data (a node's own metadata), only the owning node writes, so there are no concurrent writes to resolve.