A randomized work-stealing algorithm for scheduling fully strict multithreaded computation on MIMD computers is proposed. A formula bounding the algorithm’s expected execution time on a fixed number of processors is given and rigorously proven. Under the stated assumptions and for this type of computation, this first provably good work-stealing algorithm performs better than all known work-sharing algorithms.

The authors begin with a discussion of a simple scheduling algorithm (a “busy-leaves” algorithm), which is not really practical because it is centralized, but which clearly shows important characteristics of the general algorithm. The subsequent part of the paper presents the main algorithm itself. To analyze it, the authors introduce the atomic access model and prove important properties that hold for their computational model. The use of these results allows the authors to analyze the time, communication overhead, and space required by the algorithm.

The computational model, assumptions, and type of computation are very general and realistic, making the approach useful for many existing and potential applications.

In this well-written paper, the authors have succeeded in delivering their results in an attractive and convincing fashion. I have only one concern: the last part of the paper, which discusses the applications of the Cilk language, whose runtime incorporates the algorithm, looks too much like an advertisement. It would have been more appropriate to include technical information there.