Petra Berenbrink
Infinite Balanced Allocation via Finite Capacities
Berenbrink, Petra; Friedetzky, Tom; Hahn, Christopher; Hintze, Lukas; Kaaser, Dominik; Kling, Peter; Nagel, Lars
Authors
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
Christopher Hahn
Lukas Hintze
Dominik Kaaser
Peter Kling
Lars Nagel
Abstract
We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are n bins (servers) with a limited capacity (buffer) of size c=c(n)∈N . Given a fixed arrival rate λ=λ(n)∈(0,1) , in every round λn new balls (requests) are generated. Together with possible leftovers from previous rounds, these balls compete to be allocated to the bins. To this end, every ball samples a bin independently and uniformly at random and tries to allocate itself to that bin. Each bin accepts as many balls as possible until its buffer is full, preferring balls of higher age. At the end of the round, every bin deletes the ball it allocated first. We study how the buffer size c affects the performance of this process. For this, we analyze both the number of balls competing each round (including the leftovers from previous rounds) as well as the worst-case waiting time of individual balls. We show that (i) the number of competing balls is at any (even exponentially large) time bounded with high probability by 4⋅c−1⋅ln(1/(1−λ))⋅n+O(c⋅n) and that (ii) the waiting time of a given ball is with high probability at most (4⋅ln(1/(1−λ)))/(c⋅(1−1/e))+loglogn+O(c) . These results indicate a sweet spot for the choice of c around c=Θ(log(1/(1−λ))−−−−−−−−−−−√) . Compared to a related process with infinite capacity [Berenbrink et al., PODC'16], for constant λ the waiting time is reduced from O(logn) to O(loglogn) . Even for large λ≈1−1/n we reduce the waiting time from O(logn) to O(logn−−−−√) .
Citation
Berenbrink, P., Friedetzky, T., Hahn, C., Hintze, L., Kaaser, D., Kling, P., & Nagel, L. (2021). Infinite Balanced Allocation via Finite Capacities. . https://doi.org/10.1109/icdcs51616.2021.00096
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS) |
Start Date | Jul 7, 2021 |
End Date | Jul 10, 2021 |
Acceptance Date | Mar 17, 2021 |
Online Publication Date | Oct 4, 2021 |
Publication Date | 2021 |
Deposit Date | Nov 1, 2021 |
Publicly Available Date | Nov 2, 2021 |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 965-975 |
DOI | https://doi.org/10.1109/icdcs51616.2021.00096 |
Public URL | https://durham-repository.worktribe.com/output/1138750 |
Related Public URLs | https://repository.lboro.ac.uk/articles/conference_contribution/Infinite_balanced_allocation_via_finite_capacities/15062856 |
Files
Accepted Conference Proceeding
(873 Kb)
PDF
Copyright Statement
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
You might also like
Randomized renaming in shared memory systems
(2021)
Journal Article
Time-space trade-offs in population protocols for the majority problem
(2020)
Journal Article
Tight & Simple Load Balancing
(2019)
Presentation / Conference Contribution
A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
(2018)
Presentation / Conference Contribution
Self-Stabilizing Balls and Bins in Batches
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search