TY - GEN

T1 - Balls and bins with structure

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

AU - Godfrey, Philip B

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58449134020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449134020&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449134020

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 511

EP - 517

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -