The natural work-stealing algorithm is stable

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed, but arbitrary, distribution D over generator-allocation functions. During each time step of our process, a generator-allocation function h is chosen from D, and the generators are allocated to the processors according to h. Each generator may then generate a unit-time task, which it inserts into the queue of its host processor. It generates such a task independently with probability.. After the new tasks are generated, each processor removes one task from its queue and services it. For many choices of D, the work-generation model allows the load to become arbitrarily imbalanced, even when. lambda < 1. For example, D could be the point distribution containing a single function h which allocates all of the generators to just one processor. For this choice of D, the chosen processor receives around lambda n units of work at each step and services one. The natural work-stealing algorithm that we analyze is widely used in practical applications and works as follows. During each time step, each empty processor ( with no work to do) sends a request to a randomly selected other processor. Any nonempty processor having received at least one such request in turn decides ( again randomly) in favor of one of the requests. The number of tasks which are transferred from the nonempty processor to the empty one is determined by the so-called work-stealing function f. In particular, if a processor that accepts a request has l tasks stored in its queue, then f(l) tasks are transferred to the currently empty one. A popular work-stealing function is f(l) = [l/2], which transfers (roughly) half of the tasks. We analyze the long-term behavior of the system as a function of. and f. We show that the system is stable for any constant generation rate. < 1 and for a wide class of functions f. Most intuitively sensible functions are included in this class ( for example, every monotonically nondecreasing function f which satisfies 0 less than or equal to f(l) less than or equal to l/2 and f(l) = omega(1) as a function of l is included). Furthermore, we give upper bounds on the average system load ( as a function of f and n). Our proof techniques combine Lyapunov function arguments with domination arguments, which are needed to cope with dependency.