\(\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 {\DSample }{d\text {-}{\rm S{\small AMPLE}}}\)
\(\newcommand {\TwoSample }{{\rm T{\small WO}}\text {-}{\rm S{\small AMPLE}}}\)
\(\newcommand {\Graphical }{{\rm G{\small RAPHICAL}}}\)
\(\newcommand {\DChoice }{d\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 {\DThinning }{d\text {-}{\rm T{\small HINNING}}}\)
\(\newcommand {\Twinning }{{\rm T{\small WINNING}}}\)
\(\newcommand {\Threshold }{{\rm T{\small HRESHOLD}}}\)
\(\newcommand {\Thinning }{{\rm T{\small HINNING}}}\)
\(\newcommand {\KThreshold }{k\text {-}{\rm T{\small HRESHOLD}}}\)
\(\newcommand {\OnePlusBeta }{(1+\beta )}\)
\(\newcommand {\Packing }{{\rm P{\small ACKING}}}\)
\(\newcommand {\Quantile }{{\rm Q{\small UANTILE}}}\)
\(\newcommand {\Memory }{{\rm M{\small EMORY}}}\)
\(\newcommand {\N }{\mathbb {N}}\)
\(\newcommand {\R }{\mathbb {R}}\)
\(\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 {\Heterogeneous }{{\rm H{\small ETEROGENEOUS}}}\)
\(\newcommand {\Gap }{\mathrm {Gap}}\)
\(\newcommand {\eps }{\epsilon }\)
The \(\DThinning \) processes are a special case of \(\DSample \) processes, where for each ball they examine up to \(d\) bins in an online manner to decide which one to use for allocation. They have the attractive property that the bin samples do not need to be “held”,
thus improving communication requirements.
These processes were investigated empirically by Eager, Lazowska and Zahorjan (1986) and were first analysed
for the lightly-loaded case by Feldheim and Li (2020). For the heavily-loaded case, an adaptive process was proposed in [3] which achievs an \(\Oh ( (d-1) \cdot (\log n)^{1/(d-1)})\) bound.
\(\DThinning (f_1^t, \ldots , f_{d-1}^t)\) Process (\(\subseteq \) \(\DSample (Q^t)\)):
Parameters: Decision functions \(f_1^t, \ldots , f_{d-1}^t\), where \(f_k^t : \mathcal {F}^t \times [n]^{k} \to \{ 0, 1 \}\) decides whether to accept the \(k\)-th sample.
Iteration: At step \(t \geq 0\), sample \(d\) bins \(j_1, \ldots , j_d \in [n]\), and allocate ball \(t+1\) using the decision function
\[ Q^t(\mathfrak {F}^t, j_1, \ldots , j_d, i) = f_i^t(\mathfrak {F}^t, j_1, \ldots , j_{i}) \cdot \prod _{k = 1}^{i-1} \left (1 - f_k^t(\mathfrak {F}^t, j_1, \ldots , j_{k})\right ). \]
For a \(\DThinning \) process, we define the number of samples \(S^t\) taken up to step \(t\), as
\[ S^t := t + \sum _{s = 1}^t \prod _{k = 1}^{d-1} \left ( 1 - f_k^s(\mathfrak {F}^s, j_1^s, \ldots , j_k^s) \right ), \]
and the sample-efficiency \(\eta ^t\) as
\[ \eta ^t := \frac {\sum _{i = 1}^n x_i^t}{S^t}. \]
References
-
[1] Derek L. Eager, Ed D. Lazowska, and John Zahorjan. “Adaptive load sharing in homogeneous distributed systems”. In: IEEE Transactions on Software Engineering SE-12.5 (1986), pp. 662–675. doi: 10.1109/TSE.1986.6312961.
-
[2] Ohad Noy Feldheim and Jiange Li. “Load balancing under d-thinning”. In: Electronic Communications in Probability 25 (2020), Paper No. 1, 13. doi: 10.1214/19-ecp282.
-
[3] Dimitrios Los and Thomas Sauerwald. “Balanced Allocations with Incomplete Information: The Power of Two Queries”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS’22). Vol. 215.
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 103:1–103:23. isbn: 978-3-95977-217-4. doi: 10.4230/LIPIcs.ITCS.2022.103.