CoreConcept & Pseudocode Entry

CRDT G-Counter & PN-Counter

Conflict-free replicated counter that allows offline or partitioned replicas to increment (G-Counter) and decrement (PN-Counter) concurrently and merge without a central server via element-wise maximum.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Systems
Difficulty: Beginner
Family: Conflict-Free Replicated Data Types (CRDTs)
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: G-Counter CRDT, PN-Counter CRDT, Conflict-Free Replicated Counter, State-Based CvRDT Counter

Overview

A G-Counter (Grow-only Counter CRDT) gives each of N replicas its own slot in an array P[0..N-1]. Replica i increments only its own slot P[i] += delta, the global value is sum(P), and any two replicas merge their states offline or peer-to-peer via P_merged[k] = max(P_1[k], P_2[k]). Because element-wise max is commutative, associative, and idempotent (a join-semilattice), concurrent updates converge deterministically without locks, consensus quorums, or a central server. A PN-Counter pairs two G-Counters (P for increments, N for decrements) with value sum(P) - sum(N).

Core Concepts

join-semilatticecommutative associative idempotent mergeper-replica monotonic slotstrong eventual consistency

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1) increment, O(N) read/merge

Average

O(N) merge across N replicas

Worst

O(N)

Space

O(N) per counter

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for CRDT G-Counter & PN-Counter across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(N) merge across N replicas

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Worst-Case TimeO(N)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Working MemoryO(N) per counter

1.53 MB

Standard Heap FitN=100,000

When to Use

Use a G-Counter or PN-Counter CRDT when multiple replicas or offline clients must update a shared counter concurrently and merge without a central server, leader, or quorum round-trip.
Use it when availability under network partitions (AP in CAP) and automatic conflict-free convergence are required.

When Not to Use

Avoid when a strict non-negative balance invariant (e.g. bank account >= 0 Preventing double-spend) must be enforced on every write; that requires coordination or consensus (Raft/Paxos).

What It Does

Supports concurrent lock-free increments (and decrements in PN-Counter) across disconnected or multi-master replicas
Guarantees strong eventual consistency via commutative, associative, idempotent semilattice merge

Use Cases

Distributed page-view, like, and telemetry counters across multi-region edge servers without cross-region locks
Offline-first mobile and collaborative apps that sync counter updates when connectivity returns
Rate-limiting and quota tracking across leaderless peer-to-peer nodes

Inputs

Replica ID i in 0..N-1, local increment/decrement operations, and remote state vectors P_remote, N_remote

Outputs

Converged counter value sum_k(P[k] - N[k]) and merged semilattice state

Key Formulas (1)

Semilattice Merge & Value

merge(A, B)[k] = max(A.P_[k], B.P_[k]); value(A) = sum_{k=0}^{N−1} (A.P_[k] − A.N_[k])

merge(A, B)[k] = max(A.P[k], B.P[k]); value(A) = sum_{k=0}^{N-1} (A.P[k] - A.N[k])

Least upper bound in the product lattice of non-negative integers.

Pseudocode

1.Initialize increment vector P[0..N-1] = 0 and decrement vector N_vec[0..N-1] = 0 on each replica
2.On increment(delta >= 0) at replica i: P[i] += delta
3.On decrement(delta >= 0) at replica i (PN-Counter): N_vec[i] += delta
4.On value() query: return sum(P[0..N-1]) - sum(N_vec[0..N-1])
5.On merge(remote) from any peer: for k in 0..N-1: P[k] = max(P[k], remote.P[k]); N_vec[k] = max(N_vec[k], remote.N_vec[k])

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Initialize increment vector P[0..N-1] = 0 and decrement vector N_vec[0..N-1] = 0 on each replica
On increment(delta >= 0) at replica i: P[i] += delta
On decrement(delta >= 0) at replica i (PN-Counter): N_vec[i] += delta
On value() query: return sum(P[0..N-1]) - sum(N_vec[0..N-1])
On merge(remote) from any peer: for k in 0..N-1: P[k] = max(P[k], remote.P[k]); N_vec[k] = max(N_vec[k], remote.N_vec[k])

Canonical Example

Input: 3 replicas start at [0,0,0]; Replica 0 adds 2 -> [2,0,0]; offline Replica 1 adds 5 -> [0,5,0]; both merge twice
Output: Merged vector = max([2,0,0], [0,5,0]) = [2,5,0], total value = 7 (idempotent under duplicate merges)
Explanation: Taking element-wise max merges independent replica increments without double-counting even if messages are reordered or duplicated.

Implementation Notes

Cache the running sum locally so value queries take O(1) time between merges.

Common Pitfalls

Merging counter states by adding vectors (P1[k] + P2[k]) instead of taking the element-wise maximum max(P1[k], P2[k]), which double-counts replicated increments.
Allowing replica i to mutate slot P[j] (j != i), which violates the single-writer per-slot invariant.

Interactive Mechanism Walkthrough & State Debugger

Iterative Convergence & State Trajectory

iteration kk = 0

state estimate x_k2.36828

residual |f(x_k)|3.92e-1

convergenceDescending gradient

Step 1 of 5: Initialize increment vector P[0..N-1] = 0 and decrement vector N_vec[0..N-1] = 0 on each replica

Notes

Concept entry for CRDT G-Counter & PN-Counter: verified code implementation pending.

Sources (1)

What each reference supports for this entry.

Shapiro, Preguiça, Baquero & Zawirski (2011) — A Comprehensive Study of Convergent and Commutative Replicated Data Types

Paper

Foundational INRIA technical report formalizing state-based (CvRDT) and op-based (CmRDT) counters and sets.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Often paired withCRDT OR-Set (Observed-Remove Set)

Distributed Systems · Core

G-Counter/PN-Counter and OR-Set are the standard building blocks of state-based CRDT document stores.

Compare with this

Conceptual neighborVector Clocks