FNP CRDT Conflict-Free Merge Semantics

ELI5

A CRDT (Conflict-free Replicated Data Type) is a data structure that automatically resolves conflicts without asking humans. When two people edit the same document offline and reconnect, the CRDT ensures both clients see the exact same result — no merge conflicts, no “Accept Yours or Theirs” dialogs. It’s like mathematical magic that makes document merging automatic.

Technical Deep Dive

Core CRDT Properties

A CRDT guarantees strong eventual consistency through three properties:

1. Commutativity: Operation order doesn’t matter

   INSERT("A") → INSERT("B") = INSERT("B") → INSERT("A")
   Both yield "AB"

2. Idempotence: Applying twice = applying once

   DELETE(position 3) applied twice = DELETE(position 3) applied once

3. Determinism: All replicas converge to identical state

   Replica A: [INSERT, DELETE, INSERT] → "ACE"
   Replica B: [DELETE, INSERT, INSERT] → "ACE"
   Same result, different order!

FNP’s CRDT: LSEQ

Positions are totally ordered:

Each position = [⟨digit, site, counter⟩, ⟨digit, site, counter⟩, ...]
Lexicographic ordering (compare left-to-right)

Example:
Pos A: [⟨5, site-1, 0⟩]
Pos B: [⟨10, site-2, 0⟩]
Pos A < Pos B (because 5 < 10)

Merge algorithm (pseudocode):

def merge(local_ops, remote_ops):
    all_ops = local_ops + remote_ops
    # Sort by position, break ties by (lamport_clock, operation_id)
    all_ops.sort(key=lambda op: (op.position, op.timestamp, op.id))

    result = ""
    for op in all_ops:
        if op.type == "insert" and not op.position.deleted:
            result += op.content
        elif op.type == "delete":
            mark_position_as_deleted(op.position)

    return result

All replicas execute this same merge, computing identical results.

Tombstone Handling

Deletions don’t remove data; they mark tombstones:

flowchart LR
    P1["Pos[1] = 'h'\n(live)"]
    P2["Pos[2] = 'e'\n(live)"]
    P3["Pos[3] = 'l'\n(tombstone)"]
    P4["Pos[4] = 'l'\n(tombstone)"]
    P5["Pos[5] = 'o'\n(live)"]

    P1 --> VIS["Visible text: 'heo'"]
    P2 --> VIS
    P3 -. "filtered out" .-> VIS
    P4 -. "filtered out" .-> VIS
    P5 --> VIS

    style P3 fill:#f87171,color:#fff
    style P4 fill:#f87171,color:#fff

Tombstoned positions are shown in red and connected with dashed edges to make it immediately clear that the positions still exist in the data structure — they are not removed. Solid edges from live positions to the visible-text node represent the only characters that surface to readers. This distinction is the core insight: tombstones preserve the position space so that future inserts between them remain deterministically ordered across all replicas.

Concurrent Insert Resolution

Scenario:

• Alice: inserts “X” at position 2.5
• Bob: inserts “Y” at position 2.5 (same logical location, offline)

Resolution:

• FNP allocates Alice “position 2.5.1” and Bob “position 2.5.2”
• After merge: sorted order deterministic (based on site ID or clock)
• Result: ”…XY…” or ”…YX…” but same order on all replicas

Key Terms

• CRDT → Conflict-free Replicated Data Type; guaranteed convergence without coordination
• Strong eventual consistency → All replicas eventually reach identical state
• Commutativity → Property that operation order doesn’t affect outcome
• Idempotence → Applying operation twice = applying once
• Tombstone → Deletion marker; keeps position space stable for future inserts

Q&A

Q: What if the network is partitioned and clients diverge forever? A: Impossible. The moment they reconnect, the merge algorithm deterministically converges them. Partition duration doesn’t matter — they’ll eventually see the same data.

Q: Can concurrent deletes cause conflicts? A: No. Both delete operations mark the same position as deleted. Merge algorithm sees “delete at position X” twice — idempotent, no conflict.

Q: How does CRDT handle “undo”? A: Undo is implemented as a new operation (not a reversal). Example: insert “X” at position 5, then insert tombstone at position 5. The delete operation is itself a CRDT operation, merged deterministically.

Examples

CRDT is like a set union: no matter what order you combine sets, the result is identical.

Set A (Alice): {apple, banana}
Set B (Bob): {banana, cherry}
Alice ∪ Bob = {apple, banana, cherry}
Bob ∪ Alice = {apple, banana, cherry}
Same result!

CRDT applies this logic to document edits.