The Ghost Waits for Every Witness
The Ghost Waits for Every Witness
A writer wants to change a structure that readers are traversing right now, without ever making them stop or forcing them to wait for a lock that isn't there. The old solution was mutual exclusion: seize the structure, bar every reader at the door, make the change, then let the crowd back in. The new solution is more patient than that.
The writer does not touch the old structure at all. It builds a new version beside the old one, and with a single atomic pointer swap, redirects every future reader onto the new path. The old structure is not deleted. It becomes a ghost, still fully intact, still walkable by anyone who had already stepped onto it before the swap occurred.
Nothing forces those existing readers to notice the change or hurry to finish. They wander through the ghost at their own pace, unaware that a newer truth already exists elsewhere. The system does not reclaim the ghost's memory until it can prove that every reader who could possibly be inside it has already left.
This proof is called a grace period: a quiet interval where the system waits for every processor to pass through at least one moment of certain idleness, guaranteeing no witness remains. Only when the last witness has looked away does the ghost quietly dissolve, its memory returned to the world it once occupied.
This is Read-Copy-Update (RCU): lock-free reads bought by patient, provable memory reclamation.