Balls-into-bins with nearly optimal load distribution

Petra Berenbrink; Kamyar Khodamoradi; Thomas Sauerwald; Alexandre Stauffer

doi:10.1145/2486159.2486191

Balls-into-bins with nearly optimal load distribution

Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, Alexandre Stauffer

Research output: Contribution to conference › Paper › peer-review

27 Citations (SciVal)

382 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 language	English
Pages	326-335
Number of pages	10
DOIs	https://doi.org/10.1145/2486159.2486191
Publication status	Published - 2013
Event	SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures - Montreal, Quebec, Canada Duration: 23 Jul 2013 → 25 Jul 2013

Conference

Conference	SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures
Country/Territory	Canada
City	Montreal, Quebec
Period	23/07/13 → 25/07/13

Access to Document

10.1145/2486159.2486191

paper
© ACM 2011. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in SPAA '13 Proceedings of the 25th ACM symposium on Parallelism in algorithms and architectures, http://dx.doi.org/10.1145/2486159.2486191
Accepted author manuscript, 430 KB

Cite this

@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

T2 - SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures

Y2 - 23 July 2013 through 25 July 2013

ER -

Balls-into-bins with nearly optimal load distribution

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this