Analysis of random polling dynamic load balancing

Dynamic load balancing is crucial for the performance of many parallel algorithms. Random Polling, a simple randomized algorithm,has proved to be very efficient in practice for applications like parallel depth first search. This paper derives tight bounds for the scalability of Random Polling which are for the first time able to explain its superior performance analytically. In some cases, Random Polling even turns out to be optimal. The analysis is based on a fairly general model of the application and the parallel machine. Some of the proof-techniques used might also turn out be useful for the analysis of other parallel algorithms. Finally, a simple initialization scheme is presented which vastly improves the algorithm\u27s performance during the startup phase