Structures
GSet
The ranger sends Alice, Bob, and Carol onto separate trails to list every beacon they find. Their first rule is simple: they can add names to the survey, but they cannot remove them.
Alice reports Eagle Creek
Alice finds the Eagle Creek beacon and adds its name to her notebook. Bob and Carol are out of radio range. They still have empty lists.
Each notebook stores a set of names. At this moment Alice has
{ Eagle Creek }, while Bob and Carol each have
{}. No hiker has a global survey yet.
A GSet only adds members. When the hikers exchange their notebooks, each replica keeps the union of every name it has seen.
| Moment | Alice | Bob | Carol |
|---|---|---|---|
| Alice reports | Eagle Creek | empty | empty |
| Report delivered | Eagle Creek | Eagle Creek | Eagle Creek |
| Old copy repeats | Eagle Creek | Eagle Creek | Eagle Creek |
local members ∪ remote membersThree field notebooks
Combine the hikers' reports
Alice and Bob report different beacons while Carol waits. Exchange the records and watch every notebook keep the same union.
Merge rule Keep every distinct reported name.
Alice
No reports yet
Visible beacon list
Checkpoint note Additions page: Eagle Creek
Bob
No reports yet
Visible beacon list
Checkpoint note Additions page: Ridge Pass
Carol
No reports yet
Visible beacon list
Checkpoint note No note in this race
Mechanism evidence Entries can only accumulate.
- No records shared yet.
Enable JavaScript to run the demo. The starting state and expected result remain in the lesson.
Run the survey race, or let any hiker report a beacon.
Then the ranger needs an active list
Alice returns to Eagle Creek and finds that the old beacon has been taken down. The ranger no longer wants a record of every beacon ever observed. The ranger needs the beacons that are active now, but Alice has no valid GSet entry she can write to mean “remove Eagle Creek.”
A GSet cannot express that change. Removing the name locally would not be monotonic, and Carol's delayed copy could restore it. The next set adds permanent removal evidence instead of deleting history.
Sources and implementation
Watershed's GSet kernel uses set union for confirmed, optimistic, and peer-to-peer state.