Balls into non-uniform bins

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

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
• Electronic ISSN: 1096-0848
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 74
• Issue: 2
• Pages: 2065-2076
• DOI: https://doi.org/10.1016/j.jpdc.2013.10.008
• Public URL: https://durham-repository.worktribe.com/output/1393782