Balls and bins with structure: Balanced allocations on hypergraphs

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 B _i. We require that |B _i| = Ω(log n) and that bins are included in B _i with approximately the same probability; but the distributions of the B _is 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.