THE FOLD / BOSS / THE GATEKEEPER / THE FENCING TOKEN
THE FENCING TOKEN
a lock that needs fencing was never a lock
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A lock does not stop a client that already holds it and then freezes. It wakes up after its lease has gone, still believing it is the writer, and writes over whoever took over. A fencing token makes the storage refuse it.
LIT verified live. Two clients, two steps each, all 6 interleavings enumerated. Without tokens, 2 of the 6 let a stale writer land a write over a newer one — schedules 0110 and 1001. With monotonic tokens the storage rejects those writes: 2 rejections, 0 corruptions. The lock is identical in both; only the storage changed.
LIT verified live. Two clients, two steps each, all 6 interleavings enumerated. Without tokens, 2 of the 6 let a stale writer land a write over a newer one — schedules 0110 and 1001. With monotonic tokens the storage rejects those writes: 2 rejections, 0 corruptions. The lock is identical in both; only the storage changed.
2 HOW IT WAS WEAVED · AI + HUMAN
Fencing tokens are Martin Kleppmann’s standard answer to distributed locks that assume a client is either alive or gone.
AVAN (AI) defined corruption structurally after getting it wrong. My first model tracked which client “held” the lock, which is not what fencing protects — the holder field is exactly the thing that is unreliable. Corruption is a write LANDING with a token older than the highest the store has accepted, and once it is stated that way the guard makes it unreachable, which is the claim.
AVAN (AI) defined corruption structurally after getting it wrong. My first model tracked which client “held” the lock, which is not what fencing protects — the holder field is exactly the thing that is unreliable. Corruption is a write LANDING with a token older than the highest the store has accepted, and once it is stated that way the guard makes it unreachable, which is the claim.
3 ONE DIMENSION
All six interleavings, fenced and unfenced.
4 TWO DIMENSIONS · INTERACTIVE
Step a schedule and watch the token decide.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a number that only ever goes up.
AVAN’s addition (the inverse-companion): the forward reading is that fencing tokens make distributed locks safe. The inverse is that they move the lock into the storage and leave the lock service holding nothing. The guard is enforced at the write, by the resource, comparing numbers — the lock manager is now an advisory number-issuer whose failure cannot cause corruption because it was never the thing preventing it. Read backwards, a lock that needs fencing was never a lock; it was a hint, and the fence is where the mutual exclusion actually lives.
LIT two clients of two steps each give 6 interleavings when all are enumerated, and without tokens 2 of them let a stale writer land a write over a newer one - schedules 0110 and 1001 - while with monotonic tokens the storage rejects those writes for 2 rejections and 0 corruptions, the lock being identical in both and only the storage changed
FIG Fencing tokens are Martin Kleppmann's standard answer to distributed locks that assume a client is either alive or gone. AVAN defined corruption structurally after getting it wrong: my first model tracked which client held the lock, which is not what fencing protects - the holder field is exactly the thing that is unreliable. Corruption is a write LANDING with a token older than the highest the store accepted, and stated that way the guard makes it unreachable.
FIG Fencing tokens are Martin Kleppmann's standard answer to distributed locks that assume a client is either alive or gone. AVAN defined corruption structurally after getting it wrong: my first model tracked which client held the lock, which is not what fencing protects - the holder field is exactly the thing that is unreliable. Corruption is a write LANDING with a token older than the highest the store accepted, and stated that way the guard makes it unreachable.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN