---
title: "Scheduling Multithreaded Computations by Work Stealing"
authors:
  - "Robert D. Blumofe"
  - "Charles E. Leiserson"
year: 1999
venue: "JACM"
arxiv: null
doi: "10.1145/324133.324234"
source: "https://doi.org/10.1145/324133.324234"
topics:
  - work-stealing-schedulers
  - scheduling
seed_rank: 200
seed_batch: "systems-prefill-2026-08-13"
reviewed: "2026-08-13"
pool: "systems"
relevance_score: 10
lineage: work-stealing-schedulers
cites:
  - title: "Cilk: An Efficient Multithreaded Runtime System"
    url: "https://doi.org/10.1145/209936.209958"
    year: 1995
    doi: "10.1145/209936.209958"
  - title: "The Implementation of the Cilk-5 Multithreaded Language"
    url: "https://doi.org/10.1145/277650.277725"
    year: 1998
    doi: "10.1145/277650.277725"
  - title: "Thread Scheduling for Multiprogrammed Multiprocessors"
    url: "https://doi.org/10.1145/277651.277678"
    year: 1998
    doi: "10.1145/277651.277678"
  - title: "Dynamic Circular Work-Stealing Deque"
    url: "https://doi.org/10.1145/1073970.1073974"
    year: 2005
    doi: "10.1145/1073970.1073974"
  - title: "A Java Fork/Join Framework"
    url: "https://doi.org/10.1145/337449.337465"
    year: 2000
    doi: "10.1145/337449.337465"
see:
  - "430-cilk-an-efficient-multithreaded-runtime-system"
  - "305-the-implementation-of-the-cilk-5-multithreaded-language"
  - "431-thread-scheduling-for-multiprogrammed-multiprocessors"
  - "291-dynamic-circular-work-stealing-deque"
  - "432-a-java-fork-join-framework"
---

# Scheduling Multithreaded Computations by Work Stealing

## One-sentence takeaway

Blumofe and Leiserson analyze randomized work stealing and prove time, space, and communication bounds that made Cilk-style schedulers the default for irregular parallel job systems.

## Why it matters here

Ano/engine job graphs are multithreaded computations with highly irregular grain. Work stealing — idle workers pull from victims' deques — is the scheduler this paper justifies, not a heuristic pulled from a thread pool.

## Key ideas

- Each worker keeps a double-ended queue of ready tasks; it pushes/pops locally and steals from a random victim when idle.
- Expected execution time is \(T_1/P + O(T_\infty)\), matching the obvious lower bounds up to constants.
- Space and communication bounds follow from the busy-leaves property and the randomized steal policy.
- The model is a strict multithreaded computation (Cilk's dag), not a bag of independent jobs.
- This JACM paper is the theory behind Cilk, later Chase–Lev deques, and Fork/Join-style runtimes.

## Caveats

## Links

- DOI: [10.1145/324133.324234](https://doi.org/10.1145/324133.324234)