Distributed Lock Correctness: Lease Expiry, Fencing Tokens, and Stale Write Rejection

Worker A obtains a ten-second lease and then pauses for two minutes, allowing the coordination service to let Worker B take over. When A resumes, it still has an in-memory boolean saying it "holds the lock," so it writes its old computation result to the database and overwrites B's newer result. The lock service correctly determined that the lease had expired, yet the business resource was still corrupted by a stale owner because it never validated the ownership generation.

Optimistic vs. Pessimistic Locking discusses conflicts within a single data system, while Distributed Consensus explains how a coordination service replicates state. This article does not compare lock algorithms again. Instead, it establishes an end-to-end proof from the coordination lease to the protected write. It also differs from Cross-Tab Leadership with Web Locks: here, resources span processes and machines, so client clocks cannot act as the arbiter.

A Lease Only Grants Permission to Attempt

Publish an immutable lockGrant.v1 that binds the resource canonical ID, owner workload identity, request ID, lease/session ID, grant operation root, monotonic fenceToken, coordination backend revision, policy generation, issuer/revocation epoch, server-side TTL, and operation category. The canonical registry signs or MACs the digest and provides a proof of the current grant status or a linearizable query. The token must come from a linearizable sequence for each resource; a client-provided UUID, wall clock, or local counter cannot serve as a fence.

schema: lockGrant.v1
resource: invoice-batch/2026-07-19
owner: worker-settlement-7
lease: lease-91
fenceToken: 8842
backendRevision: 1920184
policyGeneration: 12
operationRoot: sha256:51c...
issuerEpoch: 37
grantProof: sig:v4:8bd...
statusProof: HELD@revision-1920184
state: HELD

Local state transitions through REQUESTED -> HELD -> RENEWING -> HELD. An uncertain renewal or query result moves it into OWNERSHIP_UNKNOWN; server-confirmed expiry produces EXPIRED, while a successful voluntary release produces RELEASED. While in UNKNOWN, the worker stops creating new effects, but it cannot assume that writes already issued have been revoked. If an acquisition response is lost, processing may continue only if the grant can be queried using the same request ID. Otherwise, wait for the old attempt to expire and reconcile it; do not create a second identity and run both concurrently.

ZooKeeper ephemeral sequential nodes and etcd sessions/mutexes can coordinate candidates, but they do not automatically make another database reject an old process. The adapter must pass a monotonically comparable token to the resource with every mutation. If a downstream system can only accept locked=true and cannot atomically store the highest token, it does not support fenced writes. It must instead use a single-writer architecture or narrowly scoped operations that are idempotent and compensable. The Role of Redis in Distributed Systems likewise cannot substitute cache availability for a conditional write at the resource.

The Real Acceptance Point Is the Resource Write

The sole acceptance point, applyFencedMutation, first verifies the signature or MAC with a fixed trust bundle, then validates a short-lived status proof or performs a linearizable query against the canonical registry. The grant digest must bind the resource, owner, lease, operation root, fence, and policy generation exactly. The caller's workload identity must equal the owner, and the registry state must show the current HELD/not-revoked issuer epoch. A failure must not modify highestFence. After authentication, the resource transaction maintains highestFence, the root for that fence, lastSegmentSeq, and a receipt for every segment. A higher fence is accepted only with segmentSeq=1; an equal fence is accepted only for the next segment under the same root. Replaying an accepted segment with the same payload returns the original receipt, while a different payload is quarantined. A lower fence always returns STALE_OWNER. The business change, sequence number, and receipt are written in the same transaction.

Releasing the lock does not mean the business operation completed. If A's write times out and its lease subsequently expires, the result enters MUTATION_UNKNOWN. The recovering worker first queries the resource receipt by operation ID. If the mutation was accepted, it reuses that result. Only after proving that it did not occur may a new fence submit a new operation. If the outcome cannot be determined, manual or domain-specific reconciliation is required. This boundary resembles Multi-Agent Task Claims, but databases, object storage systems, and third-party APIs must each provide equivalent fencing or stable effect queries.

Long-running jobs divide large batches into small segments. All segments share the grant operation root, but use strictly increasing segmentSeq values and revalidate the fence on every commit. Concurrently computed segments may only be accepted in the contractually defined order. A downstream asynchronous worker also carries the fence, root, and segment. If a new owner has already raised highestFence, the old owner is rejected even if it holds an unused later sequence number. If the coordination cluster restores an old snapshot and causes the token to regress, trigger FENCE_REGRESSION; never clear the highest value merely to restore traffic.

Inject Pauses, Partitions, and Generation Regressions

The failure matrix includes an owner pause extending beyond the TTL, a lost renewal response, interleaved release and reacquisition, out-of-order/duplicate/different-payload segments, delayed old messages, restoration of an old coordination-backend snapshot, a lost transaction ACK, forged oversized tokens, tampered grant digests, cross-resource proof replay, and use of a revoked issuer epoch. Assert that accepted forged/tampered/cross-resource proofs equal 0, authentication failures that contaminate highestFence equal 0, and accepted writes from expired owners, skipped segment numbers, or regressed tokens all equal 0.

Release gates require zero accepted stale writes and forged grants across 100,000 scheduling tests, 100% coverage of protected mutations by canonical grant authentication and fence checks, lock-handoff p99 below budget, and reconciliation of UNKNOWN outcomes within 15 minutes. Rollout begins by validating proofs and tokens in shadow mode, then rejecting writes for one low-risk resource before expanding coverage. Rollback may switch to the previous coordination client, but resource-side proof and fence validation must never be disabled. The trust bundle may only be rotated through a controlled process, and a new client must continue from a range above the existing highest value; otherwise, writes must pause.