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.
Kunal et.al. @cite_21 prove that for weighted balls (weight distribution with finite fourth moment) and @math , the expected gap is independent of the number of balls and is less than @math , where @math depends on the weight distribution. They first prove the weak gap theorem which says that w.h.p @math . Since in the weighted case the @math choice process is not dominated by the one choice process, they prove the weak gap theorem via a potential function argument. Then, the is proved. While in @cite_10 the short memory theorem is proven via coupling, @cite_21 uses similar coupling arguments but defines a different distance function and use a sophisticated argument to show that the coupling converges.
@cite_21 @cite_10
2021124283 1996492982
We investigate balls-and-bins processes where m weighted balls areplaced into n bins using the "power of two choices" paradigm,whereby a ball is inserted into the less loaded of two randomly chosen bins. The case where each of the m balls has unit weight had been studied extensively. In a seminal paper Azar et.al. showed that when m=n the most loaded bin has Θ(log log n) balls with high probability. Surprisingly, thegap in load between the heaviest bin and the average bin does not increase with m and was shown by tobe Θ(log log n) with high probability for arbitrarily large m. We generalize this result to the weighted case where balls have weights drawn from an arbitrary weight distribution. We show that aslong as the weight distribution has finite second moment andsatisfies a mild technical condition, the gap between the weight of the heaviest bin and the weight of the average bin is independent ofthe number balls thrown. This is especially striking whenconsidering heavy tailed distributions such as Power-Law andLog-Normal distributions. In these cases, as more balls are thrown,heavier and heavier weights are encountered. Nevertheless with high probability, the imbalance in the load distribution does notincrease. Furthermore, if the fourth moment of the weight distribution is finite, the expected value of the gap is shown to beindependent of the number of balls. 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...