|
Abstract : |
x We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes m balls are inserted into n bins. In the classical single-choice variant each ball is placed simply into a randomly selected bin. In a multiple-choice process each ball can be placed into one out of d 2 randomly selected bins. It is well known that having more than one choice for each ball can improve the load balance significantly. In contrast to previous work on multiple-choice processes, we investigate the heavily loaded case, that is, we assume m n rather than m n. The best previously known results for the multiple-choice processes in the heavily loaded case were obtained by majorization from the single-choice process. This yields an upper bound of m=n + O( p m ln n = n). We show, however, that the multiplechoice processes are fundamentally different from the singlechoice variant in that they have "short memory". The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (i.e., at most dm=ne balls in every bin) does not increase with the number of balls as in case of the single-choice process. In particular, we investigate the allocation obtained by two differ-, |
