TwoPSet

Add a second GSet

Each notebook has an additions GSet and a removals GSet. The additions GSet records every beacon name a hiker has received. The removals GSet records every name that a hiker knows is permanently retired. Both pages only grow, and the hikers merge each page by union.

Alice finds that the old Eagle Creek beacon is gone, so she writes Eagle Creek in the removals GSet. Her additions GSet still contains the name, but her visible list is empty. Bob and Carol still show Eagle Creek until they receive her removal record.

That retained removal record is a tombstone. It prevents a delayed or repeated addition record from making the retired beacon visible again.

A TwoPSet is composed of those two GSets. A value is visible only when it appears in additions and does not appear in removals.

The name means two-phase set. Each beacon name can move from never added, to present, to permanently removed. Eagle Creek cannot return after the second phase, but the hikers can still add other beacon names to their notebooks.

TwoPSet = additions GSet + removals GSet
members = additions - removals

After the hikers exchange records, every notebook contains Eagle Creek in both sets. All three visible lists are empty. A delayed addition cannot erase the retained removal.

Bob finds the replacement

The next morning, Bob finds a new beacon at Eagle Creek. Its name is the same, so his notebook adds Eagle Creek again. The name was already in his additions, and Alice's removal record still excludes it after merge.

This is the cost of permanent removal. A TwoPSet cannot distinguish two installations that use the same value. The next set gives every add its own identity, so Alice can remove the old beacon while Bob's new beacon survives.

Sources and implementation

Watershed's TwoPSet kernel stores additions and permanent removals as two grow-only sets.