Los, Dimitrios, Sauerwald, Thomas and Sylvester, John 
ORCID: 0000-0002-6543-2934
(2023)
Balanced Allocations with Heterogeneous Bins: The Power of Memory.
[Preprint]
Abstract
We consider the allocation of $m$ balls (jobs) into $n$ bins (servers). In the standard Two-Choice process, at each step $t=1,2,\ldots,m$ we first sample two bins uniformly at random and place a ball in the least loaded bin. It is well-known that for any $m \geq n$, this results in a gap (difference between the maximum and average load) of $\log_2 \log n + \Theta(1)$ (with high probability). In this work, we consider the Memory process [Mitzenmacher, Prabhakar and Shah 2002] where instead of two choices, we only sample one bin per step but we have access to a cache which can store the location of one bin. Mitzenmacher, Prabhakar and Shah showed that in the lightly loaded case ($m = n$), the Memory process achieves a gap of $\mathcal{O}(\log \log n)$. Extending the setting of Mitzenmacher et al. in two ways, we first allow the number of balls $m$ to be arbitrary, which includes the challenging heavily loaded case where $m \geq n$. Secondly, we follow the heterogeneous bins model of Wieder [Wieder 2007], where the sampling distribution of bins can be biased up to some arbitrary multiplicative constant. Somewhat surprisingly, we prove that even in this setting, the Memory process still achieves an $\mathcal{O}(\log \log n)$ gap bound. This is in stark contrast with the Two-Choice (or any $d$-Choice with $d=\mathcal{O}(1)$) process, where it is known that the gap diverges as $m \rightarrow \infty$ [Wieder 2007]. Further, we show that for any sampling distribution independent of $m$ (but possibly dependent on $n$) the Memory process has a gap that can be bounded independently of $m$. Finally, we prove a tight gap bound of $\mathcal{O}(\log n)$ for Memory in another relaxed setting with heterogeneous (weighted) balls and a cache which can only be maintained for two steps.
| Item Type: | Preprint |
|---|---|
| Additional Information: | 62 Pages, 6 Figures. Appearing at SODA 2023 |
| Uncontrolled Keywords: | cs.DM, cs.DM, cs.DS, math.CO, math.PR, 68W20, 68W27, 68W40, 60C05, G.3; G.2.m; F.2.2 |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 14 Mar 2023 10:34 |
| Last Modified: | 15 Mar 2024 19:49 |
| DOI: | 10.48550/arxiv.2301.09810 |
| Open Access URL: | https://doi.org/10.1137/1.9781611977554.ch169 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3168969 |
Dimensions
Dimensions
