Balanced allocation of online balls-into-bins has long been an active area of research for efficient load balancing and hashing applications.There exists a large number of results in this domain for different settings, such as parallel allocations parallel , multi-dimensional allocations multi , weighted balls weight etc. For sequential multi-choice allocation, where @math balls are thrown into @math bins with each ball choosing @math (constant) bins independently uniformly at random, the maximum load of a bin is @math with high probability heavily_load . This offers the current best known allocation scheme. However, for @math , the gap reduces to @math soda08 .A similar constant gap bound has been established for parallel allocations with @math communication rounds lenzen . In this paper we propose a novel multi-choice allocation algorithm, ( @math ) achieving a constant gap with a high probability for the sequential single-dimensional online allocation problem with constant @math . We achieve a maximum load of @math with high probability for constant @math choice scheme with constant number of retries or rounds per ball. We also show that the bound holds even for an arbitrary large number of balls, @math . Further, we generalize this result to (i) the weighted case, where balls have weights drawn from an arbitrary weight distribution with finite variance, (ii) multi-dimensional setting, where balls have @math dimensions with @math randomly and uniformly chosen filled dimension for @math , and (iii) the parallel case, where @math balls arrive and are placed parallely in the bins. We show that the gap in these case is also a constant w.h.p. (independent of @math ) for constant value of @math with expected constant number of retries per ball.
Mitzenmacher et. al. in @cite_11 addresses both the single choice and d-choice paradigm for multidimensional balls and bins under the assumption that the balls are uniform D-dimensional (0, 1) vectors, where each ball has exactly @math populated dimensions. They show that the gap for multidimensional balls and bins, using the two-choice process, is bounded by O(log log(nD)). We provide a better bound of @math w.h.p. for @math case.
@cite_11
2018079147
We consider a multidimensional variant of the balls-and-bins problem, where balls correspond to random D-dimensional 0-1 vectors. This variant is motivated by a problem in load balancing documents for distributed search engines. We demonstrate the utility of the power of two choices in this domain.