Balanced Allocations with Heterogeneous Bins: The Power of Memory

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,...,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 ≥ n, this results in a gap (difference between the maximum and average load) of log2 log n + Θ(1) (with high probability). In this work, we consider the Memory process [SP02] 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 [MPS02] showed that in the lightly loaded case (m = n), the Memory process achieves a gap of 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 ≥ n. Secondly, we follow the heterogeneous bins model of Wieder [W07], 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 O(log log n) gap bound. This is in stark contrast with the Two-Choice (or any $d$-Choice with d=O(1)) process, where it is known that the gap diverges as m tends to infinity [W07]. 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 O(log n) for Memory in another relaxed setting with heterogeneous (weighted) balls and a cache which can only be maintained for two steps.