How to avoid herd: A novel stochastic algorithm in grid scheduling

Grid technologies promise to bring the grid users high performance. Consequently, scheduling is being becoming a crucial problem. Herd behavior is a common phenomenon, which causes the severe performance decrease in grid environment with respect to bad scheduling behaviors. In this paper, on the basis of the theoretical results of the homogeneous balls and bins model, we proposed a novel stochastic algorithm to avoid herd behavior. Our experiments address that the multi-choice strategy, combined with the advantages of DHT, can decrease herd behavior in large-scale sharing environment, at the same time, providing better schedule performance while burdening much less scheduling overhead than greedy algorithms. In the case of 1000 resources, the simulations show that, for the heavy load(i.e. system utilization rate 0.5), the multi-choice algorithm reduces the number of incurred herds by a factor of 36, the average job waiting time by a factor of 8, and the average job turn-around time by 12% compared to the greedy algorithms.