Title :
An improved algorithm of two choices in randomized dynamic load-balancing
Author :
Wang, Yibing ; Hyatt, Robert
Author_Institution :
Dept. of Comput. & Inf. Sci., Alabama Univ., Birmingham, AL, USA
Abstract :
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.
Keywords :
parallel algorithms; randomised algorithms; resource allocation; workstation clusters; algorithm of two choices; convergence; network of workstations; new task arrival; parallel algorithm; randomized dynamic load-balancing; servers; sliding-window technique; Analytical models; Clustering algorithms; Computer networks; Convergence; Exponential distribution; Load management; Network servers; Partitioning algorithms; Runtime; Workstations;
Conference_Titel :
Algorithms and Architectures for Parallel Processing, 2002. Proceedings. Fifth International Conference on
Conference_Location :
Beijing, China
Print_ISBN :
0-7695-1512-6
DOI :
10.1109/ICAPP.2002.1173616