Perfectly Balanced AllocationWith Estimated Average Using Approximately Constant Retries

Balanced allocation of online balls-and-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 with different settings, such as parallel allocations [1], multi-dimensional allocations [5], weighted balls [4] etc. For sequential multi-choice allocation where m balls are thrown into n bins with each ball choosing d (constant) bins independently uniformly at random, the maximum load of a bin is O(log log n)+m=n with high probability [3]. This offers the current best known allocation scheme. However, for d = (log n), the gap obtained is of O(1) [9]. A similar constant gap bound has been established for parallel allocations with O(log n) communication rounds [12].
In this paper we propose a novel multi-choice allocation algorithm, Improved D-choice with Estimated Average (IDEA) achieving a constant gap with high probability for the sequential single-dimensional online allocation problem with constant d. We achieve a maximum load of dm=ne with high probability for constant d choice scheme with approximately constant number of retries or rounds per ball. We also show that the bound holds even for an arbitrary large number of balls, m >> n. Further, we generalize
this result to the weighted case, where the balls have weights drawn from an arbitrary weight distribution with finite variance. We show that the gap in this case is also independent of the number of balls thrown and is a constant. We also propose that IDEA provides constant gap bound w.h.p. in the multi-dimensional scenario for m = n.

By: Sourav Dutta, Souvik Bhattacherjee, Ankur Narang

Published in: RI11023 in 2011

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

constgap.pdf

Questions about this service can be mailed to reports@us.ibm.com .