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. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

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

Official URL: http://dx.doi.org/10.1137/1.9781611977554.ch169

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 [27] 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 [23] 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 [30], 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 → ∞ [30]. 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.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Mar 2023 10:44
Last Modified:	21 Sep 2023 00:41
DOI:	10.1137/1.9781611977554.ch169
Open Access URL:	https://doi.org/10.1137/1.9781611977554.ch169
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3168970