Skip to content

Lease and Fencing-Token Protocol

Coordination protocol — instantiates Shared-State Consistency Contract Design

Grants exclusive access for a bounded, time-limited lease and stamps each protected action with a monotonic fencing token, so a delayed or revived holder is rejected instead of corrupting state.

A Lease and Fencing-Token Protocol grants a client the exclusive right to act on shared state — hold a lock, be the leader, own a shard — but only for a bounded lease period, and pairs every grant with a monotonically increasing fencing token. Its distinguishing move addresses the failure naive locks ignore: a lock-holder that pauses (a long garbage-collection stall, a network freeze) past its lease can wake up still believing it holds the lock. Fencing defeats this by making the protected resource itself reject any action carrying a token older than the newest it has seen — so it is not enough to hold the lease; your token must still be current at the moment the write lands.

Example

A job scheduler uses a lock service so that only one worker writes to a results file in object storage at a time. Worker A acquires the lease and gets fencing token 33. Mid-write, Worker A stalls for a long GC pause; its lease expires, and the lock service grants the lease to Worker B with token 34. Both workers are now "alive." Without fencing, A resumes and writes to the file, corrupting B's work. With fencing, every write to the storage carries its token; the storage remembers it has already accepted token 34, so when A's delayed write arrives stamped 33, the storage rejects it. Correctness no longer depends on A noticing it lost the lease — the resource enforces single-writer safety on its own.

How it works

The distinctive thing is that safety is enforced at the resource, under an explicit clock/fault model, not at the client. The lease is time-bounded, so leadership expires automatically if the holder goes silent — surviving crash and partition without a human in the loop. But because a paused-then-revived holder cannot be trusted to respect expiry, each grant also carries a token that strictly increases; the protected resource records the highest token it has honored and refuses anything lower. The protocol states its assumptions openly: bounded clock drift for lease expiry to be meaningful, and crash-stop / partition (not Byzantine) faults.

Tuning parameters

  • Lease duration — short leases fail over fast when a holder dies but risk expiring under normal pauses (false loss); long leases are stable but leave the resource idle longer after a real failure.
  • Clock-skew margin — how much drift the expiry logic assumes; too tight and a lease "expires" early on skewed clocks, too loose and two holders overlap.
  • Token scope — one fencing sequence per resource vs. per shard; finer scope isolates contention but multiplies bookkeeping.
  • Renewal cadence — how aggressively a holder heartbeats to keep its lease; frequent renewal cuts false expiry at the cost of chatter.

When it helps, and when it misleads

Its strength is making mutual exclusion safe under the faults that break naive locks: pauses, partitions, and revived zombies cannot corrupt state, because the resource — not the client — has the final say. Its correctness is only as good as its assumptions: leases lean on bounded clock skew, and fencing requires the protected resource to actually check the token — a resource that ignores tokens gets no protection at all.[1] The classic misuse is using a bare lease (or a lock with a TTL) without fencing and assuming the holder will politely stop when it expires — exactly the assumption a GC pause violates. The discipline is to carry a fencing token all the way through to the resource and make the resource enforce it, and to state the clock and fault assumptions the lease depends on rather than leaving them implicit.

How it implements the components

  • write_acceptance_rule — the fencing token is a write-acceptance rule: the protected resource accepts an action only if its token is the highest seen, rejecting stale holders.
  • fault_partition_and_clock_assumptions — the protocol is built around an explicit fault/clock model (bounded skew, crash-stop, partition) and makes safe exclusion depend on those stated assumptions.

It guarantees a single safe writer but does not itself replicate or order the data a leader writes — that log and topology are Leader-Based Replication's — nor does it generate the timestamps used for ordering, which come from Hybrid Logical Clock.

References

[1] Fencing tokens — a monotonically increasing number handed out with each lock grant and checked by the resource on every write, so that a stale lock-holder's late write is rejected. This is the standard fix for the "a lease alone is not enough" problem in distributed locking: expiry cannot bind a process that is not running to notice it. ↩