Balanced Allocations with Heterogeneous Bins: The Power of Memory

Download PDF

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.