Balls and bins with structure: Balanced allocations on hypergraphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages511-517
Number of pages7
StatePublished - Dec 1 2008
Externally publishedYes
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Balls and bins with structure: Balanced allocations on hypergraphs'. Together they form a unique fingerprint.

Cite this