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's performance during
the startup phase.