CRDTs: G-Counter

Conflict-Free Replicated Data Types (CRDTs)

In an eventually consistent distributed system, replicas can accept writes independently and sync later. This creates conflicts: two replicas might have different values for the same key.

CRDTs (Conflict-Free Replicated Data Types) are data structures designed so that all conflicts can be resolved automatically — merging is always deterministic and produces the correct result.

The G-Counter (Grow-Only Counter)

The simplest CRDT is the G-Counter. It is a distributed counter that can only be incremented. Each node maintains an array of counters — one slot per node. A node only increments its own slot.

class GCounter {
  constructor(nodeId, numNodes) {
    this.nodeId = nodeId;
    this.counts = new Array(numNodes).fill(0);
  }

  increment() {
    this.counts[this.nodeId]++;
  }

  value() {
    return this.counts.reduce((sum, c) => sum + c, 0);
  }

  merge(other) {
    // Element-wise maximum
    for (let i = 0; i < this.counts.length; i++) {
      this.counts[i] = Math.max(this.counts[i], other.counts[i]);
    }
  }
}

Why It Works

• No conflicts: Each node writes to its own slot — no contention.
• Merge is idempotent: merging twice gives the same result as once.
• Merge is commutative: merging A into B gives the same result as merging B into A.
• Merge is associative: (A merge B) merge C = A merge (B merge C).

These properties mean replicas can sync in any order, at any time, and always converge to the same value.

Real-World Uses

• Redis CRDT — distributed Redis instances use CRDTs for conflict-free replication.
• Riak — uses CRDTs for sets, maps, and counters.
• Collaborative editing — operational transforms and CRDTs power Google Docs-style real-time collaboration.

Your Task

Implement a GCounter class with increment(), value(), and merge(other) methods.