Abstract
We deal with the well studied allocation problem of assigning n balls to n bins so that the maximum number of balls assigned to the same bin is minimized. We focus on randomized, constant-round, distributed, asynchronous algorithms for this problem.
Adler et al. [1] presented lower bounds and upper bounds for this problem. A similar lower bound appears in Berenbrink et al. [2]. The lower bound is based on a topological assumption. Our first contribution is the observation that the topological assumption does not hold for two algorithms presented by Adler et al. [1]. We amend this situation by presenting direct proofs of the lower bound for these two algorithms.
We present an algorithm in which a ball that was not allocated in the first round retries with a new choice in the second round. We present tight bounds on the maximum load obtained by our algorithm. The analysis is based on analyzing the expectation and transforming it to a bound with high probability using martingale tail inequalities.
Finally, we present a 3-round heuristic with a single synchronization point. We conducted experiments that demonstrate its advantage over parallel algorithms for 106 ≤ n ≤ 108 balls and bins. In fact, the obtained maximum load meets the best results for sequential algorithms.
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., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.E.: Parallel randomized load balancing. Random Struct. Algorithms 13(2), 159–188 (1998)
Berenbrink, P., auf der Heide, F.M., Schröder, K.: Allocating Weighted Jobs in Parallel. Theory of Computing Systems 32(3), 281–300 (1999)
Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM journal on computing 29(1), 180–200 (2000)
Stemann, V.: Parallel balanced allocations. In: Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, pp. 261–269. ACM, New York (1996)
Czumaj, A., auf der Heide, F., Stemann, V.: Contention Resolution in Hashing Based Shared Memory Simulations. SIAM Journal On Computing 29(5), 1703–1739 (2000)
Voecking, B.: How Asymmetry Helps Load Balancing. Journal of the ACM 50(4), 568–589 (2003)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)
Kolchin, V., Sevastyanov, B., Chistyakov, V.: Random Allocations. John Wiley & Sons, Chichester (1978)
Raab, M., Steger, A.: ”Balls into bins” - a simple and tight analysis. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 159–170. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Even, G., Medina, M. (2010). Revisiting Randomized Parallel Load Balancing Algorithms. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-11476-2_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11475-5
Online ISBN: 978-3-642-11476-2
eBook Packages: Computer ScienceComputer Science (R0)