\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\newcommand {\tcbset }[1]{}\)
\(\newcommand {\tcbsetforeverylayer }[1]{}\)
\(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\)
\(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\)
\(\newcommand {\tcblower }{}\)
\(\newcommand {\tcbline }{}\)
\(\newcommand {\tcbtitle }{}\)
\(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\)
\(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\)
\(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\)
\(\newcommand {\Batched }{b\text {-}{\rm B{\small ATCHED}}}\)
\(\newcommand {\OneChoice }{{\rm O{\small NE}}\text {-}{\rm C{\small HOICE}}}\)
\(\newcommand {\TwoChoice }{{\rm T{\small WO}}\text {-}{\rm C{\small HOICE}}}\)
\(\newcommand {\GBounded }{g\text {-}{\rm B{\small OUNDED}}}\)
\(\newcommand {\GMyopic }{g\text {-}{\rm M{\small YOPIC}}}\)
\(\newcommand {\RelativeThreshold }{{\rm R{\small ELATIVE}\text {-}T{\small RHESHOLD}}}\)
\(\newcommand {\MeanThinning }{{\rm M{\small EAN}\text {-}T{\small HINNING}}}\)
\(\newcommand {\TwoThinning }{{\rm T{\small WO}\text {-}T{\small HINNING}}}\)
\(\newcommand {\Twinning }{{\rm T{\small WINNING}}}\)
\(\newcommand {\Packing }{{\rm P{\small ACKING}}}\)
\(\newcommand {\Quantile }{{\rm Q{\small UANTILE}}}\)
\(\newcommand {\Memory }{{\rm M{\small EMORY}}}\)
\(\newcommand {\N }{\mathbb {N}}\)
\(\newcommand {\Oh }{\mathcal {O}}\)
\(\newcommand {\AdvTauDelay }{\tau \text {-}{\rm A{\small DV}}\text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\RandomTauDelay }{\tau \text {-}{\rm R{\small AND}}\text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\TauDelay }{\tau \text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\SigmaNoisyLoad }{\sigma \text {-}{\rm N{\small OISY}}\text {-}{\rm L{\small OAD}}}\)
\(\newcommand {\Gap }{\mathrm {Gap}}\)
Mitzenmacher, Prabhakar and Shah (2002) (see also [3]) introduced the \(d\)-\(\Memory \) process where the process is allowed to store \(d\) bins in a cache. For each ball, the process samples one bin uniformly at random and allocates to the least loaded of the cached
and sampled bins. The cache is then updated to store the least loaded of these items.
Below, we define the process for \(d = 1\).
\(\Memory \) Process:
Iteration: At step \(t \geq 0\), sample a uniform bin \(i\), and update its load (or of cached bin \(c_1^t\)):
\(\seteqnumber{0}{}{0}\)
\begin{equation*}
\begin{cases} x_{i}^{t+1} = x_{i}^{t} + 1 & \mbox {if $x_{i}^{t} < x_{c_1^t}^{t} $} \qquad \mbox {(also update cache $c_1^t=i$)}, \\ x_{i}^{t+1} = x_{i}^{t} + 1 & \mbox {if $x_{i}^{t} = x_{c_1^t}^{t} $}, \\ x_{c_1^t}^{t+1} =
x_{c_1^t}^{t} + 1 & \mbox {if $x_{i}^{t} > x_{c_1^t}^{t}$}. \end {cases}
\end{equation*}
In [2], it was shown that \(\Gap (n) = \log _{f(d)} \log n + \Theta (1)\), where \(f(d) \in (2d, 2d+1)\).
For the case \(d = 1\), in [1] it was shown that \(\Gap (m) = \Theta (\log \log n)\) for any \(m \geq n\). It was also shown that this \(\Theta (\log \log n)\) bound holds even when sampling from a
heterogeneous distribution (“power of memory”).
.
In [1] a variant of \(\Memory \) was studied were the cache is reset every \(k\) steps. It was shown that when \(k\) is constant, then \(\Gap (m) = \Theta (\log n)\).
References
-
[1] Dimitrios Los, Thomas Sauerwald, and John Sylvester. “Balanced Allocations with Heterogeneous Bins: The Power of Memory”. In: 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’23). SIAM, 2023,
pp. 4448–4477. doi: 10.1137/1.9781611977554.ch169.
-
[2] Michael Mitzenmacher, Balaji Prabhakar, and Devavrat Shah. “Load Balancing with Memory”. In: 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’02). IEEE, 2002, pp. 799–808. doi: 10.1109/SFCS.2002.1182005.
-
[3] Devravat Shah and Balaji Prabhakar. “The use of memory in randomized load balancing”. In: IEEE International Symposium on Information Theory (ISIT’02). IEEE, 2002, p. 125. doi: 10.1109/ISIT.2002.1023397.