Balls-into-bins with nearly optimal load distribution

Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, Alexandre Stauffer

Research output: Contribution to conferencePaper

20 Citations (Scopus)
150 Downloads (Pure)

Abstract

We consider sequential balls-into-bins processes that randomly allocate m balls into n bins. We analyze two allocation schemes that achieve a close to optimal maximum load of ⌈m/n⌉ + 1 and require only O(m) (expected) allocation time. These parameters should be compared with the classic d-choice-process which achieves a maximum load of m/n + log log n/d + O(1) and requires m • d allocation time.
Original languageEnglish
Pages326-335
Number of pages10
DOIs
Publication statusPublished - 2013
EventSPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures - Montreal, Quebec, Canada
Duration: 23 Jul 201325 Jul 2013

Conference

ConferenceSPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures
CountryCanada
CityMontreal, Quebec
Period23/07/1325/07/13

Fingerprint Dive into the research topics of 'Balls-into-bins with nearly optimal load distribution'. Together they form a unique fingerprint.

  • Cite this

    Berenbrink, P., Khodamoradi, K., Sauerwald, T., & Stauffer, A. (2013). Balls-into-bins with nearly optimal load distribution. 326-335. Paper presented at SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures, Montreal, Quebec, Canada. https://doi.org/10.1145/2486159.2486191