Balanced Allocations with Heterogeneous Bins: The Power of Memory

Los, Dimitrios, Sauerwald, Thomas and Sylvester, John ORCID: 0000-0002-6543-2934
(2023) Balanced Allocations with Heterogeneous Bins: The Power of Memory. [Preprint]

Access the full-text of this item by clicking on the Open Access link.


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: 14 Mar 2023 10:34
Open Access URL:
Related URLs: