State-Based CRDTs: The PN-Counter
Subtracting directly from a G-Counter breaks monotonicity, destroying CRDT convergence. A PN-Counter (Positive-Negative) solves this by bundling two distinct G-Counters: one tracking increments ($P$) and one tracking decrements ($N$). The effective count is $P - N$ ➕➖.
class PNCounter:
def __init__(self, node_id):
self.node_id = node_id
self.p = {node_id: 0} # Increments
self.n = {node_id: 0} # Decrements
def inc(self, step=1):
self.p[self.node_id] += step
def dec(self, step=1):
self.n[self.node_id] += step
def value(self):
return sum(self.p.values()) - sum(self.n.values())
def merge(self, other):
for k in set(self.p) | set(other.p):
self.p[k] = max(self.p.get(k, 0), other.p.get(k, 0))
for k in set(self.n) | set(other.n):
self.n[k] = max(self.n.get(k, 0), other.n.get(k, 0))
node_a = PNCounter("A")
node_a.inc(10)
node_a.dec(3)
print(f"Net Value: {node_a.value()} 🎯")
# 35. State-Based CRDTs: The PN-Counter When building a shopping cart counter or inventory reservation system, users add items ($+1$) and remove items ($-1$). If two offline replicas subtract numbers directly, taking the $\max$ during merge would ignore the subtraction completely 🛑. ```python # Broken attempt: # Node A has 5. User removes 1 -> 4. # Node B has 5. # merge(4, 5) -> max(4, 5) = 5 (The deletion vanished!) ``` ### The PN-Counter Invariant To support deletions while keeping the semilattice monotonically increasing: 1. **$P$ Vector (Grow-Only)**: Holds the total cumulative increments ever performed by each node. 2. **$N$ Vector (Grow-Only)**: Holds the total cumulative decrements ever performed by each node. 3. **Monotonic Merging**: Both $P$ and $N$ merge using standard component-wise $\max$, meaning both vectors only ever climb higher. 4. **Projection**: The observed state at any instant is: $$\text{Value} = \sum_{k} P[k] - \sum_{k} N[k]$$ Deletions are recorded forever without losing causal history ➕➖. --- ### Interactive Pop-Quiz 🧠 #### Why can you not simply subtract a number from a node's G-Counter vector slot to handle a decrement? - [ ] Because reducing a value violates the monotonic growth rule required for join-semilattice convergence 📉 - [ ] Because Python integers cannot store negative numbers in dictionaries - [ ] Because subtraction inverts the byte order of the memory allocation - [ ] Because the TCP stack rejects packets with decrement instructions --- ### Practical Challenge 🎯 Implement `PNCounter` with `inc()`, `dec()`, `value()`, and `merge()`. Node 1 increments 15 and decrements 4. Node 2 increments 10 and decrements 6. Merge Node 2 into Node 1, assert the final value is 15, and print it. <details> <summary>Solution</summary> ```python class PNCounter: def __init__(self, node_id): self.node_id = node_id self.p = {node_id: 0} self.n = {node_id: 0} def inc(self, step=1): self.p[self.node_id] += step def dec(self, step=1): self.n[self.node_id] += step def value(self): return sum(self.p.values()) - sum(self.n.values()) def merge(self, other): for k in set(self.p) | set(other.p): self.p[k] = max(self.p.get(k, 0), other.p.get(k, 0)) for k in set(self.n) | set(other.n): self.n[k] = max(self.n.get(k, 0), other.n.get(k, 0)) n1 = PNCounter("N1") n2 = PNCounter("N2") n1.inc(15) n1.dec(4) n2.inc(10) n2.dec(6) n1.merge(n2) assert n1.value() == 15 print(n1.value()) ``` </details>