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.
In the parallel setting, @cite_12 showed that a constant bound on the gap is possible with @math communication rounds. Adler et.al. @cite_22 consider parallel balls and bins with multiple rounds. They present analysis for @math bound on the gap (for @math ) using @math rounds of communication.
@cite_22 @cite_12
2069817080 2951571245
It is well known that after placing n balls independently and uniformly at Ž . random into n bins, the fullest bin holds Q log nrlog log n balls with high probability. More recently, analyzed the following process: randomly choose d bins for each ball, and then place the balls, one by one, into the least full bin from its d choices. They show that after all n balls have been placed, the fullest bin contains only Ž . log log nrlog dqQ 1 balls with high probability. We explore extensions of this result to parallel and distributed settings. Our results focus on the tradeoff between the amount of Correspondence to: M. Mitzenmacher * A preliminary version of this work appeared in the Proceedings of the Twenty-Se enth Annual ACM Symposium on the Theory of Computing, May 1995, pp. 238]247. † This work was primarily done while attending U.C. Berkeley, and was supported by a Schlumberger Foundation graduate fellowship. ‡ This work was primarily done while attending U.C. Berkeley, and was supported in part by ARPA Ž . under contract DABT63-92-C-0026, by NSF numbers CCR-9210260 and CDA-8722788 , and by Lawrence Livermore National Laboratory. § This work was primarily done while attending U.C. Berkeley, and was supported by the Office of Naval Research and by NSF grant CCR-9505448. ¶ Supported by a fellowship from U.C. Berkeley. Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r020159-30 We explore the fundamental limits of distributed balls-into-bins algorithms. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). For each assumption of the lower bound, we provide an algorithm violating it, in turn achieving a constant maximum bin load in constant time. As an application, we consider the following problem. Given a fully connected graph of n nodes, where each node needs to send and receive up to n messages, and in each round each node may send one message over each link, deliver all messages as quickly as possible to their destinations. We give a simple and robust algorithm of time complexity O(log* n) for this task and provide a generalization to the case where all nodes initially hold arbitrary sets of messages. A less practical algorithm terminates within asymptotically optimal O(1) rounds. All these bounds hold with high probability.