Conflict-free replicated data types guarantee eventual consistency without consensus. The trick: structure your data as a join-semilattice. Merging any two states produces a unique least upper bound. Merge is commutative, associative, and idempotent. No conflicts, no coordination, no locking.
Why CRDTs work
A join-semilattice is a partially ordered set where every pair of elements has a least upper bound (join). If your state is a semilattice and every update moves up in the lattice, then merging replicas always converges. Order of operations does not matter. Duplicate messages do not matter. This is the algebraic foundation of conflict-free replication.
G-Counter (grow-only counter)
Each node maintains its own counter. The value is the sum of all counters. Merge takes the componentwise max. Only increments are allowed (no decrements). This is a CRDT because max is a join on the natural number lattice.
Scheme
; G-Counter: grow-only, merge = componentwise max.; 3 nodes, each with its own slot.
(define (make-gcounter n) (make-list n 0))
(define (increment gc node-id)
(let loop ((g gc) (i 0) (acc (list)))
(if (null? g) (reverse acc)
(loop (cdr g) (+ i 1)
(cons (if (= i node-id) (+ (car g) 1) (car g)) acc)))))
(define (merge-gc a b)
(let loop ((x a) (y b) (acc (list)))
(if (null? x) (reverse acc)
(loop (cdr x) (cdr y) (cons (max (car x) (car y)) acc)))))
(define (value gc) (apply + gc))
(define a (make-gcounter 3)) ; (0 0 0)
(set! a (increment a 0)) ; (1 0 0)
(set! a (increment a 0)) ; (2 0 0)
(define b (make-gcounter 3)) ; (0 0 0)
(set! b (increment b 1)) ; (0 1 0)
(set! b (increment b 1)) ; (0 2 0)
(set! b (increment b 1)) ; (0 3 0)
(display "Replica A: ") (display a) (display " = ") (display (value a)) (newline)
(display "Replica B: ") (display b) (display " = ") (display (value b)) (newline)
(define merged (merge-gc a b))
(display "Merged: ") (display merged) (display " = ") (display (value merged)) (newline)
; Merge is idempotent
(define double-merged (merge-gc merged merged))
(display "Merge again: ") (display double-merged) (display " = ") (display (value double-merged))
Python
# G-Counter CRDTclass GCounter:
def __init__(self, n):
self.counts = [0] * n
def increment(self, node_id):
self.counts[node_id] += 1def merge(self, other):
result = GCounter(len(self.counts))
result.counts = [max(a, b) for a, b inzip(self.counts, other.counts)]
return result
def value(self):
returnsum(self.counts)
def __repr__(self):
returnf"{self.counts} = {self.value()}"
a = GCounter(3)
a.increment(0); a.increment(0)
b = GCounter(3)
b.increment(1); b.increment(1); b.increment(1)
print(f"A: {a}")
print(f"B: {b}")
merged = a.merge(b)
print(f"Merged: {merged}")
print(f"Merge(merged, merged): {merged.merge(merged)}") # idempotent
PN-Counter
A PN-Counter supports both increments and decrements by maintaining two G-Counters: P (positive) and N (negative). The value is P - N. Merge each G-Counter independently. Decrements never cancel increments at the semilattice level; they accumulate separately.
Scheme
; PN-Counter: two G-Counters, value = sum(P) - sum(N).
(define (make-pn n) (list (make-list n 0) (make-list n 0)))
(define (pn-p pn) (car pn))
(define (pn-n pn) (car (cdr pn)))
(define (pn-increment pn node-id)
(list (increment (pn-p pn) node-id) (pn-n pn)))
(define (pn-decrement pn node-id)
(list (pn-p pn) (increment (pn-n pn) node-id)))
(define (pn-merge a b)
(list (merge-gc (pn-p a) (pn-p b))
(merge-gc (pn-n a) (pn-n b))))
(define (pn-value pn)
(- (value (pn-p pn)) (value (pn-n pn))))
(define c (make-pn 2))
(set! c (pn-increment c 0)) ; +1
(set! c (pn-increment c 0)) ; +1
(set! c (pn-decrement c 0)) ; -1
(display "PN-Counter value: ") (display (pn-value c)) (newline)
(display "P = ") (display (pn-p c)) (newline)
(display "N = ") (display (pn-n c))
OR-Set (observed-remove set)
Each element gets a unique tag when added. Remove removes all currently observed tags for that element. If one replica adds and another concurrently removes, the add wins (add has a new tag the remove did not see). This gives intuitive "add wins" semantics without coordination.
Scheme
; OR-Set: add-wins semantics via unique tags.; Simplified: tags are (element, counter) pairs.
(define tag-counter 0)
(define (fresh-tag elem)
(set! tag-counter (+ tag-counter 1))
(list elem tag-counter))
(define set-a (list))
; Add "x" on replica A
(define tag-x1 (fresh-tag "x"))
(set! set-a (cons tag-x1 set-a))
; Add "y" on replica A
(define tag-y1 (fresh-tag "y"))
(set! set-a (cons tag-y1 set-a))
(display "Set A tags: ") (display set-a) (newline)
; Elements in the set
(define (elements tagged-set)
(let loop ((s tagged-set) (seen (list)))
(if (null? s) seen
(let ((elem (car (car s))))
(if (member elem seen)
(loop (cdr s) seen)
(loop (cdr s) (cons elem seen)))))))
(display "Elements: ") (display (elements set-a)) (newline)
; Remove "x": remove all tags for "x" we can see
(set! set-a (filter (lambda (tag) (not (equal? (car tag) "x"))) set-a))
(display "After removing x: ") (display (elements set-a))
Wikipedia