Allocating weighted jobs in parallel
Petra Berenbrink, Friedhelm Meyer auf der Heide, Klaus M. Schröder · 1997
It is well known that after placing m n balls independently and uniformly at random (i.u.r.) into n bins, the fullest bin contains \\Theta(log n= log log n+ m n ) balls, with high probability. It is also known (see [Ste96]) that a maximum load of O \\Gamma m n \\Delta can be obtained for all m n if a ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann ([Ste96]) shows that r communication rounds suffice to guarantee a maximum load of maxf r p log n; O \\Gamma m n \\Delta g, with high probability. Adler et al. have shown in [ACMR95] that Stemanns protocol is optimal for constant r. In this paper we extend the above results in two directions: We generalize the lower bound to arbitrary r log log n. This implies that the result of Stemanns protocol is optimal for all r. Our main result is a generalization of Stemanns upper bound to weighted jobs: Let W A (W M ) denote the average (maximum) weight of the balls. Further let \\Delta = W A =W M . Note that...