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
1996492982 2949649421 2071546224 1968904909
We investigate balls-into-bins processes allocating m balls into n bins based on the multiple-choice paradigm. In the classical single-choice variant each ball is placed into a bin selected uniformly at random. In a multiple-choice process each ball can be placed into one out of @math randomly selected bins. It is known that in many scenarios having more than one choice for each ball can improve the load balance significantly. Formal analyses of this phenomenon prior to this work considered mostly the lightly loaded case, that is, when @math . In this paper we present the first tight analysis in the heavily loaded case, that is, when @math rather than @math .The best previously known results for the multiple-choice processes in the heavily loaded case were obtained using majorization by the single-choice process. This yields an upper bound of the maximum load of bins of @math O @math with high probability. We show, however, that the multiple-choice... In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for @math balls and @math bins, if the graph is almost regular with degree @math , where @math is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is @math . For general @math -regular graphs, we show that the maximum load is @math and also provide an almost matching lower bound of @math . V "o cking [Voc99] showed that the maximum bin size with @math choice load balancing can be further improved to @math by breaking ties to the left. This requires @math random bin choices. We show that such bounds can be achieved by making only two random accesses and querying @math contiguous bins in each access. By grouping a sequence of @math bins into @math groups, each of @math consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is @math with high probability. In the standard balls-and-bins model of balanced allocations, m balls are placed sequentially into n bins. Each ball chooses d uniform-random bins and is placed in the least loaded bin. It is well known that when d = logΘ(1) n, after placing m = n balls, the maximum load (number of balls in a bin) is Θ(1) w.h.p. In this paper we show that as long as d = Ω(log n), independent random choices are not necessary to achieve a constant load balance: these choices may be structured in a very general way. Specifically, we allow each ball i to have an associated random set of bins Bi. We require that [Bi] = Ω(log n) and that bins are included in Bi with approximately the same probability; but the distributions of the Bis are otherwise arbitrary, so that there may be correlations in the choice of bins. We show that this model captures structure important to two applications, nearby server selection and load balance in distributed hash tables. 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.