Greed is not enough: adaptive load sharing in large heterogeneous systems

The authors consider the problem of job placement in load-sharing algorithms for large heterogeneous distributed computing environments. They present simulation results using a simple model; the results indicate that, under heavy loads, the usual policy of placing jobs where they will incur the shortest expected delay leads to inefficient system performance. Thus, purely greedy policies are not sufficient; the authors identify a simple threshold algorithm that does significantly better. The authors introduce a novel adaptive algorithm having a performance much closer to optimal.