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.
|Number of pages||10|
|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||SPAA'13: 25th ACM symposium on Parallelism in Algorithms and Architectures|
|Period||23/07/13 → 25/07/13|
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