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.
For offline balls-into-bins problem, using maximum flow computations it was shown that the maximum load of a bin w.h.p. is @math . @cite_24 showed that for @math balls, where @math is a sufficiently large constant, a perfect distribution of the balls was possible w.h.p. However, no such similar result is found in the literature for the online sequential case for constant @math choice.
@cite_24
1577307925 2949649421 2071546224 1996492982
We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly selected bins. The aim is to distribute the balls as evenly as possible among the bins. Previously, it was known that a simple process that places the balls one by one in the least loaded bin can achieve a maximum load of m n + Θ(loglogn) with high probability. Furthermore, it was known that it is possible to achieve (with high probability) a maximum load of at most ⌈m n ⌉ + 1 using maximum flow computations. 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. 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...