Derandomized Balanced Allocation

In this paper, we study the maximum loads of explicit hash families in the d -choice schemes when allocating sequentially n balls into n bins. We consider the Uniform-Greedy scheme [ABKU99], which provides d independent bins for each ball and places the ball into the bin with the least load, and its non-uniform variant — the Always-Go-Left scheme introduced by Vöcking [Vöc03]. We construct a hash family with O (log n log log n ) random bits based on the previous work of Celis et al. [CRSW13] and show the following results. 1. With high probability, this hash family has a maximum load of in the Uniform-Greedy scheme. 2. With high probability, it has a maximum load of in the Always-Go-Left scheme for a constant ϕ d > 1. 61. The maximum loads of our hash family match the maximum loads of a perfectly random hash function [ABKU99, Vöc03] in the Uniform-Greedy and Always-Go-Left scheme separately, up to the low order term of constants. Previously, the best known hash families matching the same maximum loads of a perfectly random hash function in d -choice schemes were O (log n )-wise independent functions [Vöc03], which needs Θ(log 2 n ) random bits.

Authors

• Xue Chen 0001

Keywords

No keywords are indexed for this paper.