CRDT Multi-User Merge¶

This diagram traces what happens when two users edit the same :class:CollaborativeDocument concurrently and their replicas converge without coordination. The CRDT machinery lives at src/fcc/collaboration/crdt.py:167 (in-memory LWW fallback) and src/fcc/collaboration/crdt.py:289 (y-py backed backend). v1.5.0 Pillar D introduced this layer; ADR-012 captures the decision to wrap two interchangeable backends behind a single CRDTBackend Protocol so that Yjs (production) and the LWW fallback (CI, demos, offline) are swap-equivalent.

The sequence below shows two replicas editing in parallel, a Lamport tie-break, and the eventual convergent state. The transport (WebSocket, in-process callback, or anything else) is abstracted behind the broadcaster / observer chain — this diagram only covers the CRDT convergence itself.

sequenceDiagram
    participant UserA as Replica A (User A)
    participant DocA as CollaborativeDocument A
    participant BackA as CRDTBackend A
    participant Transport as Wire transport
    participant BackB as CRDTBackend B
    participant DocB as CollaborativeDocument B
    participant UserB as Replica B (User B)

    Note over BackA,BackB: Both replicas start with lamport=0 and share a document_id
    UserA->>DocA: set_text("Hello")
    DocA->>BackA: set_text("Hello")
    Note over BackA: lamport=1, op=(text,"","Hello",1,A)
    BackA-->>DocA: update bytes (json LWW op)
    DocA->>Transport: on_update(update)
    UserB->>DocB: set_text("Howdy")
    DocB->>BackB: set_text("Howdy")
    Note over BackB: lamport=1, op=(text,"","Howdy",1,B)
    BackB-->>DocB: update bytes
    DocB->>Transport: on_update(update)
    Transport->>BackA: apply_update(bytes from B)
    Note over BackA: compare (1,A) vs (1,B) B wins (replica_id lex tie-break)
    BackA-->>DocA: notify observers
    Transport->>BackB: apply_update(bytes from A)
    Note over BackB: compare (1,B) vs (1,A) B keeps state
    BackB-->>DocB: notify no-op LWW lost
    DocA->>UserA: get_text() == "Howdy"
    DocB->>UserB: get_text() == "Howdy"
    Note over UserA,UserB: Both replicas converged without coordination

The convergence loop is bounded by three invariants. First, every outbound update is a JSON-encoded UTF-8 bytes blob carrying a single operation (_LwwOp → {kind, key, value, lamport, replica_id}) so the wire format is trivially replayable. Second, apply_update re-broadcasts only operations that actually won LWW, which prevents loops — observers see the post-merge state, not the raw incoming bytes. Third, every backend advances its local Lamport clock past any higher remote tick it sees, so causality is preserved even when messages arrive out of order.

Two operational notes. Presence updates (cursor position, selection range) go through the same CRDT backend under the meta/presence:<user> namespace, which means late joiners receive current presence automatically via sync_state(). And the MultiUserSession.on_remote_edit(update) path at src/fcc/collaboration/multi_user.py:308 is the wire-facing entry point that calls into this convergence sequence — every edit from a remote user lands there.

Steps in detail¶

User A local edit — set_text("Hello") produces an _LwwOp at Lamport=1 with replica_id="A" and emits a JSON bytes blob.
User B local edit — Concurrent set_text("Howdy") on replica B produces an _LwwOp at Lamport=1 with replica_id="B".
Wire exchange — Both blobs cross through the transport (WebSocket bridge, observer chain, or any on_update consumer).
Replica A applies B's op — Compares (1, "A") to the incoming (1, "B"). Because "B" > "A" lexicographically, B wins; state becomes "Howdy".
Replica B applies A's op — Compares (1, "B") to the incoming (1, "A"). B's state already wins; apply returns False; no notification.
Convergence — Both replicas agree on "Howdy" without any coordinator.

CRDT Multi-User Merge¶

Steps in detail¶

See also¶