Structures
G-counter
The ranger asks Alice, Bob, and Carol to count birds on three trails. Each hiker tracks their own sightings in a shared three-row format, then leaves notes with their name and running count. The notes may arrive late, out of order, or more than once. By the end of the hike, all three notebooks must show the same total.
Three hikers copy the same notebook
Each notebook has one row for Alice, one for Bob, and one for Carol. A hiker writes new sightings in their own row. The other rows record the latest running counts received from checkpoint notes.
| Row | Alice's notebook | Bob's notebook | Carol's notebook |
|---|---|---|---|
| Alice | 7 | 0 | 0 |
| Bob | 0 | 3 | 0 |
| Carol | 0 | 0 | 0 |
| Birds seen | 7 | 3 | 0 |
Alice does not send seven separate sightings. She leaves one cumulative note that says her row has reached 7. Bob leaves the same kind of note when his row reaches 3.
AliceRunning bird count
BobRunning bird count
Alice fills in her row
Alice takes the ridge trail. Each time she spots a bird, she adds one
to her row. After seven sightings, Alice's notebook reads
[Alice: 7, Bob: 0, Carol: 0], so her local total is 7.
Alice's local copy of the shared counter is a replica. Bob and Carol each keep their own replica. The hikers exchange cumulative messages by leaving notes at known checkpoints.
birds = count[Alice]Bob takes a different trail
Bob counts birds along the river trail. Alice changes only Alice's count, and Bob changes only Bob's count. If Alice has seen 7 birds and Bob has seen 3, their shared total is 10.
This is a grow-only counter, or G-counter. Each replica keeps the largest note it has received from each hiker, then adds those counts. It does not add every message. If Bob leaves the same checkpoint note twice, both messages contain the same count of 3 birds. His count stays 3.
count[Alice] = max(all notes from Alice)
count[Bob] = max(all notes from Bob)
birds = count[Alice] + count[Bob] + ...Their checkpoint notes cross
When a hiker finds a note, they copy its running count into the named row only if the number is larger than the count already there. The three rows add up to the bird count.
On Carol's route, the first note at the north fork is from Alice: 7 birds. At the river bridge, she finds Bob's note for 3. Carol has not seen a bird herself, so her own row stays at 0.
| Checkpoint and note | Alice | Bob | Carol | Total |
|---|---|---|---|---|
| Trailhead | 0 | 0 | 0 | 0 |
| North fork: Alice 7 | 7 | 0 | 0 | 7 |
| River bridge: Bob 3 | 7 | 3 | 0 | 10 |
| Old lookout: Alice 4 | 7 | 3 | 0 | 10 |
At the old lookout, Carol finds an earlier note from Alice with a count of 4.
Her notebook already contains 7, so she leaves that row alone:
max(7, 4) = 7. Had she found 4 first, the row would have
changed from 0 to 4, then from 4 to 7. Either path through the notes
leads to the same notebook and the same total.
Elsewhere on the trails, the three notebooks can still disagree. Alice may know only her 7, Bob only his 3, and Carol neither. Walk the next part with them: leave one note at a time, or let Alice and Bob leave their notes together.
Count birds on three hikes
Record birds for Alice, Bob, or Carol. Each hiker leaves their running count at a known checkpoint. Turn off Auto-deliver to hold several notes before delivery to the other checkpoints.
Merge rule Keep the largest bird count left by each hiker.
New note In transit to a checkpoint
Shared note Being delivered to the other hikers
Alice
Connected to checkpoint network
Birds in this hiker's view
Bob
Connected to checkpoint network
Birds in this hiker's view
Carol
Connected to checkpoint network
Birds in this hiker's view
- No checkpoint note shared yet.
Enable JavaScript to run the demo. The initial values and expected result remain available in the article.
Count birds with Alice, Bob, or Carol, or leave Alice's and Bob's checkpoint notes together.
Open the hikers' count tables
Each hiker's notebook has one row for Alice, Bob, and Carol. A row stores the largest count received from that hiker. Checkpoint notes can be delivered in any order.
| Hiker | Alice's view | Bob's view | Carol's view |
|---|---|---|---|
| Alice | 0 | 0 | 0 |
| Bob | 0 | 0 | 0 |
| Carol | 0 | 0 | 0 |
A repeated or older note cannot lower a row. Each hiker compares the note with the count already in the table and keeps the larger value.
Every trail catches up
After delivery of both checkpoint notes, Alice, Bob, and Carol all read 10. Their views were temporarily inconsistent, but the G-counter kept both hikers' observations and made every replica agree.
This is eventual consistency. For each hiker, merge keeps the larger count from their checkpoint notes. The rule is commutative, associative, and idempotent. Arrival order does not change the answer, and the network can deliver the same checkpoint note more than once.
The count cannot go down
Every hiker needs a unique replica ID. If two hikers share an ID, pairwise maximum can discard one concurrent update.
The merge rule can only keep or raise each component. If a hiker finds a counting mistake, lowering a component is unsafe because an older, larger note could restore the mistake. The next structure records corrections without changing this merge rule.
Sources and implementation
This lesson calls Watershed's public G-counter kernel. The G-counter merge rule keeps the largest cumulative count for each hiker.
The merge rule is the state-based grow-only counter described in A comprehensive study of Convergent and Commutative Replicated Data Types.