Sequence CRDT (RGA)

A sequence CRDT is a text buffer that many replicas can edit at the same time and always merge back to the identical string, with no central server refereeing the edits. This one is an RGA — a Replicated Growable Array — which gives every character a permanent id and records the id of the character it was inserted after, so a position never shifts out from under a concurrent edit. It is the shape behind offline-friendly collaborative editors: two people type into the same document, their edits sync in any order, and both screens settle on the same text.

Build a factory sequenceCrdtRga(nodeId) that returns one replica. Each character is an element { id, char, after, deleted }; ids are minted from a per-replica counter plus the nodeId, so they are globally unique and totally ordered.

Signature

// A replica is created with its own nodeId. Character ids are minted from
// (an incrementing per-node counter, nodeId), e.g. "2@A" — unique and ordered.
function sequenceCrdtRga(nodeId: string): {
  insert(afterId: string | null, char: string): string; // -> the new element id
  delete(id: string): void;                               // tombstone; never removed
  toString(): string;                                     // visible chars, in order
  ids(): string[];                                        // ids of the visible chars
  merge(other: Replica): Replica;                         // fold in another replica
  state(): Element[];                                     // serializable snapshot
};

// Element = { id: string; char: string; after: string | null; deleted: boolean }

Examples

const doc = sequenceCrdtRga('A');
const h = doc.insert(null, 'h'); // insert at the very start -> "h"
const i = doc.insert(h, 'i');    // after h -> "hi"
doc.delete(i);                   // tombstone 'i' -> "h"
doc.insert(i, '!');              // 'i' still anchors, even deleted -> "h!"
doc.toString();                  // "h!"

// Two replicas start from the same 'a', then edit concurrently.
const a = sequenceCrdtRga('A');
const anchor = a.insert(null, 'a');
const b = sequenceCrdtRga('B');
b.merge(a);            // B learns about 'a'
a.insert(anchor, 'x'); // A sees "ax"
b.insert(anchor, 'y'); // B sees "ay"
a.merge(b);
b.merge(a);
a.toString(); // "ayx"
b.toString(); // "ayx" — same on both, in either merge order

Notes

• Anchor by id, not index — insert(afterId, char) inserts immediately after the element whose id equals afterId, or at the very start when afterId is null. It returns the new element's id.
• Tombstones — delete(id) never removes the element; it flags deleted so a late insert that anchors on that id still works.
• Deterministic tie-break — when several elements are inserted after the same anchor, order them by id, highest first, so every replica agrees.
• Convergence — merge unions the two element sets by id and ORs the tombstone flags; it is commutative, associative, and idempotent.
• Ids come from (counter, nodeId) — never Math.random or Date.now; the counter makes the id orderable, the nodeId makes it unique.
• Do not worry about — the network transport, garbage-collecting tombstones, or rich text; single characters merged in memory are enough here.