FNP LSEQ CRDT Identifiers

ELI5

Each character in an FNP document gets a unique address like “5.1.0, then 10.2.3” that nobody can duplicate. The clever part is that these addresses automatically sort in the right order without any central authority assigning them. If two people insert at the same place offline, they get different addresses that sort consistently on everyone’s computer.

Technical Deep Dive

LSEQ Position Structure

LSEQ (LogootSplit CRDT) assigns positions as variable-length tuples:

Position = [⟨digit, site, counter⟩, ⟨digit, site, counter⟩, ...]

Example position:
[⟨5, site-alice, 0⟩, ⟨10, site-bob, 3⟩]

Components:

• digit ∈ [0, BASE) — allocation digit (typically BASE=32 or 64)
• site — unique replica identifier (UUID or agent ID)
• counter — monotonic per-site clock (prevents duplicates)

Allocation Algorithm

When Alice inserts between positions P1 and P2:

def allocate_position(p1, p2, allocations_count):
    if can_fit_between(p1, p2):
        # Find middle ground
        new_digit = (p1.digit + p2.digit) // 2
        return p1 + [⟨new_digit, site-alice, alice_counter⟩]
    else:
        # No space between p1 and p2; append a new level
        return p2 + [⟨0, site-alice, alice_counter⟩]
        alice_counter += 1

Depth Analysis:

• First N insertions: depth ~log(N) levels (like binary tree)
• Position space: BASE^depth (with BASE=32, depth=3 → 32,768 unique positions)
• Growth: O(log N) average depth for N insertions

Encryption Digit-by-Digit

Positions can be encrypted with M²-ORE digit-by-digit:

Position: [⟨5, site-1, 0⟩, ⟨10, site-2, 3⟩]
Encrypted: [Enc(⟨5, site-1, 0⟩), Enc(⟨10, site-2, 3⟩)]

Server compares Enc(⟨5, site-1, 0⟩) < Enc(⟨10, site-2, 3⟩)
Result: correctly identifies position ordering

Example Allocation Sequence

1. Alice inserts at position 0: allocate(0, ∞) → [⟨16, alice, 0⟩]
   Character "h" at position [⟨16, alice, 0⟩]

2. Alice inserts at position 1: allocate([⟨16, alice, 0⟩], ∞) → [⟨16, alice, 0⟩, ⟨16, alice, 1⟩]
   Character "e" at position [⟨16, alice, 0⟩, ⟨16, alice, 1⟩]

3. Bob (offline) inserts between 0 and 1:
   allocate([⟨16, alice, 0⟩], [⟨16, alice, 0⟩, ⟨16, alice, 1⟩])
   Middle digit: (16 + 16) / 2 = 16 (no space, go deeper)
   allocate([⟨16, alice, 0⟩, ⟨16, alice, 0⟩], ...)
   Result: [⟨16, alice, 0⟩, ⟨8, bob, 0⟩]

4. After merge, positions sorted:
   [⟨16, alice, 0⟩]
   [⟨16, alice, 0⟩, ⟨8, bob, 0⟩]
   [⟨16, alice, 0⟩, ⟨16, alice, 1⟩]
   Lexicographic order: "h" < "?" < "e"

Key Terms

• LSEQ → LogootSplit variant of Logoot CRDT; generates unique position identifiers
• Site identifier → Unique replica ID (agent UUID or consensus-elected number)
• Counter → Per-site clock; monotonically increasing
• Lexicographic order → Tuple comparison left-to-right (standard pair ordering)
• Digit allocation → Mid-point selection; if no space, go to next depth level

Q&A

Q: What stops position IDs from growing infinitely deep? A: With BASE=32 and depth O(log N), positions grow logarithmically. 15 levels can address 32^15 unique positions — far exceeding any practical document.

Q: Can two sites generate the same position? A: No. The site field is unique (UUID or agent-id). Even if digits and counters match, the site ID differs, preventing collisions.

Q: Why include the counter if site is unique? A: The counter ensures monotonic ordering for a single site’s insertions. Without it, position allocation could create duplicate (digit, site) pairs across multiple insertions.

Examples

LSEQ positions are like nested Russian dolls: outer doll (first level) groups characters, inner dolls (subsequent levels) refine ordering. If the outer level can’t fit more, you nest deeper, creating unique addresses for any number of insertions.