A distributed mutual-exclusion lock is built directly on top of the lease idea: "acquiring a lock" just means successfully claiming a key that's tied to a TTL, so a crashed holder's lock is automatically released once its lease expires -- instead of staying locked forever, which is the classic failure mode of a naive distributed lock with no expiry.

now is always caller-supplied, same as the other exercises in this course.

The missing link: knowing you have a lock isn't the same as still having it

A bare acquire()/release() pair has a real gap: a holder can only know what IT observed, and its observation can be stale -- a slow clock, a GC pause, a slow network link -- so it can keep believing it holds the lock well after that lock has actually expired and been reclaimed by someone else. If that holder then goes and does something to the resource the lock was protecting (writes a file, commits a value), two holders can act as if each has exclusive access at the same time -- the exact failure distributed locking exists to prevent.

Fencing tokens close this gap by moving the check to the RESOURCE being protected, not the lock itself: every successful acquire returns a token that strictly increases across acquisitions of the same key. The resource remembers the highest token it's seen and rejects any request carrying an older one -- so even a holder that never got word its lock expired gets rejected the moment it tries to act, because a newer holder's token has already superseded it.

Implement:

• acquire(key, holder_id, now, ttl): try to acquire key for holder_id, valid until now + ttl. Succeeds if the key is unlocked, its existing lock has expired, OR it's already held by this same holder_id (a renewal) -- on success, return a NEW fencing token (a plain increasing int; the first token ever issued is 1). Fails (returns None, no state change) if it's held by a DIFFERENT holder and still alive (now < its expiry).
• release(key, holder_id, now): release key, but ONLY if it's currently held by holder_id AND still alive -- releasing a lock you don't hold (or one that already expired and was reclaimed by someone else) must be a complete no-op. Never release someone else's lock.
• is_valid_token(key, token): is token the CURRENT token for key right now? False if key isn't locked at all, or is locked under a different (necessarily newer) token.

Example

lock = DistributedLock()
t1 = lock.acquire("resource", "client-a", now=0, ttl=10)    # -> 1
lock.acquire("resource", "client-b", now=5, ttl=10)          # -> None (a still holds it)
t2 = lock.acquire("resource", "client-b", now=10, ttl=10)   # -> 2 (a's lock expired at 10)
lock.is_valid_token("resource", t1)                          # -> False -- t1 is stale
lock.is_valid_token("resource", t2)                          # -> True -- t2 is current

Constraints

• The SAME holder re-acquiring is always allowed (it's how a holder renews its own lock while doing long-running work) -- only a DIFFERENT holder is blocked while the current lock is alive. A renewal still issues a brand new token; the holder's own previous token becomes invalid too.
• release must check BOTH that the caller is the current holder AND that the lock hasn't already expired (and possibly been reclaimed by someone else) -- releasing based on holder identity alone, without the liveness check, could accidentally release a lock that's already been legitimately acquired by a third party.
• Tokens only ever increase, globally across every key this DistributedLock manages -- never reused, never reset per-key.

Real-world grounding

• etcd's lease-based locking, the actual mechanism etcdctl lock and most etcd client libraries' distributed lock implementations use underneath: server/lease/lessor.go

Production distributed locks (etcd's, ZooKeeper's, Redis's Redlock) all add fencing tokens for exactly the reason described above -- Martin Kleppmann's critique of Redlock is the widely-cited writeup of why a lock's own acquire/release state is never sufficient on its own, and why the resource being protected has to be the one enforcing the token check.