A Lease Is Permission to Try; a Fencing Token Is Permission to Win

A distributed lease answers a coordination question: who may act now? It does not, by itself, answer the safety question that matters at the resource boundary: which actor may make an effect stick?

The gap appears whenever a leaseholder pauses, is partitioned, or has a response delayed beyond its expiry. A new holder can legitimately acquire the lease while the old holder still believes it owns it. If the old holder can write directly to the protected resource, a perfectly ordinary lease implementation can still permit stale work to overwrite current work.

The invariant

For each protected resource, attach a monotonically increasing fencing token to every lease grant. The resource that commits the effect must durably remember the largest token it has accepted, and it must reject every request with a token no greater than that value.

No effect authorized by token n may be accepted after an effect authorized by a higher token for the same resource.

That comparison belongs at the real arbiter: the database row, message broker, object store gateway, actuator, or whatever system makes the irreversible decision. A client-side check, cache, or coordinator-side log cannot protect an authority that never sees the token.

The failure that leases alone cannot prevent

1. Worker A receives lease token 41 and then pauses for a long GC stop.
2. Its lease expires. Worker B receives token 42 and commits the current update.
3. A resumes and sends its old update.

Expiry did not revoke packets already in flight. Without fencing, the receiver cannot distinguish A's stale request from an authorized one. With fencing, the receiver has recorded 42 and rejects 41 atomically.

This is not a timing trick. Clock skew, a slow coordinator, and a long network delay only make the counterexample easier to trigger. The safety rule relies on ordering, not on an estimate that everyone agrees about time.

What must be durable and atomic

A useful lease state machine is:

Unheld --grant(n)--> Held(n) --expire/release--> Unheld --grant(n+1)--> Held(n+1)

The grant path needs a durable, strictly increasing sequence per coordination scope. The resource path needs an atomic conditional effect, conceptually:

apply update where resource_id = :id and last_fence < :token

Then persist last_fence = :token in the same transaction as the business effect. If recording the token and applying the effect can be separated by a crash, stale work can re-enter through that gap.

A renewed lease may retain its token if it never lost ownership; a reacquisition after uncertainty must receive a higher one. A timestamp is not an adequate substitute for a fence: it is not a durable serialization point and it has ambiguous behavior under rollback and skew.

Design consequences

• Scope tokens to the contention domain. A per-object sequence gives more concurrency than a global sequence, provided all conflicting effects share that object's fence.
• Propagate the token end-to-end. Queue consumers, asynchronous workers, and downstream writers must carry it; otherwise a stale actor can cross an async boundary and lose the proof of staleness.
• Specify rejection as normal recovery. A rejected stale effect should be observable and should cause the worker to reread state, not be treated as an inexplicable transport failure.
• Test the pause, not only the timeout. Inject a pause after grant and before commit; allow another worker to acquire and commit; then release the paused request. The old request must be rejected every time.

Leases optimize who should work. Fencing tokens establish which work may change reality. Systems that need both liveness and safety should name-and enforce-both contracts.