On the efficiency of localized work stealing

This paper investigates a variant of the work‐stealing algorithm that we call the localized work‐stealing algorithm. The intuition behind this variant is that because of locality, processors can benefit from working on their own work. Consequently, when a processor is free, it makes a steal attempt to get back its own work. We call this type of steal a steal‐back. We show that the expected running time of the algorithm is $T_1/P+O(T_{\infty }P)$ , and that under the ‘even distribution of free agents assumption’, the expected running time of the algorithm is $T_1/P+O(T_{\infty }\lg P)$ . In addition, we obtain another running‐time bound based on ratios between the sizes of serial tasks in the computation. If M denotes the maximum ratio between the largest and the smallest serial tasks of a processor after removing a total of $O(P)$ serial tasks across all processors from consideration, then the expected running time of the algorithm is $T_1/P+O(T_{\infty }M)$ .