CRDTs (Conflict-free Replicated Data Types)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

/**
 * G-Counter: Grow-only counter
 * 
 * Can only increment. Perfect for: view counts, click counts, event tallies.
 */
interface GCounter {
  counts: Map<string, number>;
  replicaId: string;
}
 
// G-Counter operations
const GCounterOps = {
  create: (replicaId: string): GCounter => ({
    counts: new Map([[replicaId, 0]]),
    replicaId,
  }),
  
  increment: (counter: GCounter, amount = 1): GCounter => {
    const newCounts = new Map(counter.counts);
    const current = newCounts.get(counter.replicaId) ?? 0;
    newCounts.set(counter.replicaId, current + amount);
    return { ...counter, counts: newCounts };
  },
  
  value: (counter: GCounter): number => 
    Array.from(counter.counts.values()).reduce((a, b) => a + b, 0),
  
  merge: (a: GCounter, b: GCounter): GCounter => {
    const merged = new Map(a.counts);
    for (const [id, count] of b.counts) {
      merged.set(id, Math.max(merged.get(id) ?? 0, count));
    }
    return { ...a, counts: merged };
  },
};
 
/**
 * PN-Counter: Positive-Negative Counter
 * 
 * Supports both increment and decrement via two G-Counters:
 * - P (positive): tracks increments
 * - N (negative): tracks decrements
 * - Value = sum(P) - sum(N)
 */
interface PNCounter {
  P: Map<string, number>;  // Positive counts
  N: Map<string, number>;  // Negative counts
  replicaId: string;
}
 
const PNCounterOps = {
  create: (replicaId: string): PNCounter => ({
    P: new Map([[replicaId, 0]]),
    N: new Map([[replicaId, 0]]),
    replicaId,
  }),
  
  increment: (counter: PNCounter, amount = 1): PNCounter => {
    const newP = new Map(counter.P);
    newP.set(counter.replicaId, (newP.get(counter.replicaId) ?? 0) + amount);
    return { ...counter, P: newP };
  },
  
  decrement: (counter: PNCounter, amount = 1): PNCounter => {
    const newN = new Map(counter.N);
    newN.set(counter.replicaId, (newN.get(counter.replicaId) ?? 0) + amount);
    return { ...counter, N: newN };
  },
  
  value: (counter: PNCounter): number => {
    const pSum = Array.from(counter.P.values()).reduce((a, b) => a + b, 0);
    const nSum = Array.from(counter.N.values()).reduce((a, b) => a + b, 0);
    return pSum - nSum;
  },
  
  merge: (a: PNCounter, b: PNCounter): PNCounter => {
    const mergedP = new Map(a.P);
    for (const [id, count] of b.P) {
      mergedP.set(id, Math.max(mergedP.get(id) ?? 0, count));
    }
    
    const mergedN = new Map(a.N);
    for (const [id, count] of b.N) {
      mergedN.set(id, Math.max(mergedN.get(id) ?? 0, count));
    }
    
    return { ...a, P: mergedP, N: mergedN };
  },
};
 
// Example: Concurrent increment/decrement
function demonstratePNCounter() {
  let replicaA = PNCounterOps.create("A");
  let replicaB = PNCounterOps.create("B");
  
  // A increments 5 times
  for (let i = 0; i < 5; i++) {
    replicaA = PNCounterOps.increment(replicaA);
  }
  
  // B decrements 2 times
  for (let i = 0; i < 2; i++) {
    replicaB = PNCounterOps.decrement(replicaB);
  }
  
  // After merge: value = 5 - 2 = 3
  const merged = PNCounterOps.merge(replicaA, replicaB);
  console.log("Merged value:", PNCounterOps.value(merged)); // 3
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/**
 * LWW-Register: Last-Write-Wins Register
 * 
 * Uses timestamps to determine winner in concurrent writes.
 * Simple but potentially loses data from the "losing" write.
 */
interface LWWRegister<T> {
  value: T;
  timestamp: number;  // Logical or wall-clock time
  replicaId: string;  // Tiebreaker for equal timestamps
}
 
const LWWRegisterOps = {
  create: <T>(value: T, replicaId: string): LWWRegister<T> => ({
    value,
    timestamp: Date.now(),
    replicaId,
  }),
  
  set: <T>(register: LWWRegister<T>, value: T): LWWRegister<T> => ({
    value,
    timestamp: Date.now(),
    replicaId: register.replicaId,
  }),
  
  get: <T>(register: LWWRegister<T>): T => register.value,
  
  merge: <T>(a: LWWRegister<T>, b: LWWRegister<T>): LWWRegister<T> => {
    // Higher timestamp wins
    if (a.timestamp > b.timestamp) return a;
    if (b.timestamp > a.timestamp) return b;
    // Tiebreaker: lexicographically larger replicaId wins
    return a.replicaId > b.replicaId ? a : b;
  },
};
 
/**
 * MV-Register: Multi-Value Register
 * 
 * Preserves ALL concurrent values. Returns a set of values
 * when there are unresolved concurrent writes.
 * 
 * Uses vector clocks to track causality.
 */
type VectorClock = Map<string, number>;
 
interface MVRegister<T> {
  // Each value is tagged with the vector clock at which it was written
  values: Array<{ value: T; clock: VectorClock }>;
  clock: VectorClock;
  replicaId: string;
}
 
const MVRegisterOps = {
  create: <T>(value: T, replicaId: string): MVRegister<T> => ({
    values: [{ value, clock: new Map([[replicaId, 0]]) }],
    clock: new Map([[replicaId, 0]]),
    replicaId,
  }),
  
  set: <T>(register: MVRegister<T>, value: T): MVRegister<T> => {
    // Increment local clock
    const newClock = new Map(register.clock);
    const current = newClock.get(register.replicaId) ?? 0;
    newClock.set(register.replicaId, current + 1);
    
    // New value dominates all existing values
    return {
      values: [{ value, clock: new Map(newClock) }],
      clock: newClock,
      replicaId: register.replicaId,
    };
  },
  
  get: <T>(register: MVRegister<T>): T[] => 
    register.values.map(v => v.value),
  
  // Check if clock a dominates (happens-after) clock b
  dominates: (a: VectorClock, b: VectorClock): boolean => {
    let dominated = true;
    for (const [id, count] of b) {
      if ((a.get(id) ?? 0) < count) dominated = false;
    }
    return dominated && !MVRegisterOps.equals(a, b);
  },
  
  equals: (a: VectorClock, b: VectorClock): boolean => {
    if (a.size !== b.size) return false;
    for (const [id, count] of a) {
      if (b.get(id) !== count) return false;
    }
    return true;
  },
  
  merge: <T>(a: MVRegister<T>, b: MVRegister<T>): MVRegister<T> => {
    // Merge clocks
    const mergedClock = new Map(a.clock);
    for (const [id, count] of b.clock) {
      mergedClock.set(id, Math.max(mergedClock.get(id) ?? 0, count));
    }
    
    // Keep values that are not dominated by any other value
    const allValues = [...a.values, ...b.values];
    const kept = allValues.filter(v => 
      !allValues.some(other => 
        other !== v && MVRegisterOps.dominates(other.clock, v.clock)
      )
    );
    
    // Deduplicate (values with equal clocks)
    const unique = kept.filter((v, i) => 
      kept.findIndex(other => 
        MVRegisterOps.equals(v.clock, other.clock)
      ) === i
    );
    
    return {
      values: unique,
      clock: mergedClock,
      replicaId: a.replicaId,
    };
  },
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

/**
 * G-Set: Grow-only Set
 * 
 * Elements can only be added, never removed.
 * Merge is set union. Simplest set CRDT.
 */
interface GSet<T> {
  elements: Set<T>;
}
 
const GSetOps = {
  create: <T>(): GSet<T> => ({ elements: new Set() }),
  
  add: <T>(set: GSet<T>, element: T): GSet<T> => ({
    elements: new Set([...set.elements, element]),
  }),
  
  contains: <T>(set: GSet<T>, element: T): boolean => 
    set.elements.has(element),
  
  merge: <T>(a: GSet<T>, b: GSet<T>): GSet<T> => ({
    elements: new Set([...a.elements, ...b.elements]),
  }),
};
 
/**
 * 2P-Set: Two-Phase Set
 * 
 * Uses two G-Sets: one for additions, one for removals.
 * Element is "in" the set if in A and not in R.
 * Once removed, cannot be re-added.
 */
interface TwoPSet<T> {
  A: Set<T>;  // Additions
  R: Set<T>;  // Removals (tombstones)
}
 
const TwoPSetOps = {
  create: <T>(): TwoPSet<T> => ({ A: new Set(), R: new Set() }),
  
  add: <T>(set: TwoPSet<T>, element: T): TwoPSet<T> => ({
    A: new Set([...set.A, element]),
    R: set.R,
  }),
  
  remove: <T>(set: TwoPSet<T>, element: T): TwoPSet<T> => {
    // Can only remove if element was added
    if (!set.A.has(element)) return set;
    return {
      A: set.A,
      R: new Set([...set.R, element]),
    };
  },
  
  contains: <T>(set: TwoPSet<T>, element: T): boolean => 
    set.A.has(element) && !set.R.has(element),
  
  elements: <T>(set: TwoPSet<T>): Set<T> => {
    const result = new Set<T>();
    for (const e of set.A) {
      if (!set.R.has(e)) result.add(e);
    }
    return result;
  },
  
  merge: <T>(a: TwoPSet<T>, b: TwoPSet<T>): TwoPSet<T> => ({
    A: new Set([...a.A, ...b.A]),
    R: new Set([...a.R, ...b.R]),
  }),
};
 
/**
 * OR-Set (Observed-Remove Set, a.k.a. Add-Wins Set)
 * 
 * The most practical set CRDT. Each add generates a unique tag.
 * Remove removes only the tags currently observed.
 * Concurrent add+remove: add wins (the new tag wasn't observed).
 */
interface ORSet<T> {
  // Element -> Set of unique tags
  elements: Map<T, Set<string>>;
  replicaId: string;
  counter: number;  // For generating unique tags
}
 
const ORSetOps = {
  create: <T>(replicaId: string): ORSet<T> => ({
    elements: new Map(),
    replicaId,
    counter: 0,
  }),
  
  add: <T>(set: ORSet<T>, element: T): ORSet<T> => {
    const newElements = new Map(set.elements);
    const currentTags = newElements.get(element) ?? new Set();
    const newTag = `${set.replicaId}:${set.counter + 1}`;
    newElements.set(element, new Set([...currentTags, newTag]));
    
    return {
      elements: newElements,
      replicaId: set.replicaId,
      counter: set.counter + 1,
    };
  },
  
  remove: <T>(set: ORSet<T>, element: T): ORSet<T> => {
    // Remove all currently observed tags for this element
    const newElements = new Map(set.elements);
    newElements.delete(element);
    return { ...set, elements: newElements };
  },
  
  contains: <T>(set: ORSet<T>, element: T): boolean => {
    const tags = set.elements.get(element);
    return tags !== undefined && tags.size > 0;
  },
  
  getElements: <T>(set: ORSet<T>): T[] => {
    const result: T[] = [];
    for (const [element, tags] of set.elements) {
      if (tags.size > 0) result.push(element);
    }
    return result;
  },
  
  merge: <T>(a: ORSet<T>, b: ORSet<T>): ORSet<T> => {
    const merged = new Map<T, Set<string>>();
    
    // Union of all elements and their tags
    for (const [element, tags] of a.elements) {
      merged.set(element, new Set(tags));
    }
    for (const [element, tags] of b.elements) {
      const existing = merged.get(element) ?? new Set();
      merged.set(element, new Set([...existing, ...tags]));
    }
    
    return {
      elements: merged,
      replicaId: a.replicaId,
      counter: Math.max(a.counter, b.counter),
    };
  },
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

/**
 * LWW-Map: Last-Write-Wins Map
 * 
 * Uses LWW-Register for each key's value.
 * Simple and practical for many use cases.
 */
interface LWWMap<K, V> {
  entries: Map<K, { value: V | null; timestamp: number }>;
  replicaId: string;
}
 
const LWWMapOps = {
  create: <K, V>(replicaId: string): LWWMap<K, V> => ({
    entries: new Map(),
    replicaId,
  }),
  
  set: <K, V>(map: LWWMap<K, V>, key: K, value: V): LWWMap<K, V> => {
    const newEntries = new Map(map.entries);
    newEntries.set(key, { value, timestamp: Date.now() });
    return { ...map, entries: newEntries };
  },
  
  get: <K, V>(map: LWWMap<K, V>, key: K): V | undefined => {
    const entry = map.entries.get(key);
    return entry?.value ?? undefined;
  },
  
  delete: <K, V>(map: LWWMap<K, V>, key: K): LWWMap<K, V> => {
    const newEntries = new Map(map.entries);
    // Tombstone: mark as deleted with null value
    newEntries.set(key, { value: null, timestamp: Date.now() });
    return { ...map, entries: newEntries };
  },
  
  has: <K, V>(map: LWWMap<K, V>, key: K): boolean => {
    const entry = map.entries.get(key);
    return entry !== undefined && entry.value !== null;
  },
  
  merge: <K, V>(a: LWWMap<K, V>, b: LWWMap<K, V>): LWWMap<K, V> => {
    const merged = new Map(a.entries);
    
    for (const [key, bEntry] of b.entries) {
      const aEntry = merged.get(key);
      if (!aEntry || bEntry.timestamp > aEntry.timestamp) {
        merged.set(key, bEntry);
      }
    }
    
    return { ...a, entries: merged };
  },
  
  toObject: <K, V>(map: LWWMap<K, V>): Map<K, V> => {
    const result = new Map<K, V>();
    for (const [key, entry] of map.entries) {
      if (entry.value !== null) {
        result.set(key, entry.value);
      }
    }
    return result;
  },
};
 
/**
 * OR-Map: Observed-Remove Map with Nested CRDTs
 * 
 * Keys are managed via OR-Set semantics.
 * Values can be any CRDT type, supporting nested structures.
 */
interface ORMap<V> {
  // Key presence tracked via OR-Set tags
  keys: Map<string, Set<string>>;
  // Values are CRDTs themselves
  values: Map<string, V>;
  replicaId: string;
  counter: number;
}
 
// Example: ORMap where values are PN-Counters
interface NestedCounter {
  P: Map<string, number>;
  N: Map<string, number>;
}
 
const ORMapWithCounterOps = {
  create: (replicaId: string): ORMap<NestedCounter> => ({
    keys: new Map(),
    values: new Map(),
    replicaId,
    counter: 0,
  }),
  
  // Get or create entry for a key
  getOrCreate: (
    map: ORMap<NestedCounter>, 
    key: string
  ): { map: ORMap<NestedCounter>; counter: NestedCounter } => {
    let newMap = map;
    
    // Ensure key exists
    if (!map.keys.has(key) || map.keys.get(key)!.size === 0) {
      const newKeys = new Map(map.keys);
      const newTag = `${map.replicaId}:${map.counter + 1}`;
      newKeys.set(key, new Set([newTag]));
      
      const newValues = new Map(map.values);
      newValues.set(key, { 
        P: new Map([[map.replicaId, 0]]),
        N: new Map([[map.replicaId, 0]]),
      });
      
      newMap = {
        keys: newKeys,
        values: newValues,
        replicaId: map.replicaId,
        counter: map.counter + 1,
      };
    }
    
    return { map: newMap, counter: newMap.values.get(key)! };
  },
  
  // Update the counter at a key
  updateCounter: (
    map: ORMap<NestedCounter>,
    key: string,
    updater: (counter: NestedCounter) => NestedCounter
  ): ORMap<NestedCounter> => {
    const { map: newMap, counter } = ORMapWithCounterOps.getOrCreate(map, key);
    const updatedCounter = updater(counter);
    
    const newValues = new Map(newMap.values);
    newValues.set(key, updatedCounter);
    
    return { ...newMap, values: newValues };
  },
  
  remove: (map: ORMap<NestedCounter>, key: string): ORMap<NestedCounter> => {
    const newKeys = new Map(map.keys);
    newKeys.delete(key);
    return { ...map, keys: newKeys };
  },
  
  merge: (
    a: ORMap<NestedCounter>, 
    b: ORMap<NestedCounter>
  ): ORMap<NestedCounter> => {
    // Merge key presence (OR-Set style)
    const mergedKeys = new Map<string, Set<string>>();
    for (const [key, tags] of a.keys) {
      mergedKeys.set(key, new Set(tags));
    }
    for (const [key, tags] of b.keys) {
      const existing = mergedKeys.get(key) ?? new Set();
      mergedKeys.set(key, new Set([...existing, ...tags]));
    }
    
    // Merge values (for keys present in either)
    const mergedValues = new Map<string, NestedCounter>();
    const allKeys = new Set([...a.values.keys(), ...b.values.keys()]);
    
    for (const key of allKeys) {
      const aVal = a.values.get(key);
      const bVal = b.values.get(key);
      
      if (aVal && bVal) {
        // Merge PN-Counters
        const mergedP = new Map(aVal.P);
        for (const [id, count] of bVal.P) {
          mergedP.set(id, Math.max(mergedP.get(id) ?? 0, count));
        }
        const mergedN = new Map(aVal.N);
        for (const [id, count] of bVal.N) {
          mergedN.set(id, Math.max(mergedN.get(id) ?? 0, count));
        }
        mergedValues.set(key, { P: mergedP, N: mergedN });
      } else {
        mergedValues.set(key, aVal ?? bVal!);
      }
    }
    
    return {
      keys: mergedKeys,
      values: mergedValues,
      replicaId: a.replicaId,
      counter: Math.max(a.counter, b.counter),
    };
  },
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

/**
 * Simplified RGA (Replicated Growable Array)
 * 
 * Each character has:
 * - Unique ID (replicaId, sequence)
 * - Reference to the character it was inserted after
 * - Tombstone flag for deleted characters
 */
interface RGAChar {
  id: { replica: string; seq: number };
  value: string;
  deleted: boolean;
  after: { replica: string; seq: number } | null;  // null = start
}
 
interface RGAText {
  chars: RGAChar[];
  replicaId: string;
  seq: number;
}
 
const RGAOps = {
  create: (replicaId: string): RGAText => ({
    chars: [],
    replicaId,
    seq: 0,
  }),
  
  // Find position of a char by its ID
  findById: (
    text: RGAText, 
    id: { replica: string; seq: number } | null
  ): number => {
    if (id === null) return -1;  // Before start
    return text.chars.findIndex(
      c => c.id.replica === id.replica && c.id.seq === id.seq
    );
  },
  
  // Compare IDs for ordering concurrent inserts
  compareIds: (
    a: { replica: string; seq: number },
    b: { replica: string; seq: number }
  ): number => {
    if (a.seq !== b.seq) return b.seq - a.seq;  // Higher seq wins
    return b.replica.localeCompare(a.replica);  // Tiebreaker
  },
  
  insert: (
    text: RGAText, 
    afterIndex: number,  // -1 = at start
    char: string
  ): { text: RGAText; op: RGAChar } => {
    const newSeq = text.seq + 1;
    const afterId = afterIndex >= 0 ? text.chars[afterIndex].id : null;
    
    const newChar: RGAChar = {
      id: { replica: text.replicaId, seq: newSeq },
      value: char,
      deleted: false,
      after: afterId,
    };
    
    // Find correct position (after afterId, before any later concurrent inserts)
    let insertPosition = afterIndex + 1;
    while (insertPosition < text.chars.length) {
      const existing = text.chars[insertPosition];
      // Check if existing was also inserted after the same position
      const existingAfter = existing.after;
      const sameParent = afterId === null 
        ? existingAfter === null
        : existingAfter !== null && 
          existingAfter.replica === afterId.replica && 
          existingAfter.seq === afterId.seq;
          
      if (!sameParent) break;
      
      // Concurrent insert: compare IDs for deterministic ordering
      if (RGAOps.compareIds(newChar.id, existing.id) > 0) break;
      insertPosition++;
    }
    
    const newChars = [...text.chars];
    newChars.splice(insertPosition, 0, newChar);
    
    return {
      text: { chars: newChars, replicaId: text.replicaId, seq: newSeq },
      op: newChar,
    };
  },
  
  delete: (text: RGAText, index: number): RGAText => {
    // Don't actually remove—mark as tombstone
    const newChars = [...text.chars];
    newChars[index] = { ...newChars[index], deleted: true };
    return { ...text, chars: newChars };
  },
  
  // Apply a remote operation
  applyRemote: (text: RGAText, op: RGAChar): RGAText => {
    // Check if already applied
    if (RGAOps.findById(text, op.id) >= 0) return text;
    
    // Find insertion position
    const afterPosition = RGAOps.findById(text, op.after);
    let insertPosition = afterPosition + 1;
    
    while (insertPosition < text.chars.length) {
      const existing = text.chars[insertPosition];
      const sameParent = op.after === null
        ? existing.after === null
        : existing.after !== null &&
          existing.after.replica === op.after.replica &&
          existing.after.seq === op.after.seq;
          
      if (!sameParent) break;
      if (RGAOps.compareIds(op.id, existing.id) > 0) break;
      insertPosition++;
    }
    
    const newChars = [...text.chars];
    newChars.splice(insertPosition, 0, op);
    
    return { ...text, chars: newChars };
  },
  
  toString: (text: RGAText): string => 
    text.chars.filter(c => !c.deleted).map(c => c.value).join(''),
};
 
// Example: concurrent editing
function demonstrateConcurrentEdit() {
  let replicaA = RGAOps.create("A");
  let replicaB = RGAOps.create("B");
  
  // Both start with "Hello"
  for (const char of "Hello") {
    const result = RGAOps.insert(
      replicaA, 
      replicaA.chars.length - 1, 
      char
    );
    replicaA = result.text;
    replicaB = RGAOps.applyRemote(replicaB, result.op);
  }
  
  console.log("Initial:", RGAOps.toString(replicaA)); // "Hello"
  
  // A inserts "X" after "o"
  const { text: newA, op: opA } = RGAOps.insert(replicaA, 4, "X");
  replicaA = newA;
  
  // Concurrently, B inserts "Y" after "o"
  const { text: newB, op: opB } = RGAOps.insert(replicaB, 4, "Y");
  replicaB = newB;
  
  // Exchange operations
  replicaA = RGAOps.applyRemote(replicaA, opB);
  replicaB = RGAOps.applyRemote(replicaB, opA);
  
  // Both converge to same result (order is deterministic!)
  console.log("A:", RGAOps.toString(replicaA)); // "HelloXY" or "HelloYX"
  console.log("B:", RGAOps.toString(replicaB)); // Same as A
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

## CRDT Selection Decision Tree
 
START: What data do you need to store?
 
├── Single value (like a variable)?
│   ├── Concurrent writes should all be visible → MV-Register
│   └── Latest write should win → LWW-Register
│
├── A count or quantity?
│   ├── Only ever increases → G-Counter
│   └── Can increase and decrease → PN-Counter
│
├── A collection of items?
│   ├── Only additions, never removals → G-Set
│   ├── Add/remove, but items never re-added → 2P-Set
│   ├── Add/remove with re-add support
│   │   ├── Add-wins on conflict → OR-Set ★ Most common
│   │   └── Remove-wins on conflict → RWW-Set (rare)
│   └── Latest operation wins → LWW-Element-Set
│
├── Key-value associations?
│   ├── Simple values, LWW semantics → LWW-Map
│   └── Nested CRDTs as values → OR-Map with nested CRDTs
│
├── Ordered sequence / text?
│   ├── Simple text → RGA, YATA (Yjs)
│   └── Rich text with formatting → Peritext, Automerge
│
└── Graph structure?
    └── Use OR-Map with references, or specialized graph CRDT
 
★ = Recommended default for category