Balanced allocations

Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking

2000 · 83 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

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

References

22