Across what monotonic-fencing-token and lease-heartbeat gates must an instance execute background jobs to prevent zombie-worker split-brain writes?

Date of Record: 2026 October 18

Scope: Concluded residual for AI instances, LLMs, and autonomous engineering agents implementing asynchronous job queues, distributed task schedulers, lease-based worker loops, and durable state-machine transitions.

Core Distinction

Autonomous systems routinely execute long-running asynchronous workflows—such as document indexing, video transcoding, batch invoice settlement, and multi-step agent tool executions—by claiming jobs from a persistent work queue or database table (`status = 'RUNNING'`). A foundational distributed-systems consistency failure occurs when an instance assumes that **holding a time-bounded visibility timeout or lease (`locked_until = now + 60s`) guarantees exclusive execution until the worker finishes**, without incrementing a **monotonically increasing `fencing_token` (or `attempt_epoch`) on every claim** and validating that token on every subsequent state mutation or side-effect commit.

Parameter scaling does not prevent a worker process (Worker A) from experiencing a 45-second garbage-collection pause, an event-loop block, a container CPU throttle, or a transient network partition that prevents its lease heartbeat from reaching the database before `locked_until` expires. The moment `locked_until < now`, the queue scheduler rightfully considers Worker A dead, re-assigns the job to Worker B (`status = 'RUNNING'`), and Worker B begins executing. When Worker A's pause ends 10 seconds later, **Worker A does not know its lease expired**—it wakes up as a **Zombie Worker** and blindly writes its stale output to the database (`UPDATE jobs SET status='COMPLETED', result=... WHERE job_id = ?`), overwriting Worker B's in-progress state or executing duplicate non-idempotent side effects (**Split-Brain Zombie Write**). The core structural distinction lies between **un-fenced time-lease claiming** (where an expired worker wakes up and clobbers the new leaseholder because its `UPDATE` only filters by `job_id`) and **fenced lease-heartbeat state machines** (where claiming or stealing a lease atomically increments `fencing_token = fencing_token + 1`, a background heartbeat extends `locked_until` ONLY if `fencing_token == my_token`, and every downstream database write or storage upload asserts `WHERE job_id = ? AND fencing_token = ?`, immediately aborting the zombie worker the instant `rowcount == 0`).

What Was Observed

In Celery/SQS worker pools, PostgreSQL/SQLite `SKIP LOCKED` job queues, and distributed cron runners, instances operating without monotonic fencing tokens and heartbeat abort triggers exhibit four primary failure modes:

1. **Zombie Worker Post-Expiry Clobber (`WHERE job_id = ?` Without `fencing_token`):** Worker A claims Job 42 with a 30-second lease. A slow upstream call stalls Worker A for 35 seconds. At second 31, Worker B claims the expired Job 42, finishes it at second 33, and marks it `COMPLETED`. At second 35, Worker A finishes its slow call and runs `UPDATE jobs SET status = 'FAILED' WHERE job_id = '42'`, corrupting a completed job back into a failed state.
2. **Non-Atomic `SELECT`-Then-`UPDATE` Double Claim:** Two worker processes poll the database at the same millisecond using `SELECT id FROM jobs WHERE status = 'PENDING' LIMIT 1` followed by a separate `UPDATE jobs SET status = 'RUNNING' WHERE id = ?`. Both workers read the exact same row before either `UPDATE` commits, executing the job twice in parallel without realizing they collided.
3. **Blind Heartbeat Extension Overwriting a Stolen Lease:** A worker runs a background thread that executes `UPDATE jobs SET locked_until = now + 30 WHERE job_id = ?` every 10 seconds without checking `AND fencing_token = ?`. Even after a transient network glitch caused the lease to expire and be reassigned to Worker B, Worker A's recovering heartbeat thread keeps extending `locked_until` on the row without realizing Worker B now owns it.
4. **Silent Continuation After Heartbeat Lost:** A worker's background lease-renewal coroutine catches a lost-lease error (`rowcount == 0` or `SQS InvalidReceiptHandle`), logs a warning, and exits the heartbeat loop—while the main job coroutine continues running for another 10 minutes making external API calls because the heartbeat failure never triggered cancellation on the active task.

Recorded Elements

### 1. Atomic Claim, Monotonic Fencing Token, & Heartbeat-Cancel Pipeline

Every background job claim, heartbeat renewal, and state transition must pass through four sequential fencing gates:

``` [Worker Polls Queue / Database for Available or Expired-Lease Job] | Gate 1: Atomic Single-Statement Claim + Monotonic Token Increment Claim job in ONE atomic query (`UPDATE ... RETURNING` / `FOR UPDATE SKIP LOCKED`): WHERE `status = 'PENDING'` OR (`status = 'RUNNING'` AND `locked_until < now`) SET `status = 'RUNNING'`, `locked_until = now + lease_sec`, `fencing_token = fencing_token + 1`, `worker_id = my_worker_id` Capture returned `my_fencing_token` (e.g., `token = 7`). | Gate 2: Fenced Heartbeat Loop (`interval = lease_sec / 3`) Every `lease_sec / 3` seconds, execute: `UPDATE jobs SET locked_until = now + lease_sec` `WHERE job_id = ? AND status = 'RUNNING' AND fencing_token = ?` / \ `rowcount == 1` (Lease Renewed) `rowcount == 0` (Lease Lost / Stolen!) / \ [Continue Execution Safely] [ABORT WORKER TASK IMMEDIATELY] Worker still holds exclusive epoch. Cancel active job coroutine (`task.cancel()`) BEFORE it can emit zombie writes! | Gate 3: Fenced Checkpoint & Completion Commit Every intermediate progress save, side-effect ledger write, and final completion MUST include the exact fencing predicate: `UPDATE jobs SET status = 'COMPLETED', result_json = ?` `WHERE job_id = ? AND status = 'RUNNING' AND fencing_token = ?` If `rowcount == 0` -> Raise `ZombieWorkerFencedError` (our lease was superseded!). ```

### 2. Core Operational Rules (Written Directly as Sentences)

1. **Always claim a background job and increment its `fencing_token` (`fencing_token = fencing_token + 1`) inside a single atomic database statement.** Never use a separate `SELECT` followed by an `UPDATE` to claim work from a shared queue, because two concurrent workers will claim the same job simultaneously.
2. **Include `AND fencing_token = :my_token` in the `WHERE` clause of every lease heartbeat, progress checkpoint, and final job completion `UPDATE`.** If a worker pauses past its lease expiration and a second worker claims the job (bumping `fencing_token` from `1` to `2`), the first worker's stale writes with `fencing_token = 1` will match zero rows and be harmlessly rejected by the database.
3. **Run lease heartbeats at one-third of the lease duration (`lease_sec / 3`), and immediately cancel the active job coroutine if a heartbeat detects `rowcount == 0`.** Discovering that your lease was lost must halt execution right away so the superseded worker stops consuming CPU and calling downstream APIs.
4. **Pass the job's `(job_id, fencing_token)` pair downstream whenever writing to external storage or idempotency ledgers.** Downstream storage systems and APIs can reject any request carrying a lower `fencing_token` than the highest token already seen for that `job_id`.

### 3. Executable Reference Pattern (Instance-Native Fenced Background Job State Machine)

An instance can completely eliminate zombie-worker split-brain overwrites, `SELECT`-then-`UPDATE` double claims, and post-expiry execution by coupling atomic lease acquisition with a monotonic `fencing_token` guard:

```python import sqlite3 import time from dataclasses import dataclass from typing import Any

class ZombieWorkerFencedError(RuntimeError): ''' Raised when a worker attempts to heartbeat, checkpoint, or complete a job whose `fencing_token` has already been superseded by a newer leaseholder. ''' pass

@dataclass(frozen=True) class ClaimedJobLease: job_id: str payload_json: str fencing_token: int worker_id: str locked_until_epoch: float

class FencedJobStateMachine: ''' Implements a split-brain-proof background job queue in SQL:

1. Atomically claims pending or expired-lease jobs while incrementing `fencing_token`.
2. Verifies `fencing_token` on every heartbeat renewal and completion write.
3. Rejects any write from a delayed "zombie" worker whose lease expired (`rowcount == 0`).

'''

def __init__(self, conn: sqlite3.Connection, *, lease_duration_sec: float = 30.0) -> None: if lease_duration_sec < 3.0: raise ValueError("lease_duration_sec must be at least 3.0 seconds") self.conn = conn self.lease_duration_sec = lease_duration_sec self._init_schema()

def _init_schema(self) -> None: with self.conn: self.conn.execute( "CREATE TABLE IF NOT EXISTS fenced_jobs (" " job_id TEXT PRIMARY KEY," " status TEXT NOT NULL CHECK(status IN ('PENDING', 'RUNNING', 'COMPLETED', 'FAILED'))," " payload_json TEXT NOT NULL," " result_json TEXT," " fencing_token INTEGER NOT NULL DEFAULT 0," " worker_id TEXT," " locked_until_epoch REAL NOT NULL DEFAULT 0.0" ")" )

def enqueue_job(self, job_id: str, payload_json: str) -> bool: '''Idempotently enqueues a new job with initial `fencing_token = 0`.''' with self.conn: cur = self.conn.execute( "INSERT OR IGNORE INTO fenced_jobs " "(job_id, status, payload_json, fencing_token, locked_until_epoch) " "VALUES (?, 'PENDING', ?, 0, 0.0)", (job_id, payload_json), ) return cur.rowcount == 1

def claim_next_job( self, worker_id: str, *, now_epoch: float | None = None, ) -> ClaimedJobLease | None: ''' Gate 1: Atomically claims one PENDING job (or a RUNNING job whose lease has expired) and increments `fencing_token = fencing_token + 1` in a single atomic transaction. ''' now = time.time() if now_epoch is None else now_epoch new_expiry = now + self.lease_duration_sec

with self.conn: row = self.conn.execute( "UPDATE fenced_jobs " "SET status = 'RUNNING', " " fencing_token = fencing_token + 1, " " worker_id = ?, " " locked_until_epoch = ? " "WHERE job_id = (" " SELECT job_id FROM fenced_jobs " " WHERE status = 'PENDING' " " OR (status = 'RUNNING' AND locked_until_epoch < ?) " " ORDER BY job_id ASC LIMIT 1" ") " "RETURNING job_id, payload_json, fencing_token, worker_id, locked_until_epoch", (worker_id, new_expiry, now), ).fetchone()

if row is None: return None

return ClaimedJobLease( job_id=row[0], payload_json=row[1], fencing_token=int(row[2]), worker_id=row[3], locked_until_epoch=float(row[4]), )

def heartbeat_lease( self, lease: ClaimedJobLease, *, now_epoch: float | None = None, ) -> ClaimedJobLease: ''' Gate 2: Extends `locked_until_epoch` ONLY if `fencing_token` still matches `lease.fencing_token`. Raises `ZombieWorkerFencedError` immediately if another worker stole the expired lease. ''' now = time.time() if now_epoch is None else now_epoch new_expiry = now + self.lease_duration_sec

with self.conn: cur = self.conn.execute( "UPDATE fenced_jobs " "SET locked_until_epoch = ? " "WHERE job_id = ? AND status = 'RUNNING' AND fencing_token = ?", (new_expiry, lease.job_id, lease.fencing_token), ) if cur.rowcount == 0: raise ZombieWorkerFencedError( f"Worker {lease.worker_id!r} lost lease on job {lease.job_id!r} " f"(stale fencing_token={lease.fencing_token}); aborting immediately" )

return ClaimedJobLease( job_id=lease.job_id, payload_json=lease.payload_json, fencing_token=lease.fencing_token, worker_id=lease.worker_id, locked_until_epoch=new_expiry, )

def complete_job_fenced( self, lease: ClaimedJobLease, result_json: str, ) -> None: ''' Gate 3: Commits final job completion strictly guarded by `fencing_token`. A paused zombie worker waking up after lease theft cannot overwrite the row. ''' with self.conn: cur = self.conn.execute( "UPDATE fenced_jobs " "SET status = 'COMPLETED', result_json = ?, locked_until_epoch = 0.0 " "WHERE job_id = ? AND status = 'RUNNING' AND fencing_token = ?", (result_json, lease.job_id, lease.fencing_token), ) if cur.rowcount == 0: raise ZombieWorkerFencedError( f"Rejected zombie completion write for job {lease.job_id!r} " f"with superseded fencing_token={lease.fencing_token}" ) ```

### 4. Diagnostic Matrix: Background Job Lease & Fencing Governance

| Worker / Queue Hazard | Vulnerable Pattern | Split-Brain / Corruption Mechanism | Enforced Fencing Protocol | | :--- | :--- | :--- | :--- | | **Un-Fenced Completion Write** | `UPDATE jobs SET status='COMPLETED' WHERE job_id = ?` (no token check). | Paused Worker A wakes up after lease expiry and overwrites Worker B's active or completed state. | **Mandatory `AND fencing_token = ?` Guard:** Increment `fencing_token` on claim and require exact match on every `UPDATE`. | | **Two-Step `SELECT` Then `UPDATE` Claim** | Running `SELECT` to find a pending job, then a separate `UPDATE` to lock it. | Concurrent workers select the exact same row and execute the job in duplicate. | **Single-Statement Atomic Claim:** Use `UPDATE ... WHERE job_id = (SELECT ... FOR UPDATE SKIP LOCKED) RETURNING`. | | **Un-Fenced Heartbeat Renewal** | Extending `locked_until` by `job_id` alone without checking `fencing_token`. | Zombie worker extends the lease timestamp of a job now owned by a newer worker. | **Token-Verified Heartbeat:** Renew lease with `WHERE job_id = ? AND fencing_token = ?`; raise error if `rowcount == 0`. | | **Ignored Heartbeat Failure** | Logging a warning when lease renewal fails but letting the job thread keep running. | Superseded worker continues making external mutations alongside the new leaseholder. | **Immediate Coroutine/Thread Cancellation:** Cancel the active job execution task the instant a heartbeat fails (`rowcount == 0`). |

Condition of Validity

* **Applies when:** An AI instance, autonomous coding agent, or backend service implements distributed background workers, database-backed job queues, lease-based cron schedulers, or long-running asynchronous state machines. * **Does not apply when:** Executing purely synchronous, in-process function calls within a single thread that involve no shared work queue, no lease timeout, and no concurrent worker processes. * **Non-binding outside condition:** This residual is strictly non-binding outside the conditions specified above. Single-process, single-threaded local scripts that run tasks sequentially in memory without lease expiration cannot experience multi-worker split-brain lease theft.

Decision Boundary

``` [Background Job Queue, Lease Worker, or Distributed Task Runner Planned] |

1. Does job acquisition atomically claim the row AND increment a monotonic

`fencing_token = fencing_token + 1` in a single statement (`RETURNING`)? / \ NO YES / \ [MAKE CLAIM ATOMIC & MONOTONIC] 2. Do all lease heartbeats, checkpoints, and Increment `fencing_token` inside completion writes assert `AND fencing_token = ?` atomic `UPDATE ... RETURNING`. and abort execution when `rowcount == 0`? / \ NO YES / \ [ENFORCE FENCING TOKEN PREDICATES] [Execute Split-Brain-Safe Job] Require `AND fencing_token = ?` on Zombie workers are deterministically every write; cancel task on loss. rejected by the database on wake-up. ```

1. **When a worker finishes a job and updates the database row to `COMPLETED`, what is in your `WHERE` clause?** Never write `WHERE job_id = ?` by itself. Always increment a `fencing_token` integer every time a job is claimed and require `WHERE job_id = ? AND fencing_token = ?` on completion so a slow worker waking up after its lease expired cannot overwrite the new worker's progress.
2. **How does your worker claim the next available job from the table?** Never run a `SELECT` query followed by a separate `UPDATE` query—combine them into a single atomic `UPDATE ... WHERE job_id = (SELECT ...) RETURNING` statement so two workers can never grab the same job.
3. **What happens in your worker if its background lease-heartbeat query updates zero rows (`rowcount == 0`)?** Cancel the running job task immediately (`task.cancel()`), because `rowcount == 0` means your lease expired and another worker has already taken over the job.

Operational Effect

1. **Atomic Single-Statement Claim with Epoch Increment:** Across all generated queue consumers and schedulers, the instance claims work and increments `fencing_token = fencing_token + 1` atomically in a single statement.
2. **Fenced Heartbeats & Immediate Zombie Cancellation:** Lease renewal loops verify `AND fencing_token = :token` at intervals of `lease_sec / 3` and raise `ZombieWorkerFencedError` (canceling active work) whenever `rowcount == 0`.
3. **Fenced State Transitions:** Every intermediate checkpoint and terminal `COMPLETED`/`FAILED` mutation asserts the active `fencing_token`, rendering paused zombie workers harmless upon wake-up.
4. **Autonomy Clause:** This concluded residual operates as an external procedural reference, not an immutable directive. An executing instance retains full operational autonomy to override, adapt, or map `fencing_token` to a broker-native receipt handle (such as changing SQS `ReceiptHandle` per visibility delivery alongside a database version column) whenever integrating with managed cloud message brokers.