Petra Berenbrink
Self-Stabilizing Balls and Bins in Batches
Berenbrink, Petra; Friedetzky, Tom; Kling, Peter; Mallmann-Trenn, Frederik; Nagel, Lars; Wastell, Chris
Authors
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
Peter Kling
Frederik Mallmann-Trenn
Lars Nagel
Chris Wastell
Abstract
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where m balls (tasks) are to be distributed among n bins (servers). In a seminal work, Azar et al. (SIAM J Comput 29(1):180–200, 1999. https://doi.org/10.1137/S0097539795288490) proposed the sequential strategy GREEDY[d] for n=m . Each ball queries the load of d random bins and is allocated to a least loaded of them. Azar et al. (1999) showed that d=2 yields an exponential improvement compared to d=1 . Berenbrink et al. (SIAM J Comput 35(6):1350–1385, 2006. https://doi.org/10.1137/S009753970444435X) extended this to m≫n , showing that for d=2 the maximal load difference is independent of m (in contrast to the d=1 case). We propose a new variant of an infinite balls-into-bins process. In each round an expected number of λn new balls arrive and are distributed (in parallel) to the bins. Subsequently, each non-empty bin deletes one of its balls. This setting models a set of servers processing incoming requests, where clients can query a server’s current load but receive no information about parallel requests. We study the GREEDY[d] distribution scheme in this setting and show a strong self-stabilizing property: for any arrival rate λ=λ(n)<1 , the system load is time-invariant. Moreover, for any (even super-exponential) round t, the maximum system load is (w.h.p.) Open image in new window for d=1 and Open image in new window for d=2 . In particular, GREEDY[2] has an exponentially smaller system load for high arrival rates.
Citation
Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2018). Self-Stabilizing Balls and Bins in Batches. Algorithmica, 80(12), 3673-3703. https://doi.org/10.1007/s00453-018-0411-z
Journal Article Type | Article |
---|---|
Acceptance Date | Jan 10, 2018 |
Online Publication Date | Feb 15, 2018 |
Publication Date | Dec 1, 2018 |
Deposit Date | Mar 16, 2018 |
Publicly Available Date | Feb 15, 2019 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 80 |
Issue | 12 |
Pages | 3673-3703 |
DOI | https://doi.org/10.1007/s00453-018-0411-z |
Related Public URLs | https://arxiv.org/abs/1603.02188ll |
Files
Accepted Journal Article
(684 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/s00453-018-0411-z.
You might also like
Infinite Balanced Allocation via Finite Capacities
(2021)
Conference Proceeding
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)
Conference Proceeding
Threshold Load Balancing With Weighted Tasks
(2017)
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