Fencing Tokens Block Stale Lock Holders

A distributed lock is often used to keep two workers from changing the same resource at once. The difficult case begins when lock ownership depends on a lease. A client can acquire the lease, pause long enough for it to expire, then resume after another client has acquired a new lease.

From the old client’s point of view, execution simply continued. From the coordination service’s point of view, ownership already moved. If the protected storage system accepts both clients’ writes, the old holder can overwrite work performed by the current holder.

A fencing token closes that gap. Each successful lease acquisition receives a token greater than every token issued for the same protected scope. The client carries that token to the resource. The resource accepts a mutation only when its token is not older than the greatest token already accepted.

Lease expiry does not stop a paused process

Consider two workers, A and B, using a lease with a finite lifetime:

t=0   A acquires lease, token = 41
t=2   A pauses
t=10  A's lease expires
t=11  B acquires lease, token = 42
t=12  B writes with token 42
t=14  A resumes
t=15  A writes with token 41

The coordinator behaves correctly. It gives B the lease only after A’s lease has expired. The remaining risk sits outside the coordinator: nothing about expiry can forcibly erase A’s in-memory state or prevent already-running code from reaching a storage API later.

Long garbage-collection pauses, scheduler stalls, suspended virtual machines, network partitions, overloaded hosts, and process freezes can all create this shape. A timeout can declare ownership stale, but it cannot make the stale process disappear.

This distinction matters because mutual exclusion at the coordinator is not identical to exclusion at the resource being protected.

The token turns ownership into an ordering rule

A fencing token is commonly a monotonically increasing integer associated with a lease acquisition:

acquire() -> lease, token

A: acquire() -> token 41
B: acquire() -> token 42

Every protected write includes the token:

write(resource, token=42, value=...)

The resource tracks the highest accepted token for the relevant scope. A simplified admission rule is:

if token < highest_accepted_token:
    reject

apply mutation
highest_accepted_token = max(highest_accepted_token, token)

After B’s write with token 42 is accepted, A’s later write with token 41 is stale by construction. A can resume, reconnect, retry, or continue local execution, but it no longer has authority to mutate that resource.

The important property is monotonicity, not elapsed time. The resource compares ownership generations rather than trying to infer whether a client’s clock or lease deadline is current.

A random lock identifier is not a fencing token

Many lock implementations return a random value and require that value when releasing the lock. That value is useful: it prevents one client from accidentally releasing another client’s lease. It does not establish an ordering between successive owners.

For example:

A lease id = 8f2c...
B lease id = 19ab...

Neither identifier says which acquisition came later. The storage layer cannot use those values to reject the older owner based on generation.

A fencing token carries order:

A token = 41
B token = 42

Unique ownership IDs and fencing tokens therefore solve different problems. A system may use both: an opaque lease ID for coordinator operations and a monotonic token for writes to the protected resource.

The resource must enforce the fence

Issuing tokens alone adds no safety. The component that can be damaged by a stale holder must participate in the protocol.

Suppose a worker obtains token 52 and writes to an object store through an API that ignores the token. Another worker later obtains token 53 and writes a newer object. If the first worker resumes and the object store accepts its delayed write, token generation at the lock service has not protected the object.

Enforcement can live directly in the storage system or in a trusted service that serializes access to it. The essential condition is that stale clients cannot bypass the comparison.

For a database row, the generation can be stored beside the data and checked atomically:

UPDATE jobs
SET result = :result,
    fence_token = :token
WHERE id = :id
  AND fence_token <= :token;

The exact predicate depends on the data model and whether repeated operations with the same token are valid. The comparison and mutation must form one atomic storage operation; a separate read followed by an unchecked write reintroduces a race.

Token scope must match the protected resource

A global counter can provide monotonic tokens, but global ordering is often broader than required. If leases protect independent resources, each resource only needs a reliable ordering among owners that can mutate that resource.

A system might fence per account, shard, document, job, or storage key. The coordinator and resource need a shared definition of that scope. A token generated for one scope cannot safely order owners of another unless the token scheme explicitly provides that property.

Scope also affects persistence. If the fencing sequence can reset after coordinator restart while the resource still remembers a larger accepted token, new valid holders may be rejected. Token generation therefore needs persistence or an epoch scheme that preserves ordering across coordinator recovery.

Renewal reduces expiry risk but does not remove stale holders

Lease renewal is useful when legitimate work can run longer than the initial lease duration. A worker can periodically extend its lease while it remains healthy.

Renewal still has a failure boundary. A pause can prevent renewal, a renewal request can be delayed, or the coordinator can become unreachable. Once the lease expires and another holder takes over, the old process may eventually resume.

Code that checks the lease before every write also has a timing gap if the check and the write are separate operations:

check lease -> valid
pause
lease expires
new holder acquires
old holder writes

The fence moves the decisive check to the resource mutation itself. The write carries evidence of its ownership generation, and the resource compares that generation atomically with its recorded state.

Fencing does not make every operation idempotent

Rejecting stale generations prevents an older holder from mutating a fenced resource after a newer generation has been accepted. It does not automatically deduplicate repeated writes from the same generation.

If a client sends the same charge, message, or side effect twice with token 60, both operations can still pass a rule that accepts token 60. Idempotency keys, unique constraints, transactional state transitions, or application-specific deduplication may still be required.

Fencing also does not repair side effects that cannot enforce the token. Sending an email, invoking an external service, or writing to a legacy system may require a different coordination boundary or an intermediary that can apply the generation check before producing the effect.

Tests should resume an expired holder deliberately

A useful concurrency test does not only verify that two clients cannot hold the same live lease. It forces the stale-holder path:

A acquires token 71
pause A
expire A lease
B acquires token 72
B writes successfully
resume A
A write with 71 is rejected

The final assertion is the core invariant. A process that once held a valid lease must lose write authority after a later ownership generation reaches the protected resource.

Additional cases can cover coordinator restart, token persistence, lease renewal failure, retries with the same token, independent resource scopes, and atomic comparison at the storage boundary.

A lease answers which client currently owns a coordination record. A fencing token carries that ownership generation to the place where stale execution can cause damage. Keeping those responsibilities separate makes pause-and-resume failures explicit: an expired holder may keep running, but the protected resource no longer accepts its authority.