The impact of task-length parameters on the performance of the random load-balancing algorithm
Yosi Ben-Asher, Aviad Cohen, Assaf Schuster, Jop F. Sibeyn · 2003
Considers the problem of dynamic load balancing in an n processors parallel system. The authors focus on the algorithm which randomly assigns newly generated tasks to processors for execution. This process is modeled by randomly throwing weighted balls into n holes. For a given program A, the ball weights (task lengths) are chosen according to an unknown probability distribution D(A) with expectation mu , maximum M and minimum m. For any A, D(A) and a constant 0>