The Threshold Process

The \(\Threshold (f)\) process is an instance of the \(\TwoThinning \) process where the decision function is based on a threshold \(f \in \N \). It was one of the processes considered by Eager, Lazowska and Zahorjan (1986). The optimal threshold for the case \(m = n\) was identified in [1] and which produces \(\Gap (n) = (1+o(1)) \cdot \sqrt {\frac {\log n}{\log \log n}}\). In [4], processes with a threshold relative to the average load (i.e., \(f^t = t/n + f(n)\)) were analysed, the so-called \(\RelativeThreshold \) proceses, proving an \(\Oh (\log n + f)\) gap. An adaptive process matching the \(\Omega (\log n/\log \log n)\) lower bound was developed in [2], who also showed that there is an adaptive process achieving \(\Gap (m) = \Oh ( (\log n)^{1/2 + o(1)})\) at any fixed \(m\).

The \(\Threshold (f)\) process:
Iteration: At each step \(t = 1, 2, \ldots \),

• Sample bins \(i_1, i_2 \in [n]\) uniformly at random.
• Then, update:

\[ \begin {cases} x_{i_1}^{t+1} = x_{i_1}^t + 1 & \text {if }x_{i_1}^t \leq f \\ x_{i_2}^{t+1} = x_{i_2}^t + 1 & \text {otherwise}. \end {cases} \]

Furthermore, in [3] an extension of \(\Threshold \) processes where considered where the process samples two bins uniformly at random and then sends \(k\) binary threshold queries. It then allocates the ball to the bin that was witnessed to be lesser loaded. In [4], an adaptive process was devised achieving \(\Gap (m) = \Oh (k \cdot (\log n)^{1/k})\) for any \(k \in [1, \log \log n]\)

\(\KThreshold (f_1^t, f_2^t, \ldots , f_k^t)\) Process (\(\subseteq \) \(\TwoSample (Q^t)\)):
Parameters: Threshold functions \(f_1^t, \ldots , f_{k}^t\), where \(f_i^t : \mathcal {F}^t \to \R \) such that for any filtration \(\mathfrak {F}^t \in \mathcal {F}^t\),

\[ \infty = f_0^t(\mathfrak {F}^t) > f_1^t(\mathfrak {F}^t) > f_2^t(\mathfrak {F}^t) > \ldots > f_k^t(\mathfrak {F}^t). \]

Iteration: At step \(t \geq 0\), we define the tightest witnessed upper bound for a bin as

\[ \ell (\mathfrak {F}^t, i) := \max \{ u \in [k]\cup \{ 0 \} : f_u^t(\mathfrak {F}^t) > x_{i}^t \}, \]

and define the decision function \(Q^t\) that decides between the two bin samples \(j_1\) and \(j_2\) as follows,

\[ Q^t(\mathfrak {F}^t, j_1, j_2, i) = \begin {cases} \frac {1}{2} & \text {if }\ell (\mathfrak {F}^t, j_1) = \ell (\mathfrak {F}^t, j_2), \\ \mathbf {1}_{\ell (\mathfrak {F}^t, j_1) > \ell (\mathfrak {F}^t, j_2)} & \text {else if }i = 1,\\ \mathbf {1}_{\ell (\mathfrak {F}^t, j_1) < \ell (\mathfrak {F}^t, j_2)} & \text {otherwise}. \end {cases} \]

References

[1] Ohad N. Feldheim and Ori Gurel-Gurevich. The power of thinning in balanced allocation. Electron. Commun. Probab., 26:Paper No. 34, 8, 2021.
[2] Ohad N. Feldheim, Ori Gurel-Gurevich, and Jiange Li. Long-term balanced allocation via thinning, 2021.
[3] Kazuo Iwama and Akinori Kawachi. Approximated two choices in randomized load balancing. In Proceedings of 15th International Symposium on Algorithms and Computation (ISAAC’04), volume 3341, pages 545–557. Springer-Verlag, 2004.
[4] 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), volume 215, pages 103:1–103:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.