Locks, leases and fences: why mutual exclusion is unavailable

Why is there no distributed lock, only a lease plus a fence the resource checks?

The derivation is short, and the conclusion is stronger than most people expect.

1. A distributed lock with no expiry is a liveness bug: if the holder dies, the resource is blocked forever.
2. Therefore locks must expire. Therefore they are leases.
3. Therefore there exists an interval during which the issuer considers the lease expired and the holder considers it held. The holder cannot close that gap, because the gap is not network delay but its own delay between checking and acting.

A 15-second GC pause, a descheduled thread, a blocked write to a slow disk: the check passed, the action lands afterwards, and no clock synchronization helps, because both readings were taken on the same machine.

holder:   if (lease.isValid()) {      // check passes at t = 0
              ...                     // <-- 15 s GC pause here, lease expired at t = 10 s
              storage.write(x)        // lands at t = 15 s, after a new holder was granted the lock
          }

Therefore there is no distributed lock. There is a lease plus a fence. The lease bounds ordinary behaviour. The fencing token, the same monotonic counter as the epoch, makes the late action harmless: the resource rejects any write stamped with a token below the highest it has seen.

lock service:  grant(holder A, token = 33)     ... lease expires ...
               grant(holder B, token = 34)
B writes  (token 34)  -> resource: highest_seen = 34, accept
A wakes, writes (token 33) -> resource: 33 < 34, REJECT

The consequence practitioners most often miss: fencing requires the resource to participate. If the storage system cannot compare and check a token, the lock service has bought you a reduction in probability, not mutual exclusion, and the failure is silent and corrupts data. This is why the arrival of conditional writes on object stores (a write that succeeds only if a stated condition holds, for example "only if the version is still 5") was a coordination event and not a convenience feature: it gave the storage layer for the first time the ability to refuse a stale writer. Where the resource genuinely cannot participate, the only remaining fence is physical: STONITH ("shoot the other node in the head": power the suspect node off). It is the honest admission that "not the leader" had to be made a fact about the world, because it could not be made a fact about bookkeeping.

Seen from the other side, a lease is a cache entry whose value is authority and whose freshness bound is a TTL. Like every TTL, it converts a coordination round trip into a local decision for its duration. A leader lease lets the leader serve linearizable reads with zero RTTs, because it holds a time-bounded cached fact that no one else may lead. That is the "fixed cost gives a natural batch" idea with time as the batch: the fixed cost of confirming leadership is amortized over the lease period. Leadership is batching of coordination, which is why leaderless protocols pay two message rounds where leader-based ones pay one.

It is also the one mechanism in this article whose safety depends on a clock. Specifically it depends on a bound on drift rate, not on offset, since both endpoints measure an interval and do not compare timestamps. That is a cheaper assumption than clock synchronization. It is still an assumption, and it still requires the fence behind it.

Compression: expiry makes locks into leases, leases make ownership ambiguous at the boundary, and only a token checked by the resource itself converts that ambiguity from corruption into a rejected request.