Balls-into-bins with nearly optimal load distribution

Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, Alexandre Stauffer

Research output: Contribution to conferencePaper

17 Citations (Scopus)
79 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

Bins

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

Balls-into-bins with nearly optimal load distribution. / Berenbrink, Petra; Khodamoradi, Kamyar; Sauerwald, Thomas; Stauffer, Alexandre.

2013. 326-335 Paper presented at SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures, Montreal, Quebec, Canada.

Research output: Contribution to conferencePaper

Berenbrink, P, Khodamoradi, K, Sauerwald, T & Stauffer, A 2013, 'Balls-into-bins with nearly optimal load distribution' Paper presented at SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures, Montreal, Quebec, Canada, 23/07/13 - 25/07/13, pp. 326-335. https://doi.org/10.1145/2486159.2486191
Berenbrink P, Khodamoradi K, Sauerwald T, Stauffer A. Balls-into-bins with nearly optimal load distribution. 2013. Paper presented at SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures, Montreal, Quebec, Canada. https://doi.org/10.1145/2486159.2486191
Berenbrink, Petra ; Khodamoradi, Kamyar ; Sauerwald, Thomas ; Stauffer, Alexandre. / Balls-into-bins with nearly optimal load distribution. Paper presented at SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures, Montreal, Quebec, Canada.10 p.
@conference{bec73669747f478499f5cbec656f3fbe,
title = "Balls-into-bins with nearly optimal load distribution",
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.",
author = "Petra Berenbrink and Kamyar Khodamoradi and Thomas Sauerwald and Alexandre Stauffer",
year = "2013",
doi = "10.1145/2486159.2486191",
language = "English",
pages = "326--335",
note = "SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures ; Conference date: 23-07-2013 Through 25-07-2013",

}

TY - CONF

T1 - Balls-into-bins with nearly optimal load distribution

AU - Berenbrink, Petra

AU - Khodamoradi, Kamyar

AU - Sauerwald, Thomas

AU - Stauffer, Alexandre

PY - 2013

Y1 - 2013

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

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

UR - http://dx.doi.org/10.1145/2486159.2486191

U2 - 10.1145/2486159.2486191

DO - 10.1145/2486159.2486191

M3 - Paper

SP - 326

EP - 335

ER -