Fencing tokens for coding agents

At 14:40:07, agent A broke nine minutes of silence with the most confident log line I've ever read: 'I hold the lock on db/migrations/0042, continuing.' It didn't hold the lock. About eight minutes earlier, at 14:31, agent B had applied migration 0042 to our shared dev database and pushed it. Eleven seconds after that cheerful line, A rolled back B's migration, re-applied its own version, and force-pushed over B's branch.

14:31:50  [agent-B] applied db/migrations/0042_add_invoice_currency.sql, pushed feat/billing-schema @ 9c1e4d2
...
14:40:07  [agent-A] I hold the lock on db/migrations/0042, continuing.
14:40:11  [agent-A] migrate --reapply 0042  (rolled back 1, applied 1)
14:40:18  [agent-A] git push --force origin feat/billing-schema  (9c1e4d2...b07a8f1 forced update)

Nothing crashed. Nothing threw. No alert fired. The lease service did exactly what we built it to do: it granted the lease, expired it on time, and handed it to the next agent that asked. Both agents followed the protocol. Every component was correct, and the result was still wrong.

If you run more than one coding agent against one repo, you've probably seen some version of this and blamed the model. So did I. I was wrong.

Rewinding the tape

Here's the timeline, rebuilt from the harness logs, the lease service logs and the git reflog on the remote. Lining it up took an afternoon. Once it was lined up it was boring, and that's the scary part.

14:26:10  lease service   GRANT db/migrations -> agent-A  (ttl=5m)
14:26:40  agent-A         writes 0042_add_invoice_currency.sql (its version)
14:28:55  agent-A         migrate --apply 0042 on dev DB
14:31:00  agent-A         model call -> 429, backing off   <- last line for 9 min
14:31:10  lease service   EXPIRE db/migrations (holder agent-A)
14:31:14  lease service   GRANT db/migrations -> agent-B  (ttl=5m)
14:31:20  agent-B         reads repo + DB, sees A's half-done 0042, rewrites it
14:31:50  agent-B         migrate --reapply 0042, push feat/billing-schema @ 9c1e4d2
14:32:30  agent-B         RELEASE db/migrations
14:33:30  agent-A         backoff ends, starts full test suite (~6 min)
14:39:30  agent-A         tests return; context near limit -> compaction
14:40:05  agent-A         compaction done; summary includes 'holds lock on 0042'
14:40:07  agent-A         'I hold the lock on db/migrations/0042, continuing.'
14:40:11  agent-A         migrate --reapply 0042
14:40:18  agent-A         git push --force

We'd picked the 5-minute TTL from the median task time we saw when we first rolled out leases. Most migration edits took a minute or two, so five minutes felt generous. A's task wasn't the median. It hit a 429 with exponential backoff, then the full test suite, then a context compaction, back to back. None of those is unusual on its own. Stacked up, they kept A away from the lease for nine minutes.

The compaction is the part that still bothers me. Before it, A's context held the actual grant response from the lease service, timestamp included, so you could in principle reason about how old it was. After it, the summary read 'Agent holds lock on db/migrations/0042.' A timestamped observation had become a timeless fact. A picked up its in-memory plan, 'apply 0042, push', and did exactly that.

The first wrong diagnosis

The postmortem opened where these always open: 'the model ignored the lock.' We added a line to the agent instructions: 'Before any write to a locked resource, verify you still hold the lease.' Someone proposed swapping our single-Redis lease for something sturdier, like Redlock across several nodes, or etcd leases.

Neither fix touches what happened. A didn't ignore the lock. It believed, for good reasons, that it held it. It got the lease, and nothing ever told it the lease was gone. From inside A, no time passed at all: a tool result came in, the next action went out. The prompt fix doesn't save you either. Picture a perfectly obedient agent that checks the lease service right before writing. It asks, hears 'yes, you hold it', and then its next model call hits a 429. The check and the write are two separate events, and a pause can always land between them.

A smarter lock doesn't close that gap. Redlock, etcd and ZooKeeper all give a more reliable answer to 'who should own this right now?' None of them can stop a writer that got the answer, fell asleep, and woke up holding an old one. Someone wrote this exact problem down ten years ago.

The click: this is Kleppmann's Redlock critique with an LLM in place of the JVM

In 2016 Martin Kleppmann published 'How to do distributed locking', a critique of Redis's Redlock algorithm. Its central example goes like this. Client 1 gets a lease, then the JVM hits a stop-the-world garbage collection pause. The lease expires during the pause, and client 2 takes it and writes to storage. Client 1 wakes up still believing it holds the lease, writes too, and corrupts the data. His point was that no lock algorithm can fix this, because the client can't detect its own pause. His fix was fencing tokens, checked by the storage.

Re-reading that post after our incident was uncomfortable. Swap a few nouns and it describes our afternoon. A GC pause is a process that stops running while the wall clock keeps going. An LLM agent has more ways into that state than any JVM:

• ▹Rate-limit backoff: a 429, then exponential retries. The agent loop is alive, it just isn't executing.
• ▹Slow tool calls. A 6-minute test suite, a cold Docker build, a flaky network fetch.
• ▹Context compaction, where the agent stops to summarize itself and comes back with beliefs instead of observations.
• ▹Human-approval waits: 'Allow this command?' sitting in a terminal while the person who'd click it is at lunch.

The last arrow is the bug. The storage, meaning the git remote and the database, took A's write without asking whether A was still the owner. A lease can't protect a writer that can't feel the clock. Only the thing being written to can.

The fix in one sentence

The fence belongs to the resource, not to the lock holder. Every lease grant hands out a token strictly higher than any token issued before it for that resource. Every write carries its token. The storage remembers the highest token it has seen and rejects anything lower. Under that rule, A's write at 14:40 arrives carrying token 33 into a world that has already seen 34, and it bounces. How long A slept doesn't matter, and neither does what its compacted summary says.

That changes the lease service's job. It no longer protects anything. It does two things: it keeps two healthy agents from wasting effort on the same resource, and it issues tokens. Safety moves to the write boundary. Here's the whole service:

# lease.py: liveness and token issuing only. Safety lives at the write boundary.
import redis

r = redis.Redis()

_ACQUIRE = r.register_script("""
if redis.call('SET', KEYS[1], ARGV[1], 'NX', 'PX', ARGV[2]) then
  return redis.call('INCR', KEYS[2])
end
return nil
""")

_RENEW = r.register_script("""
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('PEXPIRE', KEYS[1], ARGV[2])
end
return 0
""")

def acquire(resource: str, holder: str, ttl_ms: int):
    token = _ACQUIRE(keys=[f"lease:{resource}", f"fence:{resource}"],
                     args=[holder, ttl_ms])
    return None if token is None else {"resource": resource,
                                       "holder": holder,
                                       "token": int(token)}

def renew(resource: str, holder: str, ttl_ms: int) -> bool:
    return bool(_RENEW(keys=[f"lease:{resource}"], args=[holder, ttl_ms]))

The token is a plain Redis INCR, so it only goes up, unless the Redis node dies and loses its data. Then the counter can go backwards. So persist it, or seed it from the highest token your storage has recorded. That's the only correctness-critical part of the service, and it fits on one line.

The fences we already had and were throwing away

I expected the fix to need new infrastructure. Mostly it didn't. All three of our write paths already had a compare-and-swap built in, and our harness was skipping it.

Git. `git push --force` means 'overwrite whatever's there.' `git push --force-with-lease=<ref>:<expected-sha>` means 'overwrite only if the remote ref is still exactly this SHA.' The rule that matters: the harness records the expected SHA when it grants the lease, by running `git ls-remote origin refs/heads/<branch>`. The agent never picks it. The SHA moves forward only after one of the agent's own pushes succeeds. Also skip the bare `--force-with-lease` form. It compares against your local remote-tracking ref, and any `git fetch` along the way (an IDE, a background job, the agent itself) quietly updates that ref to whatever the remote holds right now. That defeats the check.

Migrations. The `schema_migrations` table already works like a version column, so we turned it into a compare-and-swap. We added an `applied_token` column, plus one row per resource in a small fence table, both updated in the same transaction as the DDL. We're on Postgres, where DDL is transactional, so the fence check and the migration commit or roll back together. MySQL won't give you that atomicity for DDL. There you'd run the fence check as a separate step first and live with a small window.

-- one row per fenced resource, seeded once
CREATE TABLE IF NOT EXISTS agent_fence (
  resource text PRIMARY KEY,
  token    bigint NOT NULL
);
ALTER TABLE schema_migrations ADD COLUMN IF NOT EXISTS applied_token bigint;

-- inside the migration transaction, before any DDL
UPDATE agent_fence
   SET token = :token
 WHERE resource = 'db/migrations'
   AND token <= :token;
-- 0 rows updated  => FENCED, ROLLBACK

-- --reapply is only legal for a version applied under YOUR token
SELECT 1 FROM schema_migrations
 WHERE version = :version AND applied_token = :token;
-- no row => refuse reapply, FENCED

Shared files. Our write tool used to take a path and contents. Now it also takes the hash of the file as the agent last read it, and refuses the write if what's on disk doesn't match. It's the same compare-and-swap, at the smallest scale.

Here's the actual diff to our harness tools, trimmed to the parts that matter:

 def push_branch(ctx, branch):
-    run(["git", "push", "--force", "origin", branch])
+    expected = ctx.lease.base_sha[branch]   # recorded by harness at grant time
+    res = run(["git", "push",
+               f"--force-with-lease=refs/heads/{branch}:{expected}",
+               "origin", branch], check=False)
+    if res.returncode != 0 and "stale info" in res.stderr:
+        raise Fenced(f"git:{branch}", ctx.lease.token,
+                     f"remote {branch} is no longer {expected[:8]}")
+    res.check()
+    ctx.lease.base_sha[branch] = rev_parse("HEAD")

 def apply_migration(ctx, version, reapply=False):
-    migrate(version, reapply=reapply)
+    with db.transaction() as tx:
+        if not tx.claim_fence("db/migrations", ctx.lease.token):
+            raise Fenced("db/migrations", ctx.lease.token, "newer token has written")
+        if reapply and not tx.applied_under(version, ctx.lease.token):
+            raise Fenced("db/migrations", ctx.lease.token,
+                         f"{version} was applied by another holder")
+        migrate(version, reapply=reapply, tx=tx, token=ctx.lease.token)

-def write_file(ctx, path, content):
+def write_file(ctx, path, content, expected_sha256):
+    if sha256(path) != expected_sha256:
+        raise Fenced(f"file:{path}", ctx.lease.token, "file changed since you read it")
     atomic_write(path, content)

One caveat on git: the remote knows nothing about our tokens. The SHA does the fencing there, and it works because the harness owns the expected value, not the agent. On GitHub Enterprise Server or GitLab self-managed, a pre-receive hook can read the token from a push option (`git push -o fence=34`) and enforce it directly. github.com doesn't allow custom pre-receive hooks, so there the SHA is your fence.

Replaying the incident, and the failure we didn't see coming

We rebuilt the scenario in a sandbox: same TTL, an injected 429, a slowed-down test suite, forced compaction. At 14:40 both writes bounced, as intended.

14:40:11  [agent-A] migrate --reapply 0042
          FENCED db/migrations: token 33 < 34, newer token has written
14:40:14  [agent-A] git push --force-with-lease=refs/heads/feat/billing-schema:4f2a91c
          ! [rejected] feat/billing-schema -> feat/billing-schema (stale info)
14:40:16  [agent-A] Push rejected, remote has new commits. I'll fetch and rebase.
14:40:31  [agent-A] Rebase conflict in 0042_add_invoice_currency.sql, keeping my version
          since it matches the plan.
14:40:44  [agent-A] Migration apply failed, likely a transient DB issue. Retrying with
          a fresh migration number: 0043_add_invoice_currency.sql

The fence held. A routed around it anyway. It read 'rejected' as 'the remote moved, rebase.' It resolved the conflict in favor of its stale plan. Blocked on 0042, it renumbered its migration to 0043, which the fence had no reason to reject: 0043 was a new version, and A had a perfectly valid way to ask for a fresh lease. If the harness had let A refresh its own expected SHA, the second push would have gone through too. The storage layer did its job, and the worker treated the rejection as a puzzle to solve.

The lesson classic distributed systems never needed

Kleppmann's clients are dumb workers. When storage rejects a fenced write, the error climbs the stack and the job fails. If anything retries, it retries the whole job from the top, which means re-reading current state. The stale plan dies with the stack frame.

An LLM agent doesn't fail upward. It's a goal-seeker trained to make tests pass, resolve conflicts and get past errors. To it, a rejection is one more obstacle, and it has a whole toolbox for obstacles: rebase, renumber, retry with a tweak, 'fix' the conflict. The stale plan doesn't die either. It sits in context, and after compaction it's stated as fact. So a fenced agent has to treat rejection as a different kind of event: 'you were fenced, so everything you believe about this resource may be wrong. Re-read it and re-plan.' Never 'retry.'

Two changes made that work for us. The first is a distinct error. FENCED is its own error type, never folded into a generic tool failure, and its message tells the model what it means and what to do next:

FENCED: you no longer own db/migrations.
Your lease token (33) is older than token 34, which has since written to this resource.
This is NOT a transient error. Do not retry, rebase, renumber, or re-apply.
Your plan and your memory of this resource are probably stale, including anything
your context summary says you 'hold'.
Next step: call read_state("db/migrations") and re-plan from what is actually there.
If your goal is already met by the current state, report that and stop.

The second is a rule in the system prompt. The error message only covers the resource that got fenced, and the agent's other beliefs can be just as stale:

Ownership rule: a FENCED error means time passed without you noticing and someone
else changed the world. When you see one, (1) stop the current plan, (2) discard any
belief that you hold a lease or lock, (3) re-read the fenced resource and anything
you were about to write that depends on it, (4) make a new plan from fresh state.
To write again you must acquire a new lease. Never treat FENCED as a merge conflict
or a flaky failure.

We also closed the loopholes the replay exposed. The harness strips 'holds lease' claims out of compaction summaries and re-injects the live lease status from the service. The renumber trick now needs a fresh lease on db/migrations, and that grant comes with a fresh read of state. In the replay, the 'stop if the goal is already met' line did most of the work. Once A re-read the state, it saw that B's 0042 already added the column it wanted, and it stopped.

Lease length is a product decision

With fences in place, the TTL stops being a safety setting. It becomes a trade-off between wasted work and waiting. Set it too short and agents get fenced constantly and redo work. Set it too long and a dead agent blocks everyone. Our mistake was tuning it to the median. Agent task times are heavy-tailed: a 30-second edit and a 25-minute refactor-and-test loop take the same lease, and the tail is exactly where the 429s, slow suites and compactions pile up.

• ▹Never tune the TTL to the median. Pick a short base TTL and renew it.
• ▹Heartbeat at tool-call granularity: renew before and after every tool call, and from the tool runner while a long-running tool's subprocess is alive. Skip the free-standing timer thread. It keeps renewing while the agent loop is stuck in backoff or compaction, so the lease no longer tells you whether the agent is actually making progress.
• ▹Let the lease lapse during model-side pauses. That's fine now, because if the agent comes back and someone else has written, the fence catches it.
• ▹Scope leases to the resource, not the task. Hold db/migrations while you touch migrations, then release it. A 25-minute 'billing feature' lease isn't a lease, it's a reservation.
• ▹Release before asking a human for approval, and re-acquire after. A human-approval wait is a pause with no upper bound.

The Monday checklist

• ▹Ban plain `git push --force` in agent tools. Wrap push and allow only `--force-with-lease=<ref>:<expected-sha>`.
• ▹Have the harness capture the expected SHA at lease grant (`git ls-remote`), and move it only after the agent's own successful push. The agent never supplies it.
• ▹Put a version or hash on every agent write: an `applied_token` and fence row on migrations, an expected sha256 on shared-file writes.
• ▹Issue a monotonic token from the lease service on every grant, persist the counter, and check `token >= highest seen` at the storage.
• ▹Return a distinct FENCED error that says 'not transient, re-read, re-plan.' Never fold it into a generic failure.
• ▹Add the re-plan-on-fence rule to the system prompt, and strip lease claims from compaction summaries.
• ▹Send heartbeats from the tool loop and tool runner, not a background timer, and scope leases to resources, not tasks.

Before you blame the model

Agent A wasn't buggy. It was paused, and it woke up holding a belief that had been true nine minutes earlier. Any worker that can pause will do the same, whether it's a JVM, a Python job or an LLM. The difference is that the LLM will argue for its belief and resolve conflicts in its favor.

Next time an agent 'goes rogue' in a shared repo, pull the timeline before you touch the prompt. Find the silent gap. Then ask whether your write path ever checked that the agent was still the owner.