Leader election is one of those problems people consider solved. Put a Lease object in Kubernetes, or a key in etcd, or a row in Postgres, have every replica try to grab it, and whoever holds it is the leader. It works in the demo. It works for months.
Then a leader gets paused for 15 seconds, by a long garbage collection, by CPU throttling, by a live migration of the VM it’s on. Its lease expires. Another replica takes over and starts doing work. And then the first one wakes up and finishes what it was doing, because from inside the process, no time has passed at all.
For a few seconds you have two leaders. Leader election didn’t fail. It did exactly what it says it does. The gap is in what we assume it does.
The lease expired. The process didn’t notice.
A lease is a lock with a timer. You hold it until it expires, and you renew it to keep holding it. The timer is what makes it useful: if the holder crashes, nobody has to detect the crash, the lease simply runs out and someone else can take it.
But the timer runs on the lock service’s clock. The holder only learns its lease is gone the next time it checks. Between checks it’s acting on a belief, and beliefs can be stale.
The obvious fix is to check the lease right before every write. It doesn’t work. Martin Kleppmann laid this out in How to do distributed locking back in 2016: the pause can land between the check and the write. The check passes, the process freezes, the lease expires, someone else takes over, and then the write goes out. A slow network does the same thing without any pause at all: the write can sit in a buffer long enough for its lease to expire in transit.
There’s no check you can add on the client side that closes this window, because the client is the thing that’s been paused.
Kubernetes is upfront about this. The client-go leaderelection docs say it in one sentence: “This implementation does not guarantee that only one client is acting as a leader (a.k.a. fencing).” The defaults used by core components (a 15 second lease, a 10 second renew deadline, a 2 second retry period) are tuned to make overlap rare. Rare isn’t never.
Fencing tokens: let the resource say no
The fix moves the check to the only place that can actually enforce it: the thing being written to.
Each time the lock service grants the lease, it also hands out a fencing token, a number that goes up by one with every grant. The holder sends its token with every write. The storage remembers the highest token it has accepted and rejects anything lower.
Walk through the failure again. Worker A gets the lease with token 33, then pauses. The lease expires. Worker B gets token 34 and writes. Worker A wakes up and sends its write with token 33. Storage has already seen 34, so it refuses. A finds out it’s no longer the leader at the moment it tries to do damage, which is exactly the moment that matters.
Here’s a simulation: three workers, a 10 second lease, a 2 second read-modify-write on a counter, and a 3% chance that a worker gets paused for 12 to 20 seconds mid-write. An hour of simulated time, run once without fencing and once with it.
"""Leases without fencing tokens, simulated.
A lock service grants a 10 s lease. Each worker holds the lease while it does a
read-modify-write on a shared counter that takes 2 s. Now and then a worker is
paused (GC, VM steal, a slow syscall) for 12-20 s mid-write. Its lease expires,
another worker takes over, and then the paused worker wakes up and finishes
the write it started, still believing it is the leader.
"""
import random
LEASE, WORK, PAUSE_P, SECONDS = 10.0, 2.0, 0.03, 3600
class LockService:
def __init__(self):
self.holder, self.expires, self.token = None, 0.0, 0
def acquire(self, who, now):
if self.holder is None or now >= self.expires:
self.holder, self.expires = who, now + LEASE
self.token += 1 # strictly increasing, one per grant
return self.token
return None
class Storage:
def __init__(self, fenced):
self.fenced, self.value, self.max_token = fenced, 0, 0
self.applied = self.rejected = 0
def write(self, value, token):
if self.fenced and token < self.max_token:
self.rejected += 1 # a newer leader has already written
return False
self.max_token = max(self.max_token, token)
self.value = value
self.applied += 1
return True
def run(fenced, seed=7):
rnd = random.Random(seed)
lock, store = LockService(), Storage(fenced)
workers = {w: None for w in "ABC"} # w -> (token, read_value, finish_at)
increments = 0
t = 0.0
while t < SECONDS:
for w, job in workers.items():
if job is None:
token = lock.acquire(w, t)
if token is not None:
pause = rnd.uniform(12, 20) if rnd.random() < PAUSE_P else 0
workers[w] = (token, store.value, t + WORK + pause)
elif t >= job[2]:
token, read, _ = job
if store.write(read + 1, token):
increments += 1
if lock.holder == w:
lock.holder = None # release
workers[w] = None
t += 0.5
lost = increments - store.value
return (f"{'fenced ' if fenced else 'unfenced'} | writes applied {store.applied:5d} | "
f"rejected {store.rejected:3d} | counter {store.value:5d} | lost updates {lost:3d}")
print(run(fenced=False))
print(run(fenced=True))
unfenced | writes applied 1478 | rejected 0 | counter 1403 | lost updates 75
fenced | writes applied 1429 | rejected 49 | counter 1429 | lost updates 0
Without fencing, 75 increments vanished. Every one of them was a write that “succeeded”: no error, no exception, nothing in the logs. A paused worker woke up holding a value it had read 15 seconds earlier and wrote it back over everything that happened in between. With fencing, 49 stale writes were refused and the counter is exactly right.
That’s the part worth sitting with. The unfenced version doesn’t crash or alert. It’s just quietly wrong, and you’d find out from a reconciliation report weeks later, if you have one.
Where the token check actually lives
Fencing only works if the storage enforces it atomically with the write. A separate “read the max token, then write” in your application has the same race you started with. Push the check into the write itself.
In Postgres, that’s a conditional update:
-- One row per fenced resource, carrying the highest token that has written to it.
UPDATE job_state
SET payload = $1,
fence_token = $2
WHERE job_id = $3
AND fence_token <= $2; -- equal: same leader writing again; lower: rejected
-- 0 rows updated => a newer leader has already written. Stop, don't retry.
In object storage, use conditional writes (an If-Match on the object’s ETag) and keep the token in the object. In etcd, use a transaction that compares the key’s revision or a token field before putting. The pattern is always the same: the write carries proof of when the writer’s authority was granted, and the receiver compares it in the same atomic step.
One gap the simulation doesn’t happen to hit: a fencing token only rejects a stale write once the new leader has written something. If the old leader wakes up in the short window before the new leader’s first write, its write is accepted, and the new leader’s read-modify-write can then clobber it. If your writes are read-modify-write, have the new leader record its token at the start of its term (a cheap write that raises fence_token), or make the update a compare-and-set on a version column as well. Fencing stops stale leaders. It doesn’t make a read-modify-write atomic.
The client side has one job: when a write is rejected for a stale token, stop acting as the leader. Don’t retry. A rejection is the most reliable signal you’ll ever get that someone else has taken over.
What about Kubernetes Leases?
A Kubernetes Lease records holderIdentity, leaseDurationSeconds, acquireTime, renewTime and leaseTransitions. Updates go through the API server’s optimistic concurrency, so two candidates can’t both win the same acquisition.
leaseTransitions is the closest thing to a fencing token it gives you: it increments when the lease changes hands. If you pass it to downstream systems and they check it, you have fencing. Two caveats. It’s maintained by the election client, not enforced by the API server, so it’s only as reliable as the code updating it. And if someone deletes and recreates the Lease, it starts again from zero. If you need a token that can never go backwards, generate it somewhere that guarantees that, such as a database sequence or an etcd revision.
Most operators don’t need any of this, because what they write to is the Kubernetes API itself, with resourceVersion checks on every update. The reconciliation loop is idempotent, so two leaders briefly doing the same work mostly costs some wasted API calls. Fencing starts to matter when the leader writes to something outside the cluster that has no idea who the current leader is: a database, a bucket, a payment API, a DNS provider.
Agents make this worse
This used to be a niche concern for people writing storage systems. It’s becoming everyone’s concern, because we’re putting AI agents in charge of actions, and agents have very long, very variable pauses built in. A model call that usually takes 3 seconds sometimes takes 60. An agent can take a lease, decide to scale a service down, wait on a slow model response, and wake up after a second agent has already taken over and decided the opposite.
If two remediation agents can touch the same resource, give them a lease and a fencing token, and make the action endpoint check it. A model-call timeout is just a GC pause with a bigger bill.
A checklist
- List what your leader writes to. For each target, ask: what happens if two leaders write to it for ten seconds?
- If the answer is “nothing bad” (idempotent writes, a reconcile loop, writes to the Kubernetes API with
resourceVersion), leader election alone is fine. - If the answer is “data gets lost or duplicated”, add a fencing token from a source that can’t go backwards, and check it inside the write.
- Treat a stale-token rejection as a demotion. Stop leading, release, re-campaign.
- Don’t try to fix it by shortening the lease. That makes the window smaller and failovers more frequent. Keep timing for liveness and the token for safety.
Leader election tells everyone who’s supposed to be the leader. A fencing token is how the rest of the system checks.
Related: Raft: How a Cluster of Machines Agrees on a Single Truth · Clock Skew: Why now() Is the Least Trustworthy Function You Call · Idempotency Keys: The Thing That Makes a Retry Safe · Garbage Collection: The Convenience That Shows Up in Your p99
Comments