Key Question

How do we design data structures that can be replicated across multiple nodes, updated concurrently, and still merge into a single consistent state?

Deep Dive

The crdt.ts file implements four CRDT variants in TypeScript. Each demonstrates a different strategy for achieving eventual consistency without conflicts. There is no “last writer wins” or “manual merge” — the math guarantees convergence.

1. G-Counter: The Grow-Only Counter

A G-Counter only supports increment. Each node tracks its own contributions in a map: { nodeId: count }.

class GCounter {
  private counts: Map<number, number> = new Map()

  constructor(private nodeId: number) {}

  increment(by: number = 1) {
    this.counts.set(this.nodeId,
      (this.counts.get(this.nodeId) ?? 0) + by)
  }

  value(): number {
    let total = 0
    for (const v of this.counts.values()) total += v
    return total
  }

  merge(other: GCounter): void {
    // Take the max value for each node — this is the
    // join semilattice operation (commutative, associative, idempotent)
    for (const [key, value] of other.counts) {
      this.counts.set(key,
        Math.max(this.counts.get(key) ?? 0, value))
    }
  }
}

The value is the sum of all entries. The merge operation takes the maximum value for each key. Since counters only grow, taking the max is safe. Mathematically, this is a join semilattice: commutative, associative, and idempotent.

2. PN-Counter: Going Negative

A G-Counter can only increase. A PN-Counter solves this by using two G-Counters: one for increments (P) and one for decrements (N). value = sum(P) - sum(N):

class PNCounter {
  private p: GCounter  // increments
  private n: GCounter  // decrements

  constructor(nodeId: number) {
    this.p = new GCounter(nodeId)
    this.n = new GCounter(nodeId)
  }

  increment(by: number = 1) { this.p.increment(by) }
  decrement(by: number = 1) { this.n.increment(by) }

  value(): number { return this.p.value() - this.n.value() }

  merge(other: PNCounter): void {
    this.p.merge(other.p)  // Both G-Counters converge independently
    this.n.merge(other.n)  // so their difference also converges
  }
}

When you increment, you increment P. When you decrement, you increment N. Since both P and N are G-Counters, they converge independently, and therefore the difference also converges.

3. LWW-Register: Time as a Tiebreaker

An LWW-Register stores a value plus a timestamp. On merge, the value with the highest timestamp wins:

class LWWRegister<T> {
  private value: T | null = null
  private timestamp: number = 0
  private nodeId: number

  constructor(nodeId: number) { this.nodeId = nodeId }

  assign(newValue: T, clock: number) {
    this.value = newValue
    this.timestamp = clock
  }

  merge(other: LWWRegister<T>): void {
    // Compare (timestamp, nodeId) lexicographically.
    // Node ID breaks ties deterministically.
    if (other.timestamp > this.timestamp ||
       (other.timestamp === this.timestamp &&
        other.nodeId > this.nodeId)) {
      this.value = other.value
      this.timestamp = other.timestamp
    }
  }
}

If timestamps tie, we use the node ID as a deterministic tiebreaker. This ensures convergence even with concurrent writes. The weakness: data loss. If two nodes write concurrently, one value is silently discarded.

4. OR-Set: The Observed-Remove Set

The OR-Set solves the “add then remove” problem that plagues naive replicated sets. Every “add” creates a unique tag. A “remove” only removes the tags the remover has observed:

class ORSet<T> {
  // Map from element → Set of unique tags
  private addSet: Map<string, Set<string>> = new Map()
  private removeSet: Map<string, Set<string>> = new Map()

  add(element: T) {
    const key = JSON.stringify(element)
    if (!this.addSet.has(key)) this.addSet.set(key, new Set())
    this.addSet.get(key)!.add(this.makeTag()) // unique tag per add
  }

  remove(element: T) {
    const key = JSON.stringify(element)
    const tags = this.addSet.get(key)
    if (tags) {
      if (!this.removeSet.has(key)) this.removeSet.set(key, new Set())
      // Only remove the tags we have OBSERVED
      for (const tag of tags) this.removeSet.get(key)!.add(tag)
    }
  }

  has(element: T): boolean {
    const key = JSON.stringify(element)
    const addTags = this.addSet.get(key)
    const removeTags = this.removeSet.get(key)
    if (!addTags) return false
    if (!removeTags) return true
    // Visible if ANY add tag is NOT in the tombstone
    for (const tag of addTags)
      if (!removeTags.has(tag)) return true
    return false
  }

  merge(other: ORSet<T>): void {
    // Union of both add sets and remove sets
    for (const [key, tags] of other.addSet) { /* union add */ }
    for (const [key, tags] of other.removeSet) { /* union remove */ }
  }
}

The OR-Set guarantee: If Node 1 adds “banana” (tag t1) and Node 2 concurrently removes “banana” (only removing tag t2 which it observed), then tag t1 survives the merge. You can only remove what you have observed.

Key Takeaways

• G-Counter/PN-Counter are “state-based” CRDTs: the entire state is exchanged and merged.
• LWW-Register uses timestamps for conflict resolution but loses concurrent writes silently.
• OR-Set preserves causal history: an element added independently survives concurrent removes at other nodes.
• All four types are commutative: the order of merges doesn’t matter, guaranteeing convergence.

Running the Code

cd lessons/02-Consistency-Trade-offs/05-CRDTs/
npx ts-node crdt.ts

Full Source

View or download the complete implementation: crdt.ts

Exercises

1. Why can’t a G-Counter support decrement? What would break?
2. In an LWW-Register, why do we compare (timestamp, nodeId) instead of just timestamp?
3. Why does “banana” survive in the OR-Set simulation even though Node 2 removed it?

👁️ View Solutions

1. A G-Counter merge takes the max of per-node counts. Decrement violates the grow-only property — a decrement would be lost if the other node had a higher value, causing the counter to “undecrement” after a merge.
2. If two writes happen at the exact same timestamp (e.g., same logical clock value on different nodes), the system needs a tiebreaker. Appending the node ID creates a total order out of the partial order.
3. In the simulation, Node 1 added “banana” (tag t1) and Node 2 added “banana” (tag t2) independently. Node 2 removed “banana” but only removed tag t2 (its own tag). Tag t1 (from Node 1) was never observed by Node 2, so it survives the merge.

✏️ Exercises

Exercises: CRDTs

Exercise 1: G-Counter Merge

A G-Counter has 3 replicas. Replica A’s state is [5, 0, 0]. Replica B’s state is [0, 3, 2].

1. What is the state of each replica after they merge (A with B, B with A)?
2. What is the final counter value?
3. Now replica C (state [1, 1, 1]) joins the merge. What is the final result?

Exercise 2: G-Counter Limitations

1. Explain in one sentence why a G-Counter cannot represent decrements.
2. Could you build a G-Counter where decrement is allowed by subtracting from the local slot? What goes wrong?
3. What mathematical property of the merge function would break if you allowed arbitrary subtraction?

Exercise 3: OR-Set Concurrent Operations

Three replicas (A, B, C) start with an empty OR-Set.

• Replica A: adds “apple” (tag = a1), adds “banana” (tag = a2)
• Replica B: adds “apple” (tag = b1), removes “banana” (removes a2 — B observed A’s add)
• Replica C: removes “apple” (removes a1, b1 — C observed both)

After all replicas merge:

1. Is “apple” in the set? Why or why not?
2. Is “banana” in the set? Why or why not?
3. How many unique tags are in the final set?

Exercise 4: CRDT vs Consensus

An e-commerce platform uses an inventory CRDT (PN-Counter) to track stock across regions. The current count for item X is 5.

1. Two regions both sell one unit simultaneously (decrement by 1 each). What does the counter show after merge?
2. The actual physical inventory is 5 units. After the decrements above, you sell 3 more units in region A and 2 more in region B. A customer checks the count and sees 3. They buy 3 — but the warehouse only has 2 left. How could this over-selling happen?
3. Would Raft prevent this problem? What trade-off does it introduce?