Skip to main content

Research Repository

Advanced Search

Balls into non-uniform bins

Berenbrink, Petra; Brinkmann, André; Friedetzky, Tom; Nagel, Lars

Balls into non-uniform bins Thumbnail


Authors

Petra Berenbrink

André Brinkmann

Lars Nagel



Abstract

Balls-into-bins games for uniform bins are widely used to model randomised load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks. In this paper we consider scenarios in which non-uniform selection probabilities help to balance the load among the bins. While previous evaluations try to find strategies for identical bins, we investigate heterogeneous bins where the “capacities” of the bins might differ significantly. We look at the allocation of m balls into n bins of total capacity C where each ball has d random bin choices. For such heterogeneous environments we show that the maximum load remains bounded by lnln(n)/ln(d)+O(1)w.h.p. if the number of balls m equals the total capacity C. Further analytical and simulative results show better bounds and values for the maximum loads in special cases.

Citation

Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2014). Balls into non-uniform bins. Journal of Parallel and Distributed Computing, 74(2), 2065-2076. https://doi.org/10.1016/j.jpdc.2013.10.008

Journal Article Type Article
Acceptance Date Oct 31, 2013
Publication Date Feb 1, 2014
Deposit Date Dec 16, 2015
Publicly Available Date Mar 14, 2016
Journal Journal of Parallel and Distributed Computing
Print ISSN 0743-7315
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 74
Issue 2
Pages 2065-2076
DOI https://doi.org/10.1016/j.jpdc.2013.10.008

Files





You might also like



Downloadable Citations