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.
The @math -choice scheme @cite_9 proved that if a ball chooses with @math probability the least loaded bin of @math randomly chosen bin, and otherwise i.u.r. a single bin, the @math becomes independent of @math and is given by @math .
@cite_9
1968904909
Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is Θ (√mlog n n), for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to Θ (log log n) independent of m. Consider now the following "(1 + β)-choice" process for some parameter β ∈ (0, 1): each ball goes to a random bin with probability (1 - β) and the lesser loaded of two random bins with probability β. How does the gap for such a process behave? Suppose that the weight of each ball was drawn from a geometric distribution. How is the gap (now defined in terms of weight) affected? In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifically, we show that for the (1 + β)-choice process above, the gap is Θ(log n β), irrespective of m. Moreover the gap stays at Θ(log n β) in the weighted case for a large class of weight distributions. No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm.