An improved algorithm of two choices in randomized dynamic load-balancing

We study a kind of randomized dynamic load-balancing scheme, which, upon new task arrival, selects some constant d (d /spl ges/ 2) servers out of n servers in an independently and uniformly randomized fashion and places the newly arrived task to the least-loaded one among the d choices. To overcome the weakness of previous results when they are used in real settings, we propose an improved algorithm. We add a sliding-window technique to the original concept of Mitzenmacher´s (1996) two choices (d = 2) in randomized load-balancing. We prove that our algorithm converges to an equilibrium state in a much moderate condition than what was required in previous studies.