\(\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 }\)
An improvement over the \(\OneChoice \) process is the \(\TwoChoice \) process, where for each ball two bins are chosen uniformly at random and the ball is allocated to the least loaded bin.
The \(\TwoChoice \) process:
Iteration: At each step \(t = 1, 2, \ldots \),
-
• Sample two bins \(i_1 = i_1^t\) and \(i_2 = i_2^t\) uniformly at random.
-
• Allocate one ball to bin \(i^t \in \{ i_1, i_2 \}\) such that \(y_{i^t}^{t+1} = \min \{ x_{i_1}^t, x_{i_2}^t \}\).
Azar, Broder, Karlin and Upfal (1999) (and implicitly Karp, Luby and Meyer auf der Heide (1996)) showed that the \(\TwoChoice \) process achieves w.h.p. an \(\log _2 \log n + \Theta (1)\) gap, which is an exponential improvement over the \(\Theta
(\frac {\log n}{\log \log n})\) gap of \(\OneChoice \). Berenbrink, Czumaj, Steger and Vöcking (2006)
extended the analysis to the heavily-loaded case (for any \(m \geq n\)) proving a gap of \(\log _2 \log n + \Theta (1)\).
.
Power of two-choices
The difference in the gap of the \(\OneChoice \) and \(\TwoChoice \) process is known as the “power of two choices" phenomenon.
One-Choice
Two-Choice
.
.
References
-
[1] Yossi Azar et al. “Balanced allocations”. In: SIAM J. Comput. 29.1 (1999), pp. 180–200. issn: 0097-5397. doi: 10.1137/S0097539795288490.
-
[2] Petra Berenbrink et al. “Balanced allocations: the heavily loaded case”. In: SIAM J. Comput. 35.6 (2006), pp. 1350–1385. issn: 0097-5397. doi: 10.1137/S009753970444435X.
-
[3] Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. “Efficient PRAM simulation on a distributed memory machine”. In: Algorithmica 16.4-5 (1996), pp. 517–542. issn:
0178-4617. doi: 10.1007/BF01940878.