Abstract
We consider the problem of resource allocation in a parallel environment where new incoming resources are arriving online in groups or batches.
We study this scenario in an abstract framework of allocating balls into bins. We revisit the allocation algorithm \(\mbox{\sc Greedy} [2]\) due to Azar, Broder, Karlin, and Upfal (SIAM J. Comput. 1999), in which, for sequentially arriving balls, each ball chooses two bins at random, and gets placed into one of those two bins with minimum load. The maximum load of any bin after the last ball is allocated by \(\mbox{\sc Greedy} [2]\) is well understood, as is, indeed, the entire load distribution, for a wide range of settings. The main goal of our paper is to study balls and bins allocation processes in a parallel environment with the balls arriving in batches. In our model, m balls arrive in batches of size n each (with n being also equal to the number of bins), and the balls in each batch are to be distributed among the bins simultaneously. In this setting, we consider an algorithm that uses \(\mbox{\sc Greedy} [2]\) for all balls within a given batch, the answers to those balls’ load queries are with respect to the bin loads at the end of the previous batch, and do not in any way depend on decisions made by other balls from the same batch.
Our main contribution is a tight analysis of the new process allocating balls in batches: we show that after the allocation of any number of batches, the gap between maximum and minimum load is O(logn) with high probability, and is therefore independent of the number of batches used.
Research supported by the Centre for Discrete Mathematics and its Applications (DIMAP), and by EPSRC awards EP/D063191/1, EP/G069034/1, EP/F043333/1 and EP/F043333/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adler, M., Berenbrink, P., Schröder, K.: Analyzing an Infinite Parallel Job Allocation Process. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 417–428. Springer, Heidelberg (1998)
Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), USA, pp. 238–247 (1995)
Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM Journal on Computing 29(1), 180–200 (1999)
Berenbrink, P., Czumaj, A., Steger, A., Vöcking, B.: Balanced allocations: The heavily loaded case. SIAM Journal on Computing 35(6), 1350–1385 (2006)
Czumaj, A., Stemann, V.: Randomized allocation processes. In: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 194–203 (1997)
Dahlin, M.: Interpreting stale load information. IEEE Transactions on Parallel and Distributed Systems 11(10), 1033–1047 (2000)
Eager, D.L., Lazowska, E.D., Zahorjan, J.: Adaptive load sharing in homogeneous distributed systems. IEEE Transactions on Software Engineering 12, 662–675 (1986)
Johnson, N.L., Kotz, S.: Urn Models and Their Application: An Approach to Modern Discrete Probability Theory. John Wiley & Sons, New York (1977)
Karp, R.M., Luby, M., Meyer auf der Heide, F.: Efficient PRAM simulation on a distributed memory machine. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pp. 318–326 (1992)
Kolchin, V.F., Sevast’yanov, B.A., Chistyakov, V.P.: Random Allocations. V. H. Winston and Sons, Washington, D.C. (1978)
Lenzen, C., Wattenhofer, R.: Tight bounds for parallel randomized load balancing. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 11–20 (2011)
Mitzenmacher, M.: How useful is old information? IEEE Transactions on Parallel and Distributed Systems 11(1), 6–20 (2000)
Stemann, V.: Parallel balanced allocations. In: Proceedings of the 8th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 261–269 (1996)
Talwar, K., Wieder, U.: Balanced allocations: The weighted case. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 256–265 (2007)
Vöcking, B.: How asymmetry helps load balancing. Journal of the ACM 50(4), 568–589 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berenbrink, P., Czumaj, A., Englert, M., Friedetzky, T., Nagel, L. (2012). Multiple-Choice Balanced Allocation in (Almost) Parallel. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2012 2012. Lecture Notes in Computer Science, vol 7408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32512-0_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-32512-0_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32511-3
Online ISBN: 978-3-642-32512-0
eBook Packages: Computer ScienceComputer Science (R0)