Balanced Allocations with Heterogeneous Bins: The Power of Memory

DOI10.1137/1.9781611977554.CH169MaRDI QIDQ6424212zbMATH OpenFDO

Authors Thomas Sauerwald, John Sylvester

Publication date 23 January 2023

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH169

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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 $mgeqn$, this results in a gap (difference between the maximum and average load) of $lo{g}_{2}logn+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 $mathcalO(loglogn)$. 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 $mgeqn$. 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 $mathcalO(loglogn)$ gap bound. This is in stark contrast with the Two-Choice (or any $d$-Choice with $d=mathcalO(1)$) process, where it is known that the gap diverges as $mightarrowinfty$ [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 $mathcalO(logn)$ for Memory in another relaxed setting with heterogeneous (weighted) balls and a cache which can only be maintained for two steps.

Cited in

(1)

• An improved drift theorem for balanced allocations

This page was built for publication: Balanced Allocations with Heterogeneous Bins: The Power of Memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6424212)