# Balanced Allocations in Batches: The Tower of Two Choices111Full version of
a paper appearing in SPAA 2023.

Dimitrios Los<EMAIL_ADDRESS>Thomas Sauerwald
<EMAIL_ADDRESS>
###### Abstract

In the balanced allocation framework, the goal is to allocate $m$ balls into
$n$ bins, so as to minimize the gap (difference of maximum to average load).
The One-Choice process allocates each ball to a bin sampled independently and
uniformly at random. The Two-Choice process allocates balls sequentially, and
each ball is placed in the least loaded of two sampled bins. Finally, the
$(1+\beta)$-process mixes these processes, meaning each ball is allocated
using Two-Choice with probability $\beta\in(0,1)$, and using One-Choice
otherwise.

Despite Two-Choice being optimal in the sequential setting, it has been
observed in practice that it does not perform well in a parallel environment,
where load information may be outdated. Following [6], we study such a
parallel setting where balls are allocated in batches of size $b$, and balls
within the same batch are allocated with the same strategy and based on the
same load information.

For small batch sizes $b\in[n,n\log n]$, it was shown in [23] that Two-Choice
achieves an asymptotically optimal gap among all allocation processes with two
(or any constant number of) samples.

In this work, we focus on larger batch sizes $b\in[n\log n,n^{3}]$. It was
proved in [21] that Two-Choice leads to a gap of $\Theta(b/n)$. As our main
result, we prove that the gap reduces to $\mathcal{O}(\sqrt{(b/n)\cdot\log
n})$, if one runs the $(1+\beta)$-process with an appropriately chosen $\beta$
(in fact this result holds for a larger class of processes). This not only
proves the phenomenon that Two-Choice is not the best (leading to the
formation of “towers” over previously light bins), but also that mixing two
processes (One-Choice and Two-Choice) leads to a process which achieves a gap
that is asymptotically smaller than both. We also derive a matching lower
bound of $\Omega(\sqrt{(b/n)\cdot\log n})$ for any allocation process, which
demonstrates that the above $(1+\beta)$-process is asymptotically optimal.

Our analysis also works in the presence of randomly weighted balls, and also
implies exponential tails for the number of bins above a certain load value.

###### Contents

  1. 1 Introduction
  2. 2 Notation, Processes and Settings
    1. 2.1 Basic Notation
    2. 2.2 Processes
    3. 2.3 Conditions on Probability Vectors
    4. 2.4 Weighted and Batched Settings
  3. 3 Warm-up: $\mathcal{O}(\sqrt{b/n}\cdot\log n)$ Gap
  4. 4 Tight Bound: $\mathcal{O}(\sqrt{(b/n)\cdot\log n})$ Gap
    1. 4.1 Step 1: Concentration of the $\Gamma$ Potential
      1. 4.1.1 Preliminaries
      2. 4.1.2 Completing the Proof of Lemma 4.2
    2. 4.2 Step 2: Completing the Proof of Theorem 4.1
  5. 5 Lower Bounds on the Gap
  6. 6 Experimental Results
  7. 7 Conclusions
  8. A Tools
    1. A.1 Auxiliary Probabilistic Claims
    2. A.2 Concentration Inequalities

##  1 Introduction

##### Sequential balanced allocations.

In the sequential balanced allocations framework, there are $m$ tasks (balls)
to be allocated into $n$ servers (bins). It is well-known that allocating the
balls into bins sampled uniformly at random (a.k.a. One-Choice) leads w.h.p.
222In general, with high probability refers to probability of at least
$1-n^{-c}$ for some constant $c>0$. to a maximum load of $\Theta(\log
n/\log\log n)$ for $m=n$ and a gap (maximum load minus average load) of
$\Theta\big{(}\sqrt{(m/n)\cdot\log n}\big{)}$ for $m\geqslant n\log n$.

An improvement over One-Choice is the $d$-Choice process [16, 4, 7], where
each ball is allocated to the least loaded of $d$ bins sampled uniformly at
random. For any $m\geqslant n$, this process achieves w.h.p. an $\log_{d}\log
n+\Theta(1)$ gap, i.e., a gap that does not depend on $m$. For $d=2$, this
great improvement is known as “power-of-two-choices” (see also surveys [29,
39] for more details). Despite the simplistic nature of the balanced
allocation framework, the Two-Choice process has had a significant impact on
practical applications such as load balancing and distributed storage systems,
which was also acknowledged by the “ _ACM Paris Kanellakis Theory and Practice
Award 2020_ ” [3] (see also Applications below).

Several variants of Two-Choice have been studied. Of particular importance to
this work is the $(1+\beta)$-process, where each ball is allocated using Two-
Choice with probability $\beta\in(0,1]$ and One-Choice otherwise. Mitzenmacher
[27, Section 4.4.1] introduced this process as a model of Two-Choice with
erroneous comparisons. Peres, Talwar and Wieder [34] showed that for
$\beta:=\beta(n)\ll 1$, it achieves w.h.p. a $\Theta((\log n)/\beta)$ gap (see
also [21]), which becomes worse for smaller $\beta$, but still remains
independent of $m$. The $(1+\beta)$-process has also been applied to the
analysis of Two-Choice in the popular _graphical setting_ [17, 5, 34], where
bins are organized as vertices in a graph, and each ball is allocated to the
lesser loaded of two adjacent vertices of an edge sampled uniformly at random.

Another variant of Two-Choice that has received some attention recently is the
family of Two-Thinning processes [13, 14], where the ball is allocated to the
second sample only if the first one does not meet a certain criterion, e.g.,
based on a threshold on its load or a quantile on its rank.

It should be noted that the analyses of all these processes strongly rely on
the fact that the load information of each bin is updated after each
allocation. In effect this means balls can only be allocated sequentially,
which is a downside in distributed and parallel environments.

##### Outdated information settings.

In this work, we demonstrate that in outdated information settings by choosing
an appropriately small $\beta$, $(1+\beta)$ achieves the asymptotically
optimal gap among a large class of processes, including not only Two-Choice
(and One-Choice), but even adaptive processes that may allocate with a
different scheme after each batch. This confirms earlier empirical
observations that the performance of the Two-Choice process deteriorates under
outdated information and delays [38, 28, 9, 32, 15].

Berenbrink, Czumaj, Englert, Friedetzky and Nagel [6] introduced the
$b$-Batched setting where balls are allocated in batches of size $b$. That
means, in every batch the $b$ balls are allocated in parallel, as the decision
where to allocate the ball only depends on the load configuration before that
batch of balls arrived. For $b=n$, they proved that Two-Choice achieves w.h.p.
an $\mathcal{O}(\log n)$ gap. This bound was recently improved to $\Theta(\log
n/\log\log n)$ in [23], and in the same work, it was shown that Two-Choice has
a gap that matches the maximum load of One-Choice for $b$ balls, for any batch
size $b\in[n\cdot e^{-\log^{\Theta(1)}n},n\log n]$, and so it is
asymptotically optimal. In contrast, for $b\geqslant n\log n$, Two-Choice (and
a family of other processes) have w.h.p. a $\Theta(b/n)$ gap [21], a bound
which was shown to hold even in the presence of weights and on some graphs.
This analysis also demonstrates that increasing $d$ in the $d$-Choice process,
does not always improve the gap, which is in sharp contrast to the sequential
setting. In [23], a more powerful setting, $\tau$-Delay was studied for the
Two-Choice process, where an adversary can choose to report for each of the
bins any load from the last $\tau$ steps. For $b=\tau$, $b$-Batched is a
special instance of $\tau$-Delay and for any $\tau\leqslant n\log n$, the same
asymptotic bounds where shown to hold.

Outdated information settings have also been studied in the queuing setting
[38, 2, 19, 15, 28]. In particular, Mitzenmacher [28] studied the
corresponding version of the $b$-Batched setting, called the bulletin board
model with periodic updates, showing that some processes requiring centralized
coordination can outperform Two-Choice, but no explicit rigorous bounds were
proven. This shortcoming of Two-Choice was characterized as herd behavior,
meaning that some of the initially lighter bins receive disproportionately
many balls, turning them into heavy bins. In another empirically study, Dahlin
[9] also observed the herd behavior and suggested similar centralized
strategies to improve upon $d$-Choice. Regarding identifying optimal
processes, Whitt [38] remarks:

> We have shown that several natural selection rules are not optimal in
> various situations, but we have not identified any optimal rules.
> Identifying optimal rules in these situations would obviously be
> interesting, but appears to be difficult. Moreover, knowing an optimal rule
> might not be so useful because the optimal rule may be very complicated.

##### Applications.

Recently, several distributed low-latency schedulers, including Sparrow [32],
Eagle [10], Hawk [11], Peacock [18], Pigeon [37] and Tarcil [12], have used
variants of the Two-Choice process. In [32], with regards to the
implementation of Sparrow, the authors state:

> The power of two choices suffers from two remaining performance problems:
> first, server queue length is a poor indicator of wait time, and second, due
> to messaging delays, multiple schedulers sampling in parallel may experience
> race conditions.

Similar observations have been made in the context of distributed stream
processing [30, 31] and load balancers [25]. These studies support that batch
sizes $b=\Omega(n\log n)$ for which Two-Choice is no longer optimal are
relevant to real-world applications.

##### Weighted settings.

Several works study balanced allocation processes with weights [36, 8, 34,
21]. We will be focusing on weights sampled independently from probability
distributions with bounded moment generating functions as in [21] and [34],
which includes the geometric, exponential and Poisson distributions.

##### Our results.

In this work, we prove that a family of processes satisfying a mild technical
condition achieve the asymptotically optimal gap333By optimal we mean over all
processes that choose a probability allocation vector $p$, where $p_{i}$ gives
the probability to allocate to the $i$-th heaviest bin, at the beginning of
the batch and this vector remains the same throughout the entire batch.  of
$\mathcal{O}\big{(}\sqrt{(b/n)\cdot\log n}\big{)}$ in the weighted $b$-Batched
setting for $b\in[2n\log n,n^{3}]$, leading to roughly a quadratic improvement
over the gap of the Two-Choice process. This family of processes includes the
$(1+\beta)$-process, which is a process that can be easily implemented in a
decentralized manner, and demonstrates that by setting
$\beta=\sqrt{(n/b)\cdot\log n}$ we attain this asymptotically optimal gap.

We also provide lower bounds establishing the tightness of our upper bounds.
Interestingly, the lower bound of $\Omega(\sqrt{(b/n)\cdot\log n})$ applies to
a much more powerful class of allocation processes, where the allocation rule
is arbitrarily tailored at the beginning of the batch.

The intuition for these optimal processes relates to the herd behavior
observed in [28] and [9]. For the $d$-Choice process, the maximum probability
of allocating to a bin is $\max_{i\in[n]}p_{i}\approx d/n$. This means that,
for example, in Two-Choice in a batch of $b$ balls there are some bins that
receive $\approx 2b/n$ balls and so a gap of $\approx b/n$ arises. This
becomes worse as $d$ grows. To avoid this, we will investigate processes where
$\max_{i\in[n]}p_{i}=(1+o(1))/n$, which means that in expectation no bin
receives too many balls in any particular batch. For example, the
$(1+\beta)$-process has $\max_{i\in[n]}p_{i}\approx(1+\beta)/n$, which means
that this mixing of One-Choice steps with Two-Choice steps circumvents the
herd behavior. See Fig. 1.1 for a visualization of how $(1+\beta)$ achieves a
more balanced distribution than Two-Choice over one batch, and Fig. 1.2 for
how the gaps of different processes are getting worse with larger
$\max_{i\in[n]}p_{i}$. The asymptotic gap bounds of the One-Choice, Two-Choice
and $(1+\beta)$ processes in the $b$-Batched setting are summarized in Table
1.3. Our results also imply bounds for the shape of the load vector (see 4.4).
Our analysis also applies in the presence of randomly weighted balls, and also
implies exponential tails for the number of bins above a certain load value.

Two-Choice

$(1+\beta)$-process

Figure 1.1: The $b=750$ balls of the latest batch shown in red allocated over
the $n=35$ bins (left) for Two-Choice and (right) $(1+\beta)$ with
$\beta=1/2$. Observe that Two-Choice allocates more aggressively on the bins
that are lightly loaded at the beginning of the batch, while $(1+\beta)$
spreads the allocations more evenly.

##### Our techniques.

Our techniques build on and refine those in [21], making use of the hyperbolic
cosine potential function [34] and variants. More specifically, a slightly
weaker version of our tight upper bound is based on [21, Theorem 3.1] and a
refinement of [21, Lemma 4.1]. For our tight gap bound, our approach uses an
interplay between two hyperbolic cosine potential functions to prove
concentration and then an exponential potential with a larger smoothing
parameter to deduce the refined gap. A similar method was used in [21, Section
5], but one crucial novelty here is that we consider allocation processes
whose probability allocation vector have a small $\ell_{\infty}$ distance from
the uniform distribution. We believe that relating and comparing different
allocation processes based on their $\ell_{\infty}$ distance (or other
metrics) could be a promising avenue for future work. This can be also seen as
a natural relaxation of the _majorization technique_ , which has been the
dominant tool to relate different allocation processes [34, 22].

##### Organization.

In Section 2, we introduce the basic notation for balanced allocations, and
define the processes and settings that we will be working with. In particular,
in Section 2.3 we define general conditions on the probability allocation
vector used by the processes, under which our upper bounds on the gap apply.
In Section 3, we prove the $\mathcal{O}\big{(}\sqrt{b/n}\cdot\log n\big{)}$
bound on the gap for a family of processes in the weighted $b$-Batched
setting. In Section 4, we perform a refined analysis and improve this bound to
$\mathcal{O}\big{(}\sqrt{(b/n)\cdot\log n}\big{)}$. In Section 5, we show that
this achieved gap is asymptotically optimal, and in Section 6, we present some
empirical results on the gap of some specific processes. Finally, in Section
7, we summarize the results and conclude with some open problems.

Figure 1.2: In the $b$-Batched setting for large batch size $b$, the gaps
achieved by the processes are ordered by their maximum entry in the
probability allocation vector $p$: Three-Choice with
$\max_{i\in[n]}p_{i}\approx\frac{3}{n}$, Two-Choice with
$\max_{i\in[n]}p_{i}\approx\frac{2}{n}$, $(1+\beta)$ with
$\max_{i\in[n]}p_{i}\approx\frac{1+\beta}{n}$ for $\beta=0.5$,
$\beta=\sqrt{(n/b)\cdot\log n}$ and $\beta=\sqrt{(n/b)\cdot\log n}$. See Fig.
6.3 for full details of the experiment.

Process | Gap in Sequential Setting | Gap in $b$-Batched Setting | Batch Size
---|---|---|---
One-Choice |  $\Theta\left(\sqrt{(m/n)\cdot\log n}\right)$ [35] |  $\Theta\left(\sqrt{(m/n)\cdot\log n}\right)$ [35] | $b\in\mathbb{N}$
|  |  $\Theta(\log\log n)$ [23] | $b\in\Theta(1)$
|  |  $\Theta\left(\frac{\log n}{\log((4n/b)\log n)}\right)$ [23] | $b\in[n\cdot e^{-\log^{\Theta(1)}n},n\log n]$
Two-Choice | $\log_{2}\log n+\mathcal{O}(1)$ [4, 7] |  $\Theta\left(b/n\right)$ [21] | $b\in[n\log n,n^{3}]$
$(1+\beta)$, $\beta=\Theta(1)$ | $\Theta(\log n)$ [34] | $\Theta\left(b/n+\log n\right)$ [21] | $b\in[n,n^{3}]$
|  |  $\Omega\left(\sqrt{(b/n)\cdot\log n}\right)$ Thm 5.2 |
$(1+\beta)$-process, $\beta=\sqrt{(n/b)\cdot\log n}$ | $\Theta((\log n)/\beta)$ [34] |  $\mathcal{O}\left(\sqrt{(b/n)\cdot\log n}\right)$ Thm 4.1 | $b\in[2n\log n,n^{3}]$
|  |  $\Omega\left(\sqrt{(b/n)\cdot\log n}\right)$ Thm 5.2 |
$(1+\beta)$-process, $\beta=\sqrt{n/b}$ | $\Theta((\log n)/\beta)$ [34] |  $\mathcal{O}\left(\sqrt{b/n}\cdot\log n\right)$ Cor 3.2 | $b\geqslant n\log n$

Table 1.3: Overview of the gap bounds in previous works (rows in  Gray ) and
the gap bounds derived in this work (rows in  Green ). All gap bounds hold
with probability at least $1-o(1)$. Lower bounds hold for sufficiently large
enough $m$. For the sake of simplicity, we focus on the setting with unit
weights and only list results for $(1+\beta)$. Among all these processes, One-
Choice produces the worst gap in both settings, even though the gap does not
change between the $b$-Batched and sequential setting. For Two-Choice, the gap
becomes $b/n$ in the $b$-Batched setting with $b=\Omega(n\log n)$, whereas for
$(1+\beta)$ the gap is improved to $\sqrt{(b/n)\cdot\log n}$ (for a suitable
$\beta$).

##  2 Notation, Processes and Settings

In this section, we introduce notation, processes and settings used throughout
this work.

###  2.1 Basic Notation

We consider the allocation of $m$ balls into $n$ bins, which are labeled
$[n]:=\\{1,2,\ldots,n\\}$. For the moment, the $m$ balls are unweighted (or
equivalently, all balls have weight $1$). For any step $t\geqslant 0$, $x^{t}$
is the $n$-dimensional _load vector_ , where $x_{i}^{t}$ is the number of
balls allocated to bin $i$ in the first $t$ allocations. In particular,
$x_{i}^{0}=0$ for every $i\in[n]$. Finally, the _gap_ is defined as

$\operatorname{Gap}(t)=\max_{i\in[n]}x_{i}^{t}-\frac{t}{n}.$

It will also be convenient to sort the load vector $x$. To this end, let
$\widetilde{x}^{t}:=x^{t}-\frac{t}{n}$. Then, relabel the bins such that
$y^{t}$ is a permutation of $\widetilde{x}^{t}$ and $y_{1}^{t}\geqslant
y_{2}^{t}\geqslant\cdots\geqslant y_{n}^{t}$. Note that
$\sum_{i\in[n]}y_{i}^{t}=0$ and $\operatorname{Gap}(t)=y_{1}^{t}$. We call a
bin $i\in[n]$ _overloaded_ , if $y_{i}^{t}\geqslant 0$ and _underloaded_
otherwise.

A probability vector $p\in\mathbb{R}^{n}$ is any vector satisfying
$\sum_{i=1}^{n}p_{i}=1$ and $p_{i}\in[0,1]$ for $i\in[n]$. Following [34],
many allocation processes can be described by a time-invariant _probability
allocation vector_ $p^{t}$, which is the probability vector with $p_{i}^{t}$
being probability of allocating a ball to the $i$-th heaviest bin.

By $\mathfrak{F}^{t}$ we denote the filtration of the process until step $t$,
which in particular reveals the load vector $x^{t}$.

###  2.2 Processes

We start with a formal description of the One-Choice process.

One-Choice Process:
Iteration: For each $t\geqslant 0$, sample one bin $i$, independently and
uniformly at random. Then update:

$x_{i}^{t+1}=x_{i}^{t}+1.$

We continue with a formal description of the Two-Choice process.

Two-Choice Process:
Iteration: For each $t\geqslant 0$, sample two bins $i_{1}$ and $i_{2}$,
independently and uniformly at random. Let $i\in\\{i_{1},i_{2}\\}$ be such
that $x_{i}^{t}=\min\\{x_{i_{1}}^{t},x_{i_{2}}^{t}\\}$, breaking ties
randomly. Then update:

$x_{i}^{t+1}=x_{i}^{t}+1.$

It is immediate that the probability allocation vector of Two-Choice is

$p_{i}=\frac{2i-1}{n^{2}},\qquad\mbox{ for all $i\in[n]$.}$

Following [34], we recall the definition of the $(1+\beta)$-process which
interpolates between One-Choice and Two-Choice:

($1+\beta$) Process:
Parameter: A mixing factor $\beta\in(0,1]$.
Iteration: For each $t\geqslant 0$, sample two bins $i_{1}$ and $i_{2}$,
independently and uniformly at random. Let $i\in\\{i_{1},i_{2}\\}$ be such
that $x_{i}^{t}=\min\big{\\{}x_{i_{1}}^{t},x_{i_{2}}^{t}\big{\\}}$, breaking
ties randomly. Then update:

$\begin{cases}x_{i}^{t+1}=x_{i}^{t}+1&\mbox{with probability $\beta$},\\\
x_{i_{1}}^{t+1}=x_{i_{1}}^{t}+1&\mbox{otherwise}.\end{cases}$

In other words at each step, the $(1+\beta)$-process allocates the ball
following the Two-Choice rule with probability $\beta$, and otherwise
allocates the ball following the One-Choice rule. Therefore, its probability
allocation vector is given by

$p_{i}=(1-\beta)\cdot\frac{1}{n}+\beta\cdot\frac{2i-1}{n^{2}},\qquad\mbox{ for
all $i\in[n]$.}$

Recall that in [34] (and [21]), it was shown that
$\operatorname{Gap}(m)=\mathcal{O}\big{(}\frac{\log n}{\beta}\big{)}$ for any
$m\geqslant n$ and $\beta\in(0,1]$; so in particular, this gap (bound) does
not grow with $m$.

The next process is another relaxation of Two-Choice.

$\textsc{Quantile}(\delta)$ Process:
Parameter: A quantile $\delta\in\\{1/n,2/n,\ldots,1\\}$.
Iteration: For each $t\geqslant 0$, sample two bins $i_{1}$ and $i_{2}$,
independently and uniformly at random. Then update:

$\begin{cases}x_{i_{2}}^{t+1}=x_{i_{2}}^{t}+1&\mbox{if $i_{1}$ is among the
$\delta n$ heaviest bins},\\\
x_{i_{1}}^{t+1}=x_{i_{1}}^{t}+1&\mbox{otherwise}.\end{cases}$

Note that the $\textsc{Quantile}(\delta)$ processes can be implemented as a
two-phase procedure: First probe the bin $i_{1}$ and place the ball there if
$i_{1}$ is not among the $\delta n$ heaviest bins. Otherwise, take a second
sample $i_{2}$ and place the ball there. Since we only need to know whether a
bin’s rank is above or below a value, the response by a bin can be encoded as
a single bit (at the cost of knowing the rank of each bin). The probability
allocation vector of $\textsc{Quantile}(\delta)$ is given by:

$p_{i}=\begin{cases}\frac{\delta}{n}&\mbox{ if $1\leqslant i\leqslant\delta
n$},\\\ \frac{1+\delta}{n}&\mbox{ if $\delta n+1\leqslant i\leqslant
n$}.\end{cases}$

###  2.3 Conditions on Probability Vectors

In [21], the weighted $b$-Batched setting was analyzed for probability
allocation vectors satisfying the following two conditions. The first
condition says that the process has a small $\varepsilon/n$ bias to place away
from overloaded and towards underloaded bins; and the second condition says
that no bin has too high probability of being allocated.

  * •

Condition $\mathcal{C}_{1}$: There exist constant quantile444Here constant
means that the quantile satisfies $\delta\in(\delta_{1},\delta_{2})$ for
constant $\delta_{1},\delta_{2}\in(0,1)$. $\delta\in(0,1)$ and (not
necessarily constant) $\varepsilon\in(0,1)$, such that for any $1\leqslant
k\leqslant\delta n$,

$\sum_{i=1}^{k}p_{i}\leqslant(1-\varepsilon)\cdot\frac{k}{n},$

and similarly for any $\delta n+1\leqslant k\leqslant n$,

$\sum_{i=k}^{n}p_{i}\geqslant\left(1+\varepsilon\cdot\frac{\delta}{1-\delta}\right)\cdot\frac{n-k+1}{n}.$

  * •

Condition $\mathcal{C}_{2}$: There exists a $C>1$, such that
$\max_{i\in[n]}p_{i}\leqslant\frac{C}{n}$.

In the same paper [21, Proposition 7.4] it was shown that any process with
$\max_{i\in[n]}p_{i}\geqslant\frac{1+\varepsilon}{n}$ for
$\varepsilon=\Omega(1)$ also has $\operatorname{Gap}(m)=\Omega(b/n)$ for any
$b=\Omega(n\log n)$. Therefore, to improve on this asymptotic gao bound, we
have to consider processes with $\max_{i\in[n]}p_{i}=\frac{1+o(1)}{n}$. In our
analysis in Sections 3 and 4 we will make use of the following condition based
on the $\ell_{\infty}$-distance between the probability allocation vector $p$
and the uniform distribution (i.e., One-Choice):

  * •

Condition $\mathcal{C}_{3}$: There exists a $C>1$, such that

$\max_{i\in[n]}\left|p_{i}-\frac{1}{n}\right|\leqslant\frac{C-1}{n}.$

Note that this condition implies condition $\mathcal{C}_{2}$ for the same
$C>1$, but unlike $\mathcal{C}_{2}$ it imposes both an upper and a lower bound
on the $p_{i}$’s. It is easy to verify that $(1+\beta)$-process satisfies all
three conditions.

######  Lemma 2.1.

For any $\beta\in(0,1]$, the $(1+\beta)$-process satisfies condition
$\mathcal{C}_{1}$ with $\delta=\frac{1}{4}$ and $\varepsilon=\frac{\beta}{2}$,
condition $\mathcal{C}_{2}$ with $C=1+\beta$ and condition $\mathcal{C}_{3}$
with $C=1+\beta$.

###### Proof.

Recall that for the $(1+\beta)$-process, the probability allocation vector
satisfies

$p_{i}=(1-\beta)\cdot\frac{1}{n}+\beta\cdot\frac{2i-1}{n^{2}},\quad\text{for
all }i\in[n].$

We will first show that $\mathcal{C}_{1}$ holds with $\delta=1/4$ and
$\varepsilon=\beta/2$. For any $1\leqslant k\leqslant\delta n$, since $p$ is
non-decreasing the prefix sums satisfy

$\sum_{i=1}^{k}p_{i}\leqslant p_{k}\cdot k\leqslant p_{\delta n}\cdot
k\leqslant\left((1-\beta)+\beta\cdot(2\delta)\right)\cdot\frac{k}{n}=\left(1-\frac{\beta}{2}\right)\cdot\frac{k}{n},$

Similarly, for any $\delta n+1\leqslant k\leqslant n$, the suffix sums satisfy

$\displaystyle\sum_{i=k}^{n}p_{i}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{n-k+1}{n}\cdot(1-\beta)+\frac{\beta}{n^{2}}\cdot(n^{2}-(k-1)^{2})$
$\displaystyle=\frac{n-k+1}{n}\cdot(1-\beta)+\frac{\beta}{n^{2}}\cdot(n-k+1)\cdot(n+k-1)$
$\displaystyle=\left(1+\frac{\beta}{n}\cdot(k-1)\right)\cdot\frac{n-k+1}{n}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geqslant}}(1+\beta\cdot\delta)\cdot\frac{n-k+1}{n}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geqslant}}\left(1+\varepsilon\cdot\frac{\delta}{1-\delta}\right)\cdot\frac{n-k+1}{n},$

using in $(a)$ that $\sum_{i=1}^{u}(2i-1)=u^{2}$, in $(b)$ that
$k\geqslant\delta n+1$ and in $(c)$ that $\delta=1/4$ and
$\varepsilon=\beta/2$.

Condition $\mathcal{C}_{3}$ for $C=1+\beta$ (and hence $\mathcal{C}_{2}$ as
well) is verified as follows. As $p_{i}$ is increasing in $i\in[n]$,

$\max_{i\in[n]}\left|p_{i}-\frac{1}{n}\right|=\max\left\\{\frac{1}{n}-p_{1},p_{n}-\frac{1}{n}\right\\}=\frac{\beta}{n}-\frac{\beta}{n^{2}}\leqslant\frac{\beta}{n}.\qed$

Note that in contrast to Two-Choice which satisfies $\mathcal{C}_{3}$ for
$C=2-\frac{1}{n}$, by choosing $\beta$ small enough we can make the
probability allocation vector arbitrarily close to uniform.

We also note that for any process $\mathcal{P}$ satisfying condition
$\mathcal{C}_{3}$ for some $C>1$, we can define a process
$\mathcal{P}^{\prime}$ satisfying condition $\mathcal{C}_{3}$ for
$C^{\prime}\in(1,C)$ by mixing the probability allocation vector of
$\mathcal{P}$ with that of One-Choice with probability
$\eta=\frac{C^{\prime}-1}{C-1}$.

For instance, the $\textsc{Quantile}(1/2)$ process satisfies condition
$\mathcal{C}_{3}$ for any $C=1+1/2$ (since $\min_{i\in[n]}p_{i}=\frac{1}{2n}$
and $\max_{i\in[n]}p_{i}=\frac{3}{2n}$). Therefore, mixing
$\textsc{Quantile}(1/2)$ with One-Choice with probability $\eta\in[0,1]$,
gives the following probability allocation vector satisfying condition
$\mathcal{C}_{3}$ for $C=1+\eta/2$,

$p_{i}=\begin{cases}\frac{1}{n}\cdot(1-\eta)+\frac{1}{2n}\cdot\eta=\frac{1}{n}-\frac{\eta}{2n}&\text{if
}i\leqslant\frac{1}{2}n,\\\
\frac{1}{n}\cdot(1-\eta)+\frac{3}{2n}\cdot\eta=\frac{1}{n}+\frac{\eta}{2n}&\text{otherwise}.\end{cases}$

######  Observation 2.2.

The process obtained by mixing $\textsc{Quantile}(1/2)$ with One-Choice
satisfies condition $\mathcal{C}_{1}$ with $\delta=1/2$ and
$\varepsilon=\eta/2$, condition $\mathcal{C}_{2}$ with $C=1+\eta/2$ and
condition $\mathcal{C}_{3}$ with $C=1+\eta/2$.

###  2.4 Weighted and Batched Settings

As in [21], we now extend the definitions of Section 2.1 and Section 2.2 to
_weighted balls_ and later to the _batched setting_. To this end, let
$w^{t}\geqslant 0$ be the weight of the $t$-th ball to be allocated for
$t\geqslant 1$. By $W^{t}$ we denote the total weights of all balls allocated
after the first $t\geqslant 0$ allocations, so
$W^{t}:=\sum_{i=1}^{n}x_{i}^{t}=\sum_{s=1}^{t}w^{s}$. The normalized loads are
$\widetilde{x}_{i}^{t}:=x_{i}^{t}-\frac{W^{t}}{n}$, and with $y_{i}^{t}$ being
again the decreasingly sorted, normalized load vector, we have
$\operatorname{Gap}(t)=y_{1}^{t}$.

The weight of each ball will be drawn independently from a fixed distribution
$\mathcal{W}$ over $[0,\infty)$. Following [34], we assume that the
distribution $\mathcal{W}$ satisfies:

  * •

$\mathbf{E}[\,\mathcal{W}\,]=1$.

  * •

$\mathbf{E}[\,e^{\zeta\mathcal{W}}\,]<\infty$ for some $\zeta>0$.

Specific examples of distributions satisfying above conditions (after scaling)
are the geometric, exponential, binomial and Poisson distributions.

In the analysis we will be using the following property (see also [34]) and
refer to these distributions as $\textsc{Finite-MGF}(\zeta)$ (or
$\textsc{Finite-MGF}(S)$):

######  Lemma 2.3 ([21, Lemma 2.4]).

There exists $S:=S(\zeta)\geqslant\max\\{1,1/\zeta\\}$, such that for any
$\gamma\in(0,\min\\{\zeta/2,1\\})$ and any $\kappa\in[-1,1]$,

$\mathbf{E}\left[\,e^{\gamma\cdot\kappa\cdot\mathcal{W}}\,\right]\leqslant
1+\gamma\cdot\kappa+S\gamma^{2}\cdot\kappa^{2}.$

We will now describe the allocation of weighted balls into bins using a batch
size of $b\geqslant n$. For the sake of concreteness, let us first describe
the $b$-Batched setting if the allocation is done using Two-Choice. For a
given batch size consisting of $b$ consecutive balls, each ball of the batch
performs the following. First, it samples two bins $i_{1}$ and $i_{2}$
independently and uniformly at random, and compares the load the two bins had
at the beginning of the batch (let us denote the bin which has less load by
$i_{\min}$). Secondly, a weight is sampled from the distribution
$\mathcal{W}$. Then a weighted ball is added to bin $i_{\min}$. Recall that
since the load information is only updated at the beginning of the batch, all
allocations of the $b$ balls within the same batch can be performed in
parallel.

In the following, we will use a more general framework, where the process of
sampling (one or more) bins and then deciding where to allocate the ball to is
described by a probability allocation vector $p$ over the $n$ bins (Section
2.1). Also for the analysis, it will be convenient to focus on the normalized
and sorted load vector $y$, which is why the definition below is based on $y$
rather than the actual load vector $x$.

$b$-Batched Setting with Weights
Parameters: Batch size $b\geqslant n$, probability allocation vector $p$,
weight distribution $\mathcal{W}$.
Iteration: For each $t=0\cdot b,1\cdot b,2\cdot b,\ldots$:

  1. 1.

Sample $b$ bins $i_{1},i_{2},\ldots,i_{b}$ from $[n]$ following $p$.

  2. 2.

Sample $b$ weights $w^{t+1},w^{t+2},\ldots,w^{t+b}$ from $\mathcal{W}$.

  3. 3.

Update for each bin $i\in[n]$,

$z_{i}^{t+b}=y_{i}^{t}+\sum_{j=1}^{b}w^{t+j}\cdot\mathbf{1}_{i_{j}=i}-\frac{1}{n}\cdot\sum_{j=1}^{b}w^{t+j}.$

  4. 4.

Let $y^{t+b}$ be the vector $z^{t+b}$, sorted decreasingly.

We also look at the version of the processes that perform random tie-breaking
between bins of the same load. For $b=1$, this makes no observable difference
to the process, but for multiple steps, this effectively averages out the
probability over (possibly) multiple bins that have the same load. This would,
for instance, correspond to Two-Choice, randomly deciding between the two bins
if they have the same load. In particular, if $p$ is the original probability
allocation vector, then the one with random tie-breaking is
$\widetilde{p}(y^{t})$ (for $t$ being the beginning of the batch), where

$\widetilde{p}_{i}(y^{t}):=\frac{1}{|\\{j\in[n]:y_{j}^{t}=y_{i}^{t}\\}|}\cdot\sum_{j\in[n]:y_{j}^{t}=y_{i}^{t}}p_{j},\quad\text{for
all}i\in[n].$ (2.1)

$b$-Batched Setting with Weights and Random Tie-Breaking
Parameters: Batch size $b\geqslant n$, probability allocation vector $p$,
weight distribution $\mathcal{W}$.
Iteration: For each $t=0\cdot b,1\cdot b,2\cdot b,\ldots$:

  1. 1.

Let $\widetilde{p}:=\widetilde{p}(y^{t})$ be the probability allocation vector
accounting for random tie-breaking.

  2. 2.

Sample $b$ bins $i_{1},i_{2},\ldots,i_{b}$ from $[n]$ following
$\widetilde{p}$.

  3. 3.

Sample $b$ weights $w^{t+1},w^{t+2},\ldots,w^{t+b}$ from $\mathcal{W}$.

  4. 4.

Update for each bin $i\in[n]$,

$z_{i}^{t+b}=y_{i}^{t}+\sum_{j=1}^{b}w^{t+j}\cdot\mathbf{1}_{i_{j}=i}-\frac{1}{n}\cdot\sum_{j=1}^{b}w^{t+j}.$

  5. 5.

Let $y^{t+b}$ be the vector $z^{t+b}$, sorted decreasingly.

##  3 Warm-up: $\mathcal{O}(\sqrt{b/n}\cdot\log n)$ Gap

In this section, we will refine the analysis of [21, Section 4] to prove an
$\mathcal{O}(\sqrt{b/n}\cdot\log n)$ bound on the gap for a family of
processes. This will also be used as a starting point for the analysis in
Section 4 to obtain the tighter bound. The main theorem that we prove is the
following.

######  Theorem 3.1.

Consider any allocation process with probability allocation vector $p^{t}$
satisfying conditions $\mathcal{C}_{1}$ for constant $\delta\in(0,1)$ and (not
necessarily constant) $\varepsilon\in(0,1)$ as well as condition
$\mathcal{C}_{3}$ for some $C\in(1,1.9)$, at every step $t\geqslant 0$.
Further, consider the weighted $b$-Batched setting with weights from a
$\textsc{Finite-MGF}(S)$ distribution with $S\geqslant 1$ and a batch size
$b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$. Then, there exists a constant
$k:=k(\delta)>0$, such that for any step $m\geqslant 0$ being a multiple of
$b$,

$\mathbf{Pr}\left[\,\max_{i\in[n]}|y_{i}^{m}|\leqslant
k\cdot\frac{(C-1)^{2}}{\varepsilon}\cdot\frac{b}{n}\cdot\log
n\,\right]\geqslant 1-n^{-2}.$

Recall that by Lemma 2.1, the $(1+\beta)$-process satisfies condition
$\mathcal{C}_{1}$ with $\varepsilon=\frac{\beta}{2}$ and $\delta=\frac{1}{4}$,
and conditions $\mathcal{C}_{2}$ and $\mathcal{C}_{3}$ with $C=1+\beta$.

In particular, by choosing $\beta=\Theta\big{(}\sqrt{n/b}\big{)}$ we get a
process that is asymptotically better than Two-Choice and which is within just
a $\sqrt{\log n}$ multiplicative factor from the optimal gap bound proven for
unit weights in Section 5.

######  Corollary 3.2.

Let $b\geqslant n\log n$ and consider the weighted $b$-Batched setting with
weights from a $\textsc{Finite-MGF}(S)$ distribution with $S\in[1,b/4n]$.
Then, there exists a constant $k>0$ such that for the $(1+\beta)$-process with
$\beta=\sqrt{4S\cdot\frac{n}{b}}$ and for any step $m\geqslant 0$ being a
multiple of $b$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant
k\cdot\sqrt{\frac{Sb}{n}}\cdot\log n\,\right]\geqslant 1-n^{-2}.$

The analysis is based on the hyperbolic cosine potential which is defined for
smoothing parameter $\gamma>0$ as

$\displaystyle\Gamma^{t}:=\Gamma^{t}(\gamma):=\Phi^{t}+\Psi^{t}:=\sum_{i=1}^{n}e^{\gamma
y_{i}^{t}}+\sum_{i=1}^{n}e^{-\gamma y_{i}^{t}}.$ (3.1)

We also decompose $\Gamma^{t}$ by defining

$\Gamma_{i}^{t}:=\Phi_{i}^{t}+\Psi_{i}^{t}=e^{\gamma y_{i}^{t}}+e^{-\gamma
y_{i}^{t}},\quad\text{for any bin $i\in[n]$}.$

Further, we use the following shorthands to denote the changes in the
potentials over one step $\Delta\Phi_{i}^{t+1}:=\Phi_{i}^{t+1}-\Phi_{i}^{t}$,
$\Delta\Psi_{i}^{t+1}:=\Psi_{i}^{t+1}-\Psi_{i}^{t}$ and
$\Delta\Gamma_{i}^{t+1}:=\Gamma_{i}^{t+1}-\Gamma_{i}^{t}$.

We will make use of the following drift theorem shown in [21]. Note that in
statement of the theorem, rounds could consist of multiple single-step
allocations and in that case $p^{t}$ is not necessarily the probability
allocation vector, but it could be a probability vector giving an estimate for
the “average number of balls” allocated to a bin.

######  Theorem 3.3 (cf. [21, Theorem 3.1]).

Consider any allocation process $\mathcal{P}$ and a probability vector $p^{t}$
satisfying condition $\mathcal{C}_{1}$ for some constant $\delta\in(0,1)$ and
some $\varepsilon\in(0,1)$ at every round $t\geqslant 0$. Further assume that
there exist $K>0$,
$\gamma\in\big{(}0,\min\big{\\{}1,\frac{\varepsilon\delta}{8K}\big{\\}}\big{]}$
and $R>0$, such that for any round $t\geqslant 0$, process $\mathcal{P}$
satisfies for potentials $\Phi:=\Phi(\gamma)$ and $\Psi:=\Psi(\gamma)$ that,

$\sum_{i=1}^{n}\mathbf{E}\left[\,\left.\Delta\Phi_{i}^{t+1}\,\right|\,\mathfrak{F}^{t}\,\right]\leqslant\sum_{i=1}^{n}\Phi_{i}^{t}\cdot\left(\left(p_{i}^{t}-\frac{1}{n}\right)\cdot
R\cdot\gamma+K\cdot R\cdot\frac{\gamma^{2}}{n}\right),$

and

$\sum_{i=1}^{n}\mathbf{E}\left[\,\left.\Delta\Psi_{i}^{t+1}\,\right|\,\mathfrak{F}^{t}\,\right]\leqslant\sum_{i=1}^{n}\Psi_{i}^{t}\cdot\left(\left(\frac{1}{n}-p_{i}^{t}\right)\cdot
R\cdot\gamma+K\cdot R\cdot\frac{\gamma^{2}}{n}\right).$

Then, there exists a constant $c:=c(\delta)>0$, such that for
$\Gamma:=\Gamma(\gamma)$ and any round $t\geqslant 0$,

$\mathbf{E}\left[\,\left.\Delta\Gamma^{t+1}\,\right|\,\mathfrak{F}^{t}\,\right]\leqslant-\Gamma^{t}\cdot
R\cdot\frac{\gamma\varepsilon\delta}{8n}+R\cdot c\gamma\varepsilon,$

and

$\mathbf{E}\left[\,\Gamma^{t}\,\right]\leqslant\frac{8c}{\delta}\cdot n.$

Now we will show that any process satisfying condition $\mathcal{C}_{3}$, also
satisfies the preconditions of 3.3 for the expected change of the potential
functions $\Phi$ and $\Psi$ over one batch.

######  Lemma 3.4.

Consider any allocation process with probability allocation vector $p^{t}$
satisfying condition $\mathcal{C}_{3}$ for some $C\in(1,1.9)$ at every step
$t\geqslant 0$. Further, consider the weighted $b$-Batched setting with
weights from a $\textsc{Finite-MGF}(S)$ distribution with constant $S\geqslant
1$ and a batch size $b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$. Then for
$\Phi:=\Phi(\gamma)$ and $\Psi:=\Psi(\gamma)$ with any smoothing parameter
$\gamma\in(0,\frac{n}{2(C-1)\cdot b}]$ and any step $t\geqslant 0$ being a
multiple of $b$,

$\displaystyle\mathbf{E}\left[\,\left.\Phi^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]\leqslant\sum_{i=1}^{n}\Phi_{i}^{t}\cdot\left(1+\Big{(}p_{i}^{t}-\frac{1}{n}\Big{)}\cdot
b\cdot\gamma+\frac{5(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\right),$
(3.2)

and

$\displaystyle\mathbf{E}\left[\,\left.\Psi^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]\leqslant\sum_{i=1}^{n}\Psi_{i}^{t}\cdot\left(1+\Big{(}\frac{1}{n}-p_{i}^{t}\Big{)}\cdot
b\cdot\gamma+\frac{5(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\right).$
(3.3)

The proof proceeds in a similar manner to [21, Lemma 4.1], but we bound the
terms in 3.6 and 3.10 more tightly using the new condition $\mathcal{C}_{3}$.
Compared to the statement of [21, Lemma 4.1], the coefficients of the term
$\frac{\gamma^{2}}{n}$ change from $5C^{2}S^{2}\frac{b^{2}}{n}$ to
$5(C-1)^{2}\frac{b^{2}}{n}$. Note that $C$ is replaced by $C-1$, which makes a
difference when $C=1+o(1)$, and that $S$ does not appear as we have assumed
that $b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$.

###### Proof.

Consider an arbitrary step $t\geqslant 0$ being a multiple of $b$ and for
convenience let $p=p^{t}$. First note that the given assumptions
$\gamma\leqslant\frac{n}{2(C-1)\cdot b}$ and
$b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$ imply that

$\displaystyle\gamma\leqslant\frac{n}{2(C-1)\cdot b}\leqslant\frac{C-1}{4CS}.$
(3.4)

Consider an arbitrary bin $i\in[n]$. Define the binary vector
$Z\in\\{0,1\\}^{b}$, where $Z_{j}$ indicates whether the $j$-th ball was
allocated to bin $i$. The expected change for the overload potential
$\Phi_{i}^{t}$ of the bin is given by,

$\displaystyle\mathbf{E}\left[\,\left.\Phi_{i}^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]$
$\displaystyle=\Phi_{i}^{t}\cdot\sum_{z\in\\{0,1\\}^{b}}\mathbf{Pr}\left[\,Z=z\,\right]\cdot\mathbf{E}\left[\,\left.e^{\gamma\sum_{j=1}^{b}\left(z_{j}w^{t+j}-\frac{w^{t+j}}{n}\right)}\,\right|\,\mathfrak{F}^{t},Z=z\,\right].$

In the following, let us upper bound the factor of $\Phi_{i}^{t}$:

$\displaystyle\sum_{z\in\\{0,1\\}^{b}}\mathbf{Pr}\left[\,Z=z\,\right]\cdot\mathbf{E}\left[\,\left.e^{\gamma\sum_{j=1}^{b}\left(z_{j}w^{t+j}-\frac{w^{t+j}}{n}\right)}\,\right|\,\mathfrak{F}^{t},Z=z\,\right]$
$\displaystyle\qquad\stackrel{{\scriptstyle(a)}}{{=}}\\!\\!\\!\sum_{z\in\\{0,1\\}^{b}}\prod_{j=1}^{b}(p_{i})^{z_{j}}(1-p_{i})^{1-z_{j}}(\mathbf{E}[\,e^{\gamma
W(1-\frac{1}{n})}\,])^{z_{j}}(\mathbf{E}[\,e^{-\gamma W/n}\,])^{1-z_{j}}$
$\displaystyle\qquad\stackrel{{\scriptstyle(b)}}{{\leqslant}}\\!\\!\\!\sum_{z\in\\{0,1\\}^{b}}\prod_{j=1}^{b}\left(p_{i}\cdot\left(1+\gamma\cdot\left(1-\frac{1}{n}\right)+S\gamma^{2}\right)\right)^{z_{j}}\cdot\left((1-p_{i})\cdot\left(1-\frac{\gamma}{n}+\frac{S\gamma^{2}}{n^{2}}\right)\right)^{1-z_{j}}$
$\displaystyle\qquad\stackrel{{\scriptstyle(c)}}{{=}}\left(p_{i}\cdot\left(1+\gamma\cdot\left(1-\frac{1}{n}\right)+S\gamma^{2}\right)+(1-p_{i})\cdot\left(1-\frac{\gamma}{n}+\frac{S\gamma^{2}}{n^{2}}\right)\right)^{b}$
$\displaystyle\qquad=\left(1+\gamma\cdot\left(p_{i}-\frac{1}{n}\right)+p_{i}\cdot
S\gamma^{2}+(1-p_{i})\cdot\frac{S\gamma^{2}}{n^{2}}\right)^{b}$
$\displaystyle\qquad\stackrel{{\scriptstyle(d)}}{{\leqslant}}\left(1+\gamma\cdot\left(p_{i}-\frac{1}{n}\right)+2\cdot
p_{i}\cdot S\gamma^{2}\right)^{b},$ (3.5)

using in $(a)$ that the weights are independent given $\mathfrak{F}^{t}$, in
$(b)$ Lemma 2.3 twice with $\kappa=1-\frac{1}{n}$ and with
$\kappa=-\frac{1}{n}$ respectively (and that $(1-1/n)^{2}\leqslant 1$), in
$(c)$ the binomial theorem and in $(d)$ that $p_{i}\geqslant\frac{1}{n^{2}}$
by condition $\mathcal{C}_{3}$ for $C\in(1,1.9)$. Let us define

$\displaystyle u_{i}:=\left(p_{i}-\frac{1}{n}\right)\cdot\gamma+2\cdot
p_{i}\cdot S\gamma^{2}.$ (3.6)

We will now show that $|u_{i}\cdot b|\leqslant 2(C-1)\cdot
b\cdot\frac{\gamma}{n}\leqslant 1$, which holds indeed since

$\displaystyle|u_{i}\cdot b|$
$\displaystyle=\left\lvert\left(p_{i}-\frac{1}{n}\right)\cdot
b\cdot\gamma+2\cdot p_{i}\cdot b\cdot S\gamma^{2}\right|$
$\displaystyle\leqslant\left\lvert\left(p_{i}-\frac{1}{n}\right)\cdot
b\cdot\gamma\right|+2\cdot p_{i}\cdot b\cdot S\gamma^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\frac{C-1}{n}\cdot
b\cdot\gamma+2\cdot\frac{C}{n}\cdot b\cdot S\gamma^{2}$
$\displaystyle=(C-1+2CS\gamma)\cdot b\cdot\frac{\gamma}{n}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}2(C-1)\cdot
b\cdot\frac{\gamma}{n}$ (3.7)
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}1,$ (3.8)

using in $(a)$ that $\big{|}p_{i}-\frac{1}{n}\big{|}\leqslant\frac{C-1}{n}$ by
condition $\mathcal{C}_{3}$, in $(b)$ that $\gamma\leqslant\frac{C-1}{2CS}$ by
3.4 and in $(c)$ that $\gamma\leqslant\frac{n}{2(C-1)\cdot b}$.

Then,

$\displaystyle\mathbf{E}\left[\,\left.\Phi_{i}^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Phi_{i}^{t}\cdot
e^{u_{i}\cdot b}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\Phi_{i}^{t}\cdot\left(1+u_{i}\cdot
b+(u_{i}\cdot b)^{2}\right)$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(\ref{eq:u_definition})}}{{=}}\Phi_{i}^{t}\cdot\left(1+\left(p_{i}-\frac{1}{n}\right)\cdot
b\cdot\gamma+2\cdot p_{i}\cdot b\cdot S\gamma^{2}+(u_{i}\cdot b)^{2}\right)$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(\ref{eq:yb_bounded_1})}}{{\leqslant}}\Phi_{i}^{t}\cdot\left(1+\left(p_{i}-\frac{1}{n}\right)\cdot
b\cdot\gamma+2\cdot p_{i}\cdot b\cdot S\gamma^{2}+\left(2(C-1)\cdot
b\cdot\frac{\gamma}{n}\right)^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}\Phi_{i}^{t}\cdot\left(1+\left(p_{i}-\frac{1}{n}\right)\cdot
b\cdot\gamma+\frac{5(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\right),$

using in $(a)$ that $1+v\leqslant e^{v}$ for any $v$, in $(b)$ that
$e^{v}\leqslant 1+v+v^{2}$ for $v\leqslant 1.75$ and 3.8, and in $(c)$ that
$\frac{(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\geqslant
2\cdot\frac{C}{n}\cdot b\cdot S\gamma^{2}\geqslant 2\cdot p_{i}\cdot b\cdot
S\gamma^{2}$, since $b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$.

Similarly, for the underloaded potential $\Psi^{t}$, for any bin $i\in[n]$,

$\displaystyle\mathbf{E}\left[\,\left.\Psi_{i}^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]=\Psi_{i}^{t}\cdot\sum_{z\in\\{0,1\\}^{b}}\mathbf{Pr}\left[\,Z=z\,\right]\cdot\mathbf{E}\left[\,\left.e^{-\gamma\sum_{j=1}^{b}\left(z_{j}w^{t+j}-\frac{w^{t+j}}{n}\right)}\,\right|\,\mathfrak{F}^{t},Z=z\,\right].$

As before, we will upper bound the factor of $\Psi_{i}^{t}$:

$\displaystyle\sum_{z\in\\{0,1\\}^{b}}\mathbf{Pr}\left[\,Z=z\,\right]\cdot\mathbf{E}\left[\,\left.e^{-\gamma\sum_{j=1}^{b}\left(z_{j}w^{t+j}-\frac{w^{t+j}}{n}\right)}\,\right|\,\mathfrak{F}^{t},Z=z\,\right]$
$\displaystyle\qquad\stackrel{{\scriptstyle(a)}}{{=}}\\!\\!\\!\sum_{z\in\\{0,1\\}^{b}}\prod_{j=1}^{b}(p_{i})^{z_{j}}(1-p_{i})^{1-z_{j}}(\mathbf{E}[\,e^{-\gamma
W\cdot(1-\frac{1}{n})}\,])^{z_{j}}(\mathbf{E}[\,e^{\gamma W/n}\,])^{1-z_{j}}$
$\displaystyle\qquad\stackrel{{\scriptstyle(b)}}{{\leqslant}}\\!\\!\\!\sum_{z\in\\{0,1\\}^{b}}\prod_{j=1}^{b}\left(p_{i}\cdot\left(1-\gamma\cdot\left(1-\frac{1}{n}\right)+S\gamma^{2}\right)\right)^{z_{j}}\cdot\left((1-p_{i})\cdot\left(1+\frac{\gamma}{n}+\frac{S\gamma^{2}}{n^{2}}\right)\right)^{1-z_{j}}$
$\displaystyle\qquad\stackrel{{\scriptstyle(c)}}{{=}}\left(p_{i}\cdot\left(1-\gamma\cdot\left(1-\frac{1}{n}\right)+S\gamma^{2}\right)+(1-p_{i})\cdot\left(1+\frac{\gamma}{n}+\frac{S\gamma^{2}}{n^{2}}\right)\right)^{b}$
$\displaystyle\qquad=\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot\gamma+p_{i}\cdot
S\gamma^{2}+(1-p_{i})\cdot\frac{S\gamma^{2}}{n^{2}}\right)^{b}$
$\displaystyle\qquad\stackrel{{\scriptstyle(d)}}{{\leqslant}}\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot\gamma+2\cdot
p_{i}\cdot S\gamma^{2}\right)^{b},$ (3.9)

using in $(a)$ that the weights are independent given $\mathfrak{F}^{t}$, in
$(b)$ Lemma 2.3 twice with $\kappa=-\big{(}1-\frac{1}{n}\big{)}$ and with
$\kappa=\frac{1}{n}$ respectively, in $(c)$ the binomial theorem and in $(d)$
that $p_{i}\geqslant\frac{1}{n^{2}}$ by condition $\mathcal{C}_{3}$ for
$C\in(1,1.9)$. Let us define

$\displaystyle\widetilde{u}_{i}:=\left(\frac{1}{n}-p_{i}\right)\cdot\gamma+2\cdot
p_{i}\cdot S\gamma^{2}.$ (3.10)

Similarly, to 3.8, we get that

$\displaystyle|\widetilde{u}_{i}\cdot b|$
$\displaystyle\leqslant\left\lvert\left(\frac{1}{n}-p_{i}\right)\cdot
b\cdot\gamma\right|+2\cdot p_{i}\cdot b\cdot S\gamma^{2}\leqslant 2(C-1)\cdot
b\cdot\frac{\gamma}{n}$ (3.11) $\displaystyle\leqslant 1.$ (3.12)

So,

$\displaystyle\mathbf{E}\left[\,\left.\Psi_{i}^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Psi_{i}^{t}\cdot
e^{\widetilde{u}_{i}\cdot b}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\Psi_{i}^{t}\cdot\left(1+\widetilde{u}_{i}\cdot
b+(\widetilde{u}_{i}\cdot b)^{2}\right)$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(\ref{eq:tile_u_definition})}}{{=}}\Psi_{i}^{t}\cdot\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot
b\cdot\gamma+2\cdot p_{i}\cdot S\gamma^{2}\cdot b+(\widetilde{u}_{i}\cdot
b)^{2}\right)$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(\ref{eq:tilde_u_b_1})}}{{\leqslant}}\Psi_{i}^{t}\cdot\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot
b\cdot\gamma+2\cdot p_{i}\cdot b\cdot\gamma^{2}+\left(2(C-1)\cdot
b\cdot\frac{\gamma}{n}\right)^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}\Psi_{i}^{t}\cdot\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot
b\cdot\gamma+\frac{5(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\right),$

using in $(a)$ that $1+v\leqslant e^{v}$ for any $v$, in $(b)$ that
$e^{v}\leqslant 1+v+v^{2}$ for $v\leqslant 1.75$ and 3.12, and in $(c)$ that
$\frac{(C-1)^{2}b}{n}\cdot b\cdot\frac{\gamma^{2}}{n}\geqslant
2\cdot\frac{C}{n}\cdot b\cdot S\gamma^{2}\geqslant 2\cdot p_{i}\cdot b\cdot
S\gamma^{2}$, since $b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$. ∎

Having verified the preconditions for 3.3, we are now ready to prove the bound
on the gap for this family of processes.

######  Remark 3.5.

The same upper bound in 3.1 also holds for processes with random tie breaking.
The reason for this is that $(i)$ averaging probabilities in 2.1 can only
reduce the maximum entry (and increase the minimum) in the allocation vector
$\widetilde{p}^{t}$, i.e.
$\max_{i\in[n]}\widetilde{p}_{i}^{t}(x^{t})\leqslant\max_{i\in[n]}p_{i}$, so
it still satisfies condition $\mathcal{C}_{3}$ and $(ii)$ moving probability
between bins $i,j$ with $x_{i}^{t}=x_{j}^{t}$ (and thus
$\Phi_{i}^{t}=\Phi_{j}^{t}$ and $\Psi_{i}^{t}=\Psi_{j}^{t}$), implies that the
aggregate upper bounds 3.2 and 3.3 in Lemma 3.4 remain the same.

###### Proof of 3.1.

Consider the $b$-Batched setting at steps that are a multiple of $b$ and
rounds consisting of $b$ consecutive allocations. By Lemma 3.4, the
preconditions of 3.3 are satisfied for $K:=5\cdot(C-1)^{2}\cdot\frac{b}{n}$,
$R:=b$ and
$\gamma:=\frac{\varepsilon\delta}{8K}=\frac{\varepsilon\delta}{40\cdot(C-1)^{2}\cdot\frac{b}{n}}\leqslant\frac{n}{2(C-1)\cdot
b}$, since $\varepsilon\leqslant C-1$ and also $\gamma\leqslant 1$ since
$b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$, $C>1$ and $S\geqslant 1$ (as in
3.4),

$\gamma\leqslant\frac{n}{2(C-1)\cdot b}\leqslant\frac{C-1}{4CS}\leqslant 1.$

Hence, by 3.3, there exists a constant $c:=c(\delta)>0$ such that for any step
$m\geqslant 0$ which is a multiple of $b$,

$\mathbf{E}\left[\,\Gamma^{m}\,\right]\leqslant\frac{8c}{\delta}\cdot n.$

Therefore, by Markov’s inequality

$\mathbf{Pr}\left[\,\Gamma^{m}\leqslant\frac{8c}{\delta}\cdot
n^{3}\,\right]\geqslant 1-n^{-2}.$

To conclude the claim, note that when
$\big{\\{}\Gamma^{m}\leqslant\frac{8c}{\delta}\cdot n^{3}\big{\\}}$ holds,
then also,

$\max_{i\in[n]}|y_{i}^{m}|\leqslant\frac{1}{\gamma}\cdot\left(\log\left(\frac{8c}{\delta}\right)+3\cdot\log
n\right)\leqslant 4\cdot\frac{\log n}{\alpha}\leqslant 4\cdot\frac{8\cdot
5\cdot(C-1)^{2}}{\varepsilon\delta}\cdot\frac{b}{n}\cdot\log n.\qed$

##  4 Tight Bound: $\mathcal{O}(\sqrt{(b/n)\cdot\log n})$ Gap

In this section, we will prove the stronger
$\mathcal{O}\big{(}\sqrt{(b/n)\cdot\log n}\big{)}$ bound on the gap for a
family of processes in the weighted $b$-Batched setting (with $b\in[2n\log
n,n^{3}]$). More specifically, these processes are a subset of the ones
analyzed in Section 3 and include the $(1+\beta)$-process with
$\beta=\sqrt{(n/b)\log n}$, as well as $\textsc{Quantile}(1/2)$ mixed with
One-Choice. As we will show in Section 5, these processes achieve the
asymptotically optimal bound.

######  Theorem 4.1.

Consider the weighted $b$-Batched setting with any $b\in[2n\log n,n^{3}]$ and
weights from a $\textsc{Finite-MGF}(S)$ distribution with constant $S\geqslant
1$. Further let $\varepsilon=\sqrt{(n/b)\cdot\log n}$. Consider any process
with probability allocation vector $p^{t}$ satisfying at every step
$t\geqslant 0$, condition $\mathcal{C}_{1}$ for constant $\delta\in(0,1)$ and
$\varepsilon$, as well as condition $\mathcal{C}_{3}$ for $C=1+\varepsilon$.
Then, there exists a constant $\kappa:=\kappa(\delta,S)>0$, such that for any
step $m\geqslant 0$ being a multiple of $b$,

$\mathbf{Pr}\left[\,\max_{i\in[n]}y_{i}^{m}\leqslant\kappa\cdot\sqrt{\frac{b}{n}\cdot\log
n}\,\right]\geqslant 1-n^{-2}.$

There are two key steps in the proof:

Step 1: Similarly to the analysis in [22], we will use two instances of the
hyperbolic cosine potential (defined in 3.1), in order to show that it is
concentrated at $\mathcal{O}(n)$. More specifically, we will be using
$\Gamma_{1}:=\Gamma_{1}(\gamma_{1})$ with the smoothing parameter
$\gamma_{1}:=\frac{\delta}{40S}\cdot\sqrt{n/(b\log n)}$ and
$\Gamma_{2}:=\Gamma_{2}(\gamma_{2})$ with
$\gamma_{2}:=\frac{\gamma_{1}}{8\cdot 30}$, i.e., with a smoothing parameter
which is a large constant factor smaller than $\gamma_{1}$. So, in particular
$\Gamma_{2}^{t}\leqslant\Gamma_{1}^{t}$ at any step $t\geqslant 0$.

In the following lemma, proven in Section 4.1, we show that w.h.p.
$\Gamma_{2}=\mathcal{O}(n)$ for any $\log^{3}n$ consecutive batches.

######  Lemma 4.2.

Consider any process satisfying the conditions in 4.1. Let
$\widetilde{c}:=2\cdot\frac{8c}{\delta}$ where $c:=c(\delta)>0$ is the
constant from 3.3. Then, for any step $t\geqslant 0$ being a multiple of $b$,

$\mathbf{Pr}\left[\,\bigcap_{j\in[0,\log^{3}n]}\left\\{\Gamma_{2}^{t+j\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]\geqslant 1-n^{-3}.$

The proof follows the interplay between the two hyperbolic cosine potentials,
in that conditioning on $\Gamma_{1}^{t}=\operatorname{poly}(n)$ (which follows
w.h.p. by the analysis in Section 3) implies that
$\big{|}\Delta\Gamma_{2}^{t+1}\big{|}\leqslant
n^{1/4}\cdot\sqrt{(n/b)\cdot\log n}$ (Lemma 4.6 $(ii)$). This in turn allows
us to apply a bounded difference inequality to prove concentration for
$\Gamma_{2}$. In contrast to [22] and [23], here we need a slightly different
concentration inequality A.6 (also used in [21]), as in a single batch the
load of a bin may change by a large amount (with small probability). The
complete proof is given in Section 4.1.

Step 2: Consider an arbitrary step $s=t+j\cdot b$ where
$\\{\Gamma_{2}^{s}\leqslant\widetilde{c}n\\}$ holds. Then, the number of bins
$i$ with load $y_{i}^{s}$ at least
$z:=\frac{1}{\gamma_{2}}\cdot\log(\widetilde{c}/\delta)=\Theta(\sqrt{(b/n)\cdot\log
n})$ is at most $\widetilde{c}n\cdot e^{-\gamma_{2}z}=\delta n$. With this in
mind, we define the following potential function for any step $t\geqslant 0$,
which only takes into account bins that are overloaded by at least $z$ balls:

$\Lambda^{t}:=\Lambda^{t}(\lambda,z):=\sum_{i:y_{i}^{t}\geqslant
z}\Lambda_{i}^{t}:=\sum_{i:y_{i}^{t}\geqslant
z}e^{\lambda\cdot(y_{i}^{t}-z)},$

where $\lambda:=\frac{\varepsilon}{4CS}=\Theta(\sqrt{(n/b)\cdot\log n})$ and
we define $\Lambda_{i}^{t}=0$ for the rest of the bins $i$. This means that
when $\\{\Gamma_{2}^{s}\leqslant\widetilde{c}n\\}$ holds, the probability of
allocating to one of these bins is
$p_{i}^{s}\leqslant\frac{1-\varepsilon}{n}$, because of the condition
$\mathcal{C}_{1}$. Hence, the potential drops in expectation over one batch
(Lemma 4.10) and this means that w.h.p. $\Lambda^{m}=\operatorname{poly}(n)$,
which implies that $\operatorname{Gap}(m)=\mathcal{O}(z+\lambda^{-1}\cdot\log
n)=\mathcal{O}(\sqrt{(b/n)\cdot\log n})$ gap.

###  4.1 Step 1: Concentration of the $\Gamma$ Potential

Recall that in 4.1, we considered the weighted $b$-Batched setting with any
$b\in[2n\log n,n^{3}]$ and weights sampled independently from a
$\textsc{Finite-MGF}(S)$ distribution with constant $S\geqslant 1$, for any
allocation process with probability allocation vector $p^{t}$ satisfying
condition $\mathcal{C}_{1}$ for constant $\delta\in(0,1)$ and
$\varepsilon\in(0,1)$ as well as condition $\mathcal{C}_{3}$ for some $C>1$,
at every step $t\geqslant 0$.

######  Lemma 4.3 (Restated, page 4.2).

Consider any process satisfying the conditions in 4.1. Let
$\widetilde{c}:=2\cdot\frac{8c}{\delta}$ where $c:=c(\delta)>0$ is the
constant from 3.3. Then, for any step $t\geqslant 0$ being a multiple of $b$,

$\mathbf{Pr}\left[\,\bigcap_{j\in[0,\log^{3}n]}\left\\{\Gamma_{2}^{t+j\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]\geqslant 1-n^{-3}.$

######  Remark 4.4.

The number of bins $i\in[n]$ with normalized load value $y_{i}^{t}$ at least
$z$ is w.h.p. at most $\widetilde{c}n\cdot e^{-\gamma_{2}z}$, where
$\gamma_{2}=\Theta(\sqrt{(n/b)\cdot\log n})$.

The proof of this lemma is similar to the proofs in [21, Section 5] and [22,
Section 5], in that we use the interplay between two instances of the
hyperbolic cosine potential $\Gamma_{1}:=\Gamma_{1}(\gamma_{1})$ and
$\Gamma_{2}:=\Gamma_{2}(\gamma_{2})$ with smoothing parameter $\gamma_{2}$
being a large constant factor smaller than $\gamma_{1}$. More specifically, we
will be working with $\gamma_{1}:=\frac{\delta}{40S}\cdot\sqrt{n/(b\log n)}$
and $\gamma_{2}:=\frac{\gamma_{1}}{8\cdot 30}$.

The rest of this section is organized as follows. In Section 4.1.1, we
establish some basic properties for the potentials $\Gamma_{1}$ and
$\Gamma_{2}$ and in Section 4.1.2 we use these to show that w.h.p.
$\Gamma_{2}^{t}=\mathcal{O}(n)$ for at least $\log^{3}n$ batches, and complete
the proof of Lemma 4.2. Then, in Section 4.2, we complete the proof of 4.1.

####  4.1.1 Preliminaries

We define the following event, for any step $t\geqslant 0$

$\mathcal{H}^{t}:=\left\\{w^{t}\leqslant\frac{15}{\zeta}\cdot\log n\right\\},$

which means that the weight of the ball sampled in step $t$ is
$\mathcal{O}(\log n)$ (since by assumption $\zeta>0$ is constant). By a simple
Chernoff bound and a union bound, we can deduce that this holds for a
$\operatorname{poly}(n)$-long interval.

######  Lemma 4.5 (cf. [21, Lemma 5.4]).

Consider any $\textsc{Finite-MGF}(\zeta)$ distribution $\mathcal{W}$ with
constant $\zeta>0$. Then, for any steps $t_{0}\geqslant 0$ and
$t_{1}\in[t_{0},t_{0}+n^{3}\log^{3}n]$, we have that

$\mathbf{Pr}\left[\,\bigcap_{s\in[t_{0},t_{1}]}\mathcal{H}^{s}\,\right]\geqslant
1-n^{-10}$

We will now show that when $\Gamma_{1}^{t}=\operatorname{poly}(n)$ and
$\mathcal{H}^{t}$ holds, then $\Delta\Gamma_{2}^{t+1}$ is small.

######  Lemma 4.6.

Consider any process satisfying the conditions in Lemma 4.2 and any step
$t\geqslant 0$, such that $\Gamma_{1}^{t}\leqslant 2\widetilde{c}n^{26}$ and
$\mathcal{H}^{t}$ holds. Then, we have that

$\displaystyle(i)$ $\displaystyle\qquad\Gamma_{2}^{t}\leqslant n^{5/4},$
$\displaystyle(ii)$
$\displaystyle\qquad|\Gamma_{2}^{t+1}-\Gamma_{2}^{t}|\leqslant
n^{1/4}\cdot\sqrt{\frac{n}{b}\cdot\log n}.$ Further, let $\widehat{x}^{t}$ be
the load vector obtained by moving any ball of the load vector $x^{t}$ to some
other bin, then $\displaystyle(iii)$
$\displaystyle\qquad\Gamma_{1}^{t}(\widehat{x}^{t})\leqslant
2\cdot\Gamma_{1}^{t}(x^{t}).$

###### Proof.

Recall that $\gamma_{1}:=\frac{\delta}{40S}\cdot\sqrt{n/(b\log n)}$ and
$\gamma_{2}:=\frac{\gamma_{1}}{8\cdot 30}$. Consider any step $t\geqslant 0$,
such that $\Gamma_{1}^{t}\leqslant 2\widetilde{c}n^{26}$ and $\mathcal{H}^{t}$
holds. We start by bounding the load of any bin $i\in[n]$,

$\displaystyle\Gamma_{1}^{t}\leqslant 2\widetilde{c}n^{26}$
$\displaystyle\Rightarrow e^{\gamma_{1}\cdot y_{i}^{t}}+e^{-\gamma_{1}\cdot
y_{i}^{t}}\leqslant\widetilde{c}n^{26}\Rightarrow
y_{i}^{t}\leqslant\frac{27}{\gamma_{1}}\log
n\,\wedge\,-y_{i}^{t}\leqslant\frac{27}{\gamma_{1}}\log n,$ (4.1)

where in the second implication we used
$\log(2\widetilde{c})+\frac{26}{\gamma_{1}}\log
n\leqslant\frac{27}{\gamma_{1}}\log n$, for sufficiently large $n$.

First statement. Using 4.1, we bound the contribution of any bin $i\in[n]$ to
$\Gamma_{2}^{t}$ as follows,

$\Gamma_{2i}^{t}=e^{\gamma_{2}y_{i}^{t}}+e^{-\gamma_{2}y_{i}^{t}}\leqslant
2\cdot e^{\gamma_{2}\cdot\frac{27}{\gamma_{1}}\log n}\leqslant 2n^{1/8},$
(4.2)

using that $\gamma_{2}:=\frac{\gamma_{1}}{8\cdot 30}$. By aggregating, we get
the first claim $\Gamma_{1}^{t}=\sum_{i=1}^{n}\Gamma_{1i}^{t}\leqslant 2\cdot
n\cdot n^{1/8}\leqslant n^{5/4}$.

Second statement. Let bin $j\in[n]$ be the bin where the $j$-th ball was
allocated. We consider the following cases for the contribution of a bin $i$
to $\Gamma_{2i}^{t}$:

Case 1 [$i=j$ and $y_{j}^{t}\geqslant 0$]: Since $j\in[n]$ is overloaded, we
have that

$\displaystyle\left|\Delta\Gamma_{2j}^{t+1}\right|$
$\displaystyle\leqslant\Gamma_{2j}^{t}\cdot
e^{\gamma_{2}\cdot\frac{15}{\zeta}\cdot\log
n}-\Gamma_{2j}^{t}\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Gamma_{2j}^{t}\cdot\Big{(}1+\gamma_{2}\cdot\frac{30}{\zeta}\cdot\log
n\Big{)}-\Gamma_{2j}^{t}$
$\displaystyle=\Gamma_{2j}^{t}\cdot\gamma_{2}\cdot\frac{30}{\zeta}\cdot\log
n\stackrel{{\scriptstyle(b)}}{{\leqslant}}n^{1/8}\cdot\sqrt{\frac{n}{b}\cdot\log
n},$

using in $(a)$ the Taylor estimate $e^{v}\leqslant 1+2v$ (for $v\leqslant 1$)
and that $\gamma_{2}\cdot\frac{15}{\zeta}\cdot\log n\leqslant 1$, since
$\gamma_{2}\leqslant\frac{\delta}{60S}\cdot\sqrt{\frac{n}{b\log n}}$ and
$S\geqslant\frac{1}{\zeta}$ and in $(b)$ that 4.2,
$\gamma_{2}\leqslant\frac{\delta}{60S}\cdot\sqrt{\frac{n}{b\log n}}$ and
$S\geqslant\frac{1}{\zeta}$.

Case 2 [$i=j$ and $y_{j}^{t}<0$]: Similarly, if $j$ is underloaded, we have
that

$\displaystyle\left|\Delta\Gamma_{2j}^{t+1}\right|$
$\displaystyle\leqslant\Gamma_{2j}^{t}-\Gamma_{2j}^{t}\cdot
e^{-\gamma_{2}\cdot\frac{15}{\zeta}\cdot\log
n}\leqslant\Gamma_{2j}^{t}-\Gamma_{2j}^{t}\cdot\Big{(}1-\gamma_{2}\cdot\frac{30}{\zeta}\cdot\log
n\Big{)}$
$\displaystyle=\Gamma_{2j}^{t}\cdot\gamma_{2}\cdot\frac{30}{\zeta}\cdot\log
n\leqslant n^{1/8}\cdot\sqrt{\frac{n}{b}\cdot\log n}.$

Case 3 [$i\neq j$ and $y_{i}^{t}\geqslant 0$]: The contribution of the rest of
the bins is due to the change in the average load. More specifically, for any
overloaded bin $i\in[n]\setminus\\{j\\}$,

$\displaystyle\left|\Delta\Gamma_{2i}^{t+1}\right|$
$\displaystyle\leqslant\Gamma_{2i}^{t}\cdot
e^{\gamma_{2}\cdot\frac{15}{\zeta}\cdot\frac{\log
n}{n}}-\Gamma_{2i}^{t}\leqslant\Gamma_{2i}^{t}\cdot\left(1+2\cdot\gamma_{2}\cdot\frac{15}{\zeta}\cdot\frac{\log
n}{n}\right)-\Gamma_{2i}^{t}$
$\displaystyle=\Gamma_{2i}^{t}\cdot\gamma_{2}\cdot\frac{30}{\zeta}\cdot\frac{\log
n}{n}\leqslant\sqrt{\frac{\log n}{bn}}\cdot n^{1/8}.$

Case 4 [$i\neq j$ and $y_{i}^{t}<0$]: Similarly, for any underloaded bin
$i\in[n]\setminus\\{j\\}$,

$\displaystyle\left|\Delta\Gamma_{2i}^{t+1}\right|$
$\displaystyle\leqslant\Gamma_{2i}^{t}-\Gamma_{2i}^{t}\cdot
e^{-\gamma_{2}\cdot\frac{15}{\zeta}\cdot\frac{\log n}{n}}$
$\displaystyle\leqslant\Gamma_{2i}^{t}-\Gamma_{2i}^{t}\cdot\left(1-2\cdot\gamma_{2}\cdot\frac{15}{\zeta}\cdot\frac{\log
n}{n}\right)$
$\displaystyle=\Gamma_{2i}^{t}\cdot\gamma_{2}\cdot\frac{30}{\zeta}\cdot\frac{\log
n}{n}\leqslant\sqrt{\frac{\log n}{bn}}\cdot n^{1/8}.$

Hence, aggregating over all bins

$\displaystyle\left|\Delta\Gamma_{2}^{t+1}\right|$
$\displaystyle\leqslant\left|\Delta\Gamma_{2j}^{t+1}\right|+\sum_{i\in[n]\setminus\\{j\\}}\left|\Delta\Gamma_{2i}^{t+1}\right|\leqslant
n^{1/8}\cdot\sqrt{\frac{n}{b}\cdot\log n}+n\cdot\sqrt{\frac{\log n}{bn}}\cdot
n^{1/8}\leqslant n^{1/4}\cdot\sqrt{\frac{n}{b}\cdot\log n},$

for sufficiently large $n$.

Third statement. Let $i,j\in[n]$ be the differing bins between $x^{t}$ and
$\widehat{x}^{t}$. Then since $\mathcal{H}^{t}$ holds, it follows that
$w^{t}\leqslant\frac{15}{\zeta}\cdot\log n$, so for bin $i$,

$\Gamma_{1i}^{t}(\widehat{x}^{t})\leqslant
e^{\gamma_{1}w^{t}}\cdot\Gamma_{1i}^{t}(x^{t})\leqslant
2\cdot\Gamma_{1i}^{t}(x^{t}),$

since $\gamma_{1}\leqslant\frac{1}{40\cdot S\cdot\log n}$ and $S>1/\zeta$.
Similarly, for bin $j$.

$\Gamma_{1j}^{t}(\widehat{x}^{t})\leqslant
e^{\gamma_{1}w^{t}}\cdot\Gamma_{1j}^{t}(x^{t})\leqslant
2\cdot\Gamma_{1j}^{t}(x^{t}),$

Hence,

$\Gamma_{1}^{t}(\widehat{x}^{t})=\sum_{k=1}^{n}\Gamma_{1k}^{t}(\widehat{x}^{t})\leqslant\sum_{k=1}^{n}2\cdot\Gamma_{1k}^{t}(x^{t})=2\cdot\Gamma_{1}^{t}(x^{t}).\qed$

Next, we will show that $\mathbf{E}[\,\Gamma_{2}\,]=\mathcal{O}(n)$ and that
when $\Gamma_{2}$ is sufficiently large, it drops in expectation over the next
batch.

######  Lemma 4.7.

Consider any process satisfying the conditions in Lemma 4.2. Then, there
exists a constant $\widetilde{c}:=\widetilde{c}(\delta)$ such that for any
step $t\geqslant 0$ being a multiple of $b$,

$(i)\quad\mathbf{E}[\,\Gamma_{1}^{t}\,]\leqslant\frac{\widetilde{c}}{2}\cdot
n,\quad\text{ and
}\quad(ii)\quad\mathbf{E}[\,\Gamma_{2}^{t}\,]\leqslant\frac{\widetilde{c}}{2}\cdot
n.$

Further,

$(iii)\quad\mathbf{E}\left[\,\Gamma_{2}^{t+b}\,\,\Big{|}\,\,\mathfrak{F}^{t},\Gamma_{2}^{t}\geqslant\widetilde{c}n\,\right]\leqslant\Gamma_{2}^{t}\cdot\Big{(}1-\frac{1}{\log
n}\Big{)},$

and

$(iv)\quad\mathbf{E}\left[\,\Gamma_{2}^{t+b}\,\,\Big{|}\,\,\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n\,\right]\leqslant\widetilde{c}n-\frac{n}{\log^{2}n}.$

###### Proof.

First/Second statement. Recall that $C=1+\varepsilon$ and
$\varepsilon=\sqrt{\frac{n}{b}\cdot\log n}$. By Lemma 3.4 with
$K:=5\cdot(C-1)^{2}\cdot\frac{b}{n}$, $R:=b$ and
$\gamma_{1}:=\frac{\delta}{40S}\cdot\sqrt{\frac{n}{b\log n}}$, the
preconditions for $\Phi:=\Phi(\gamma_{1})$ and $\Psi:=\Psi(\gamma_{1})$ in 3.3
are satisfied. To apply 3.3 we just need to verify $(i)$ that
$\gamma_{1}\leqslant\frac{\varepsilon\delta}{8K}\leqslant 1$, which holds
since

$\frac{\delta}{40S}\cdot\sqrt{\frac{n}{b\log
n}}\leqslant\frac{\delta}{40}\cdot\sqrt{\frac{n}{b\log
n}}=\frac{\varepsilon\delta}{8K}\leqslant 1$

and $(ii)$ that $b\geqslant\frac{2CS}{(C-1)^{2}}\cdot n$, which follows since

$\frac{2CS}{(C-1)^{2}}\cdot n=2CS\cdot\frac{b}{\log n}\leqslant b.$

Hence, by 3.3 we get the conclusion by setting $\widetilde{c}:=16c/\delta$,
for some constant $c:=c(\delta)>0$.

Similarly for the potential $\Gamma_{2}:=\Gamma_{2}(\gamma_{2})$ since
$\gamma_{2}\leqslant\gamma_{1}$.

Third statement. Furthermore, by Lemma 3.4 and 3.3, we also get that for any
$t\geqslant 0$,

$\mathbf{E}\left[\,\left.\Gamma_{2}^{t+b}\,\,\right|\,\,\mathfrak{F}^{t}\,\right]\leqslant\Gamma_{2}^{t}\cdot\Big{(}1-b\cdot\frac{\varepsilon\delta}{8n}\cdot\gamma_{2}\Big{)}+b\cdot
c\gamma_{2}\varepsilon.$ (4.3)

We define the constant

$\displaystyle\widetilde{c}_{1}$ $\displaystyle:=\frac{1}{2}\cdot
b\cdot\frac{\varepsilon\delta}{8n}\cdot\gamma_{2}=b\cdot\frac{\delta^{2}}{16\cdot
8\cdot 30\cdot 40S\cdot n}\cdot\sqrt{\frac{n}{b\log n}}\cdot\sqrt{\frac{n\log
n}{b}}$ $\displaystyle=\frac{\delta^{2}}{16\cdot 8\cdot 30\cdot 40\cdot S}.$

When $\big{\\{}\Gamma_{2}^{t}\geqslant\widetilde{c}n\big{\\}}$ holds, then 4.3
yields,

$\displaystyle\mathbf{E}\left[\,\Gamma_{2}^{t+b}\,\Big{|}\,\mathfrak{F}^{t},\Gamma_{2}^{t}\geqslant\widetilde{c}n\,\right]$
$\displaystyle\leqslant\Gamma_{2}^{t}\cdot\Big{(}1-2\cdot\widetilde{c}_{1}\Big{)}+b\cdot
c\gamma_{2}\varepsilon$
$\displaystyle=\Gamma_{2}^{t}-\widetilde{c}_{1}\cdot\Gamma_{2}^{t}+\Big{(}b\cdot
c\gamma_{2}\varepsilon-\widetilde{c}_{1}\cdot\Gamma_{2}^{t}\Big{)}$
$\displaystyle\leqslant\Gamma_{2}^{t}-\widetilde{c}_{1}\cdot\Gamma_{2}^{t}+\Big{(}b\cdot
c\gamma_{2}\varepsilon-\frac{1}{2}\cdot
b\cdot\frac{\varepsilon\delta}{8n}\cdot\gamma_{2}\cdot\frac{16c}{\delta}\cdot
n\Big{)}$ $\displaystyle\leqslant\Gamma_{2}^{t}\cdot\Big{(}1-\frac{1}{\log
n}\Big{)}.$

Fourth statement. Similarly, when $\Gamma_{1}^{t}<\widetilde{c}n$, 4.3 yields,

$\displaystyle\mathbf{E}\left[\,\Gamma_{2}^{t+b}\,\Big{|}\,\mathfrak{F}^{t},\Gamma_{2}^{t}<\widetilde{c}n\,\right]$
$\displaystyle\leqslant\widetilde{c}n\cdot\Big{(}1-2\cdot\widetilde{c}_{1}\Big{)}+b\cdot
c\gamma_{2}\varepsilon$
$\displaystyle=\widetilde{c}n-\widetilde{c}\cdot\widetilde{c}_{1}\cdot
n+\Big{(}b\cdot
c\gamma_{2}\varepsilon-\widetilde{c}\cdot\widetilde{c}_{1}\cdot n\Big{)}$
$\displaystyle=\widetilde{c}n-\frac{\widetilde{c}}{\log n}\cdot
n\leqslant\widetilde{c}n-\frac{n}{\log^{2}n}.\qed$

In the next lemma, we show that w.h.p. $\Gamma_{1}$ is
$\operatorname{poly}(n)$ for every step in an interval of length
$2b\log^{3}n$.

######  Lemma 4.8.

Let $\widetilde{c}:=2\cdot\frac{8c}{\delta}$ be the constant defined in Lemma
4.7. For any $b\in[2n\log n,n^{3}]$ and for any step $t\geqslant 0$ being a
multiple of $b$,

$\mathbf{Pr}\left[\,\bigcap_{s\in[t,t+2b\log^{3}n]}\left\\{\Gamma_{1}^{s}\leqslant\widetilde{c}n^{26}\right\\}\,\right]\geqslant
1-n^{-10}.$

###### Proof.

We will start by bounding $\Gamma_{1}^{s}$ at steps $s$ being a multiple of
$b$. Using Lemma 4.7 $(i)$, Markov’s inequality and the union bound over
$2\log^{3}n+1$ steps, we have for any $t\geqslant 0$,

$\mathbf{Pr}\left[\,\bigcap_{s\in[0,2\log^{3}n]}\left\\{\Gamma_{1}^{t+s\cdot
b}\leqslant\widetilde{c}n^{12}\right\\}\,\right]\geqslant 1-(4\log^{3}n)\cdot
n^{-11}.$ (4.4)

Now, assuming that $\Gamma_{1}^{t+s\cdot b}\leqslant\widetilde{c}n^{12}$, we
will upper bound $\Gamma_{1}$ for the steps in between, i.e., for
$\Gamma_{1}^{t+s\cdot b+r}$ for any $r\in[0,b)$. To this end, recalling that
$\Gamma_{1i}^{t+s\cdot b+r}:=\Phi_{1i}^{t+s\cdot b+r}+\Psi_{1i}^{t+s\cdot
b+r}$, we will upper bound for each bin $i\in[n]$ the terms
$\Phi_{1i}^{t+s\cdot b+r}$ and $\Psi_{1i}^{t+s\cdot b+r}$ separately.
Proceeding using 3.5 in Lemma 3.4 (since $\gamma_{1}\leqslant 1$ and $p$
satisfies condition $\mathcal{C}_{3}$),

$\displaystyle\mathbf{E}\left[\,\left.\Phi_{1i}^{t+s\cdot
b+r}\,\right|\,\mathfrak{F}^{t+s\cdot b},\Phi_{1i}^{t+s\cdot b}\,\right]$
$\displaystyle\leqslant\Phi_{1i}^{t+s\cdot
b}\cdot\left(1+\left(p_{i}-\frac{1}{n}\right)\cdot\gamma_{1}+2\cdot p_{i}\cdot
S\gamma_{1}^{2}\right)^{r}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Phi_{1i}^{t+s\cdot
b}\cdot\left(1+\frac{C-1}{n}\cdot\gamma_{1}+2\cdot\frac{C}{n}\cdot
S\gamma_{1}^{2}\right)^{r}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\Phi_{1i}^{t+s\cdot
b}\cdot\left(1+2\cdot\frac{C-1}{n}\cdot\gamma_{1}\right)^{r}$
$\displaystyle\leqslant\Phi_{1i}^{t+s\cdot b}\cdot
e^{2\gamma_{1}(C-1)\cdot\frac{r}{n}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}2\cdot\Phi_{1i}^{t+s\cdot
b},$

using in $(a)$ that $p_{i}-\frac{1}{n}\leqslant\frac{C-1}{n}$ by condition
$\mathcal{C}_{3}$, $(b)$ that $\gamma_{1}\leqslant\frac{C-1}{2CS}$ (as in 3.4)
and in $(c)$ that
$\gamma_{1}\leqslant\frac{\delta}{40}\cdot\sqrt{\frac{n}{b\log n}}$ and
$C-1=\sqrt{\frac{n\log n}{b}}$. Similarly, using 3.9 in Lemma 3.4,

$\displaystyle\mathbf{E}\left[\,\left.\Psi_{1i}^{t+s\cdot
b+r}\,\right|\,\mathfrak{F}^{t+s\cdot b},\Psi_{1i}^{t+s\cdot b}\,\right]$
$\displaystyle\leqslant\Psi_{1i}^{t+s\cdot
b}\cdot\left(1+\left(\frac{1}{n}-p_{i}\right)\cdot\gamma_{1}+2\cdot p_{i}\cdot
S\gamma_{1}^{2}\right)^{r}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Psi_{1i}^{t+s\cdot
b}\cdot\left(1+\frac{C-1}{n}\cdot\gamma_{1}+2\cdot\frac{C}{\gamma_{1}}\cdot
S\gamma_{1}^{2}\right)^{r}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\Psi_{1i}^{t+s\cdot
b}\cdot\left(1+2\cdot\frac{C-1}{n}\cdot\gamma_{1}\right)^{r}$
$\displaystyle\leqslant\Psi_{1i}^{t+s\cdot b}\cdot
e^{2\gamma(C-1)\cdot\frac{r}{n}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}2\cdot\Psi_{1i}^{t+s\cdot
b},$

using in $(a)$ that $\frac{1}{n}-p_{i}\leqslant\frac{C-1}{n}$ by condition
$\mathcal{C}_{3}$, $(b)$ that $\gamma_{1}\leqslant\frac{C-1}{2CS}$ and in
$(c)$ that $\gamma_{1}\leqslant\frac{\delta}{40}\cdot\sqrt{\frac{n}{b\log n}}$
and $C-1=\sqrt{\frac{n\log n}{b}}$. Hence, combining and aggregating over the
bins,

$\mathbf{E}\left[\,\left.\Gamma_{1}^{t+s\cdot
b+r}\,\right|\,\mathfrak{F}^{t+s\cdot b},\Gamma_{1}^{t+s\cdot
b}\,\right]\leqslant 2\cdot\Gamma_{1}^{t+s\cdot b}.$

Applying Markov’s inequality, for any $r\in[0,b)$,

$\mathbf{Pr}\left[\,\Gamma_{1}^{t+s\cdot b+r}\leqslant
n^{14}\cdot\Gamma_{1}^{t+s\cdot b}\,\right]\geqslant 1-2n^{-14}.$

Hence, by a union bound over the $2b\log^{3}n\leqslant 2n^{3}\log^{3}n$
possible steps (since $b\leqslant n^{3}$) for $s\in[0,2\log^{3}n]$ and
$r\in[0,b)$,

$\displaystyle\mathbf{Pr}\left[\,\bigcap_{r\in[0,b]}\bigcap_{s\in[0,2\log^{3}n]}\left\\{\Gamma_{1}^{t+s\cdot
b+r}\leqslant n^{14}\cdot\Gamma_{1}^{t+s\cdot b}\right\\}\,\right]\geqslant
1-2n^{-14}\cdot 2b\log^{3}n\geqslant 1-\frac{1}{2}n^{-10}.$ (4.5)

Finally, taking the union bound of 4.4 and 4.5, we conclude

$\displaystyle\mathbf{Pr}\left[\,\bigcap_{s\in[t,t+2b\log^{3}n]}\left\\{\Gamma_{1}^{s}\leqslant\widetilde{c}n^{26}\right\\}\,\right]$
$\displaystyle\geqslant\Pr\Bigg{[}\bigcap_{r\in[0,b]}\bigcap_{s\in[0,2\log^{3}n]}\left\\{\Gamma_{1}^{t+s\cdot
b+r}\leqslant n^{14}\cdot\Gamma_{1}^{t+s\cdot b}\right\\}$
$\displaystyle\qquad\qquad\cap\bigcap_{s\in[0,2\log^{3}n]}\left\\{\Gamma_{1}^{t+s\cdot
b}\leqslant\widetilde{c}n^{12}\right\\}\Bigg{]}$ $\displaystyle\geqslant
1-\frac{1}{2}n^{-10}-(4\log^{3}n)\cdot n^{-11}\geqslant 1-n^{-10}.\qed$

We will now show that w.h.p. there is a step every $b\log^{3}n$ steps, such
that the exponential potential $\Gamma_{2}$ becomes $\mathcal{O}(n)$. We call
this the recovery phase.

######  Lemma 4.9 (Recovery).

Consider any process satisfying the conditions in Lemma 4.2. Let
$\widetilde{c}:=2\cdot\frac{8c}{\delta}$ be the constant defined in Lemma 4.7.
For any step $t\geqslant 0$ being a multiple of $b$,

$\mathbf{Pr}\left[\,\bigcup_{s\in[0,\log^{3}n]}\left\\{\Gamma_{2}^{t+s\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]\geqslant 1-2n^{-8}.$

###### Proof.

By Lemma 4.7 $(ii)$, using Markov’s inequality at step $t$ being a multiple of
$b$, we have

$\mathbf{Pr}\left[\,\Gamma_{2}^{t}\leqslant\widetilde{c}n^{9}\,\right]\geqslant
1-n^{-8}.$ (4.6)

We will be assuming $\Gamma_{2}^{t}\leqslant\widetilde{c}n^{9}$. By Lemma 4.7
$(iii)$, for any step $r\geqslant 0$, then

$\mathbf{E}\left[\,\left.\Gamma_{2}^{r+1}\,\right|\,\mathfrak{F}^{r},\Gamma_{2}^{r}>\widetilde{c}n\,\right]\leqslant\Gamma_{2}^{r}\cdot\Big{(}1-\frac{1}{\log
n}\Big{)}.$

In order to prove that $\Gamma_{2}^{t+s\cdot b}$ is small for some
$s\in[0,b\log^{3}n]$, we define the “killed” potential function for any
$r\in[0,\log^{3}n]$,

$\widehat{\Gamma}_{2}^{t+r\cdot b}:=\Gamma_{2}^{t+r\cdot
b}\cdot\mathbf{1}_{\bigcap_{s\in[0,r]}\\{\Gamma_{2}^{t+s\cdot
b}>\widetilde{c}n\\}}.$

Note that $\widehat{\Gamma}_{2}^{t+r\cdot b}\leqslant\Gamma_{2}^{t+r\cdot b}$
and that $\big{\\{}\widehat{\Gamma}_{2}^{t+r\cdot b}=0\big{\\}}$ implies that
$\big{\\{}\widehat{\Gamma}_{2}^{t+r\cdot b+1}=0\big{\\}}$. Hence, the
$\widehat{\Gamma}$ potential satisfies unconditionally the drop inequality of
Lemma 4.7 $(iii)$, that is,

$\mathbf{E}\left[\,\left.\widehat{\Gamma}_{2}^{t+(r+1)\cdot
b}\,\right|\,\mathfrak{F}^{t+r\cdot b},\widehat{\Gamma}_{2}^{t+r\cdot
b}\,\right]\leqslant\widehat{\Gamma}_{2}^{t+r\cdot
b}\cdot\Big{(}1-\frac{1}{\log n}\Big{)}.$

Inductively applying this for $\log^{3}n$ batches and using that
$\widehat{\Gamma}_{2}^{t}\leqslant\Gamma_{2}^{t}\leqslant\widetilde{c}n^{9}$,

$\mathbf{E}\left[\,\left.\widehat{\Gamma}_{2}^{t+(\log^{3}n)\cdot
b}\,\,\right|\,\,\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n^{9}\,\right]\leqslant\Gamma_{2}^{t}\cdot\Big{(}1-\frac{1}{\log
n}\Big{)}^{\log^{3}n}\leqslant\widetilde{c}n^{9}\cdot e^{-\log^{2}n}<n^{-7}.$

So by Markov’s inequality,

$\mathbf{Pr}\left[\,\left.\widehat{\Gamma}_{2}^{t+(\log^{3}n)\cdot
b}<n\,\,\right|\,\,\Gamma_{2}^{t}\leqslant\widetilde{c}n^{9}\,\right]\geqslant
1-n^{-{8}}$

By combining with 4.6,

$\displaystyle\mathbf{Pr}\left[\,\widehat{\Gamma}_{2}^{t+(\log^{3}n)\cdot
b}<n\,\right]$
$\displaystyle\geqslant\left(1-n^{-8}\right)\cdot\left(1-n^{-8}\right)\geqslant
1-2n^{-8}.$

Due to the definition of $\Gamma_{2}$, at any step $t\geqslant 0$,
deterministically $\Gamma_{2}^{t}\geqslant 2n$. So, we conclude that w.p. at
least $1-2n^{-8}$, we have that $\widehat{\Gamma}_{2}^{t+(\log^{3}n)\cdot
b}=0$ or equivalently the event

$\neg\bigcap_{s\in[0,\log^{3}n]}\left\\{\Gamma_{2}^{t+s\cdot
b}>\widetilde{c}n\right\\},$

holds, which implies the conclusion. ∎

####  4.1.2 Completing the Proof of Lemma 4.2

We are now ready to prove Lemma 4.2, using a method of bounded differences
with a bad event A.6 ([20, Theorem 3.3]).

###### Proof of Lemma 4.2.

Our starting point is to apply Lemma 4.9, which proves that there is at least
one step $t+\rho\cdot b\in[t-b\log^{3}n,t]$ with $\rho\in[-\log^{3}n,0]$ such
that the potential $\Gamma_{2}$ is small,

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{\rho\in[-\log^{3}n,0]}\left\\{\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]$ $\displaystyle\geqslant
1-2n^{-8}.$ (4.7)

Note that if $t<b\log^{3}n$, then deterministically
$\Gamma_{2}^{0}=2n\leqslant\widetilde{c}n$ (which corresponds to $\rho=-t/b$).

We are now going to apply the concentration inequality A.6 to each of the
batches starting at $t+\rho\cdot b,\ldots,t+(\log^{3}n)\cdot b$ and show that
the potential remains $\leqslant\widetilde{c}n$ at the last step of each
batch. More specifically, we will show that for any
$\widetilde{r}\in[\rho,\log^{3}n]$, for $r=t+b\cdot\widetilde{r}$,

$\mathbf{Pr}\left[\,\left.\Gamma_{2}^{r+b}>\widetilde{c}n\,\right|\,\mathfrak{F}^{r},\Gamma_{2}^{r}\leqslant\widetilde{c}n\,\right]\leqslant
3n^{-4}.$

We will show this by applying A.6 for all steps of the batch $[r,r+b]$. We
define the good event

$\mathcal{G}_{r}:=\mathcal{G}_{r}^{r+b}:=\bigcap_{s\in[r,r+b]}\left(\left\\{\Gamma_{1}^{s}\leqslant\widetilde{c}n^{26}\right\\}\cap\mathcal{H}^{s}\right),$

and the bad event $\mathcal{B}_{r}:=(\mathcal{G}_{r})^{c}$. Using a union
bound over Lemma 4.5 and Lemma 4.8,

$\displaystyle\mathbf{Pr}\left[\,\bigcap_{s\in[t-b\log^{3}n,t+b\log^{3}n]}\left(\left\\{\Gamma_{1}^{s}\leqslant\widetilde{c}n^{26}\right\\}\cap\mathcal{H}^{s}\right)\,\right]\geqslant
1-2n^{-10}.$ (4.8)

Consider any $u\in[r,r+b]$. Further, we define the slightly weaker good event,
$\widetilde{\mathcal{G}}_{r}^{u}:=\bigcap_{s\in[r,u]}\left(\left\\{\Gamma_{1}^{s}\leqslant
2\widetilde{c}n^{26}\right\\}\cap\mathcal{H}^{s}\right)$ and the “killed”
potential,

$\widehat{\Gamma}_{r}^{u}:=\Gamma_{2}^{u}\cdot\mathbf{1}_{\widetilde{\mathcal{G}}_{r}^{u}}.$

We will show that the sequence
$\widehat{\Gamma}_{r}^{r},\ldots,\widehat{\Gamma}_{r}^{r+b}$ is strongly
difference-bounded by $(n^{5/4},n^{1/4}\cdot\sqrt{(n/b)\cdot\log n},2n^{-10})$
(A.5).

Let $\omega\in[n]^{b}$ be an allocation vector encoding the allocations made
in $[r,r+b]$. Let $\omega^{\prime}$ be an allocating vector resulting from
$\omega$ by changing one arbitrary allocation. It follows that,

$\displaystyle\left|\widehat{\Gamma}_{r}^{r+b}(\omega)-\widehat{\Gamma}_{r}^{r+b}(\omega^{\prime})\right|$
$\displaystyle\leqslant\max_{\widetilde{\omega}}\widehat{\Gamma}_{r}^{r+b}(\widetilde{\omega})-\min_{\widetilde{\omega}}\widehat{\Gamma}_{r}^{r+b}(\widetilde{\omega})$
$\displaystyle\leqslant\max_{\widetilde{\omega}\in\widetilde{\mathcal{G}}_{r}^{r+b}}\Gamma_{2}^{r+b}(\widetilde{\omega})-0$
$\displaystyle\leqslant n^{5/4},$

where in the last inequality we used Lemma 4.6 $(i)$ that for any
$\widetilde{\omega}\in\widetilde{\mathcal{G}}_{r}^{r+b}$, we have
$\widehat{\Gamma}_{r}^{r+b}(\widetilde{\omega})\leqslant\Gamma_{2}^{r+b}(\widetilde{\omega})\leqslant
n^{5/4}$.

We will now derive a refined bound by additionally assuming that
$\omega\in\mathcal{G}_{r}$. Then, for any $u\in[r,r+b]$,

$\Gamma_{1}^{u}(\omega^{\prime})\leqslant
2\cdot\Gamma_{1}^{u}(\omega)\leqslant 2\widetilde{c}n^{26},$

where the first inequality is by Lemma 4.6 $(iii)$. Hence
$\omega^{\prime}\in\widetilde{\mathcal{G}}_{r}^{r+b}$, so
$\mathbf{1}_{\widetilde{\mathcal{G}}_{r}^{r+b}(\omega^{\prime})}=1$ and
$\widehat{\Gamma}_{r}^{r+b}(\omega^{\prime})=\Gamma_{2}^{r+b}(\omega^{\prime})$.
Similarly, for
$\omega\in\mathcal{G}_{r}\subseteq\widetilde{\mathcal{G}}_{r}^{r+b}$, we have
$\widehat{\Gamma}_{r}^{r+b}(\omega)=\Gamma_{2}^{r+b}(\omega)$ and by Lemma 4.6
$(ii)$,

$\left|\widehat{\Gamma}_{r}^{r+b}(\omega)-\widehat{\Gamma}_{r}^{r+b}(\omega^{\prime})\right|=\left|\Gamma_{2}^{r+b}(\omega)-\Gamma_{2}^{r+b}(\omega^{\prime})\right|\leqslant
n^{1/4}\cdot\sqrt{\frac{n}{b}\cdot\log n}.$

Within a single batch all allocations are independent, so we apply A.6,
choosing $\gamma_{k}:=\frac{1}{b}$ and $N:=b$, which states that for any $T>0$
and
$\mu:=\mathbf{E}\left[\,\left.\widehat{\Gamma}_{r}^{r+b}>\mu+T\,\right|\,\mathfrak{F}^{r},\Gamma_{2}^{r}\leqslant\widetilde{c}n\,\right]$,

$\displaystyle\mathbf{Pr}\left[\,\left.\widehat{\Gamma}_{r}^{r+b}>\mu+T\,\right|\,\mathfrak{F}^{r},\Gamma_{2}^{r}\leqslant\widetilde{c}n\,\right]$
$\displaystyle\quad\leqslant\exp\left(-\frac{T^{2}}{2\cdot\sum_{k=1}^{b}(n^{1/4}\cdot\sqrt{\frac{n}{b}\cdot\log
n}+n^{5/4}\cdot\frac{1}{b})^{2}}\right)+2n^{-10}\cdot\sum_{k=1}^{b}b.$

By Lemma 4.7 $(iv)$, we have
$\mu\leqslant\mathbf{E}[\,\widehat{\Gamma}_{r}^{r+b}\mid\Gamma_{2}^{r}<\widetilde{c}n\,]\leqslant\mathbf{E}[\,\Gamma_{2}^{r+b}\mid\Gamma_{2}^{r}<\widetilde{c}n\,]\leqslant\widetilde{c}n-n/\log^{2}n$.
Hence, for $T:=n/\log^{2}n$, since $2n\log n\leqslant b\leqslant n^{3}$, we
have

$\displaystyle\mathbf{Pr}\left[\,\left.\widehat{\Gamma}_{r}^{r+b}>\widetilde{c}n\,\right|\,\mathfrak{F}^{r},\Gamma_{2}^{r}\leqslant\widetilde{c}n\,\right]$
$\displaystyle\leqslant\exp\left(-\frac{n^{2}/\log^{4}n}{2\cdot b\cdot(2\cdot
n^{1/4}\cdot\sqrt{\frac{n}{b}\cdot\log n})^{2}}\right)+2n^{-10}\cdot b^{2}$
$\displaystyle\leqslant\exp\left(-\frac{n^{1/2}}{8\cdot\log^{5}n}\right)+2n^{-10}\cdot
n^{6}\leqslant 3n^{-4}.$

Let
$\mathcal{K}_{\rho}^{\widetilde{r}}:=\mathcal{G}_{\rho}^{t+\widetilde{r}\cdot
b}\cap\\{\Gamma_{2}^{t+\rho\cdot b}\leqslant\widetilde{c}n\\}$ for
$\widetilde{r}\in[\rho,\log^{3}n]$. For any $\widetilde{r}\geqslant\rho$,
since
$\mathcal{K}_{\rho}^{\widetilde{r}+1}\subseteq\mathcal{K}_{\rho}^{\widetilde{r}}$,
we have

$\displaystyle\mathbf{Pr}\left[\,\left.\widehat{\Gamma}_{r}^{t+(\widetilde{r}+1)\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{r}+1}}>\widetilde{c}n\,\right|\,\mathfrak{F}^{r},\widehat{\Gamma}_{r}^{t+\widetilde{r}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{r}}}\leqslant\widetilde{c}n\,\right]\leqslant
3n^{-4}.$ (4.9)

By union bound of 4.7 and 4.8,

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{\rho\in[-\log^{3}n]}\mathcal{K}_{\rho}^{\log^{3}n}\,\right]$
$\displaystyle\geqslant\mathbf{Pr}\left[\,\mathcal{G}_{-\log^{3}n}^{\log^{3}n}\cap\bigcup_{\rho\in[-\log^{3}n,0]}\left\\{\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]$ $\displaystyle\geqslant
1-2n^{-8}-2n^{-10}\geqslant 1-3n^{-8}.$ (4.10)

Let

$\mathcal{A}:=\bigcap_{\widetilde{r}\in[0,\log^{3}n]}\left\\{\Gamma_{2}^{t+\widetilde{r}\cdot
b}\leqslant\widetilde{c}n\right\\},$

and

$\mathcal{A}_{\rho}:=\bigcap_{\widetilde{r}\in[\rho,\log^{3}n]}\left\\{\widehat{\Gamma}_{r}^{t+\widetilde{r}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{r}}}\leqslant\widetilde{c}n\right\\}.$

Then,

$\displaystyle\mathbf{Pr}\left[\,\mathcal{A}_{\rho}\,\,\left|\,\,\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\right.\,\right]$
$\displaystyle\geqslant\prod_{\widetilde{r}\in[\rho,\log^{3}n-1]}\mathbf{Pr}\left[\bigcap_{\widetilde{s}\in[\rho+1,\widetilde{r}+1]}\left\\{\widehat{\Gamma}_{r}^{t+\widetilde{s}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{s}}}\leqslant\widetilde{c}n\right\\}\right.$
$\displaystyle\qquad\qquad\left.\bigg{|}\,\bigcap_{\widetilde{s}\in[\rho+1,\widetilde{r}-1]}\left\\{\widehat{\Gamma}_{r}^{t+\widetilde{s}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{s}}}\leqslant\widetilde{c}n\right\\},\widehat{\Gamma}_{r}^{t+\widetilde{r}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{s}}}\leqslant\widetilde{c}n\right]$
$\displaystyle\geqslant\prod_{\widetilde{r}\in[\rho,\log^{3}n-1]}\mathbf{Pr}\left[\,\left.\widehat{\Gamma}_{r}^{\widetilde{r}+b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{r}+1}}>\widetilde{c}n\,\right|\,\mathfrak{F}^{t+\widetilde{r}\cdot
b},\widehat{\Gamma}_{r}^{t+\widetilde{r}\cdot
b}\cdot\mathbf{1}_{\mathcal{K}_{\rho}^{\widetilde{r}}}\leqslant\widetilde{c}n\,\right]$
$\displaystyle\geqslant(1-3n^{-4})^{2\log^{3}n}\geqslant
1-6n^{-4}\cdot\log^{3}n,$

where in the last inequality we have used 4.9 and the fact
$\rho\geqslant-\log^{3}n$. So,

$\displaystyle\mathbf{Pr}\left[\,\mathcal{A}_{\rho}\,\right]$
$\displaystyle=\mathbf{Pr}\left[\,\mathcal{A}_{\rho}\,\left|\,\,\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\right.\,\right]\cdot\mathbf{Pr}\left[\,\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\,\right]+1\cdot\mathbf{Pr}\left[\,\neg\left\\{\Gamma_{2}^{t+\rho\cdot
b}\leqslant\widetilde{c}n\right\\}\,\right]$ $\displaystyle\geqslant
1-6n^{-4}\cdot\log^{3}n.$ (4.11)

Note that for any $\rho\in[-\log^{3}n,0]$, we have that
$\mathcal{A}_{\rho}\cap\mathcal{K}_{\rho}^{\log^{3}n}\subseteq\mathcal{A}$.
Hence we conclude by the union bound of 4.10 and 4.11, that

$\displaystyle\mathbf{Pr}\left[\,\mathcal{A}\,\right]$
$\displaystyle\geqslant\mathbf{Pr}\left[\,\bigcup_{\rho\in[-\log^{3}n,0]}\mathcal{K}_{\rho}^{\log^{3}n}\cap\bigcap_{\rho\in[-\log^{3}n,0]}\mathcal{A}_{\rho}\,\right]\geqslant
1-3n^{-8}-6n^{-4}\cdot\log^{6}n\geqslant 1-n^{-3}.\qed$

###  4.2 Step 2: Completing the Proof of Theorem 4.1

We will now show that when $\Gamma_{2}^{t}=\mathcal{O}(n)$, the stronger
potential function $\Lambda^{t}$ drops in expectation over the next batch.
This will allow us to prove that $\Lambda^{m}=\operatorname{poly}(n)$ and
deduce that w.h.p.
$\operatorname{Gap}(m)=\mathcal{O}\big{(}\sqrt{(b/n)\cdot\log n}\big{)}$.

######  Lemma 4.10.

Consider any process satisfying the conditions in 4.1. Let
$\widetilde{c}:=2\cdot\frac{8c}{\delta}$ where $c:=c(\delta)>0$ is the
constant from 3.3. For any step $t\geqslant 0$ being a multiple of $b$,

$\mathbf{E}\left[\,\left.\Lambda^{t+b}\,\right|\,\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n\,\right]\leqslant\Lambda^{t}\cdot
e^{-\frac{\lambda\varepsilon}{2n}\cdot b}+n^{2}.$

###### Proof.

Consider an arbitrary step $t\geqslant 0$ being a multiple of $b$ and consider
a labeling of the bins so that they are sorted by load. Assuming that
$\\{\Gamma_{2}^{t}\leqslant\widetilde{c}n\\}$ holds, the number of bins with
load $y_{i}^{t}\geqslant z$ is at most

$\widetilde{c}n\cdot e^{-\gamma_{2}\cdot z}=\widetilde{c}n\cdot
e^{-\log(\widetilde{c}/\delta)}=\delta n.$

For any bin $i\in[n]$ with $y_{i}^{t}\geqslant z$, we get as in 3.5 (using
that $\lambda\leqslant 1$ and that $p$ satisfies $\mathcal{C}_{3}$ for
$C\in(1,1.9)$),

$\displaystyle\mathbf{E}\left[\,\left.\Lambda_{i}^{t+b}\,\,\right|\,\,\mathfrak{F}^{t}\,\right]$
$\displaystyle\leqslant\Lambda_{i}^{t}\cdot\left(1+\Big{(}p_{i}^{t}-\frac{1}{n}\Big{)}\cdot\lambda+2\cdot
p_{i}^{t}\cdot S\lambda^{2}\right)^{b}.$

Since there are at most $\delta n$ such bins (i.e., $i\leqslant\delta n$), $p$
satisfies condition $\mathcal{C}_{1}$ and the normalized vector $y^{t}$ is
sorted, by Lemma A.2 the upper bound on
$\mathbf{E}\left[\,\Lambda^{t+b}\mid\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n\,\right]$
is maximized when $p_{i}^{t}=\frac{1-\varepsilon}{n}$, so

$\displaystyle\sum_{i:y_{i}^{t}\geqslant
z}\mathbf{E}\left[\,\left.\Lambda_{i}^{t+b}\,\,\right|\,\,\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n\,\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\sum_{i:y_{i}^{t}\geqslant
z}\Lambda_{i}^{t}\cdot\left(1-\frac{\lambda\varepsilon}{n}+2CS\cdot\frac{\lambda^{2}}{n}\right)^{b}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\sum_{i:y_{i}^{t}\geqslant
z}\Lambda_{i}^{t}\cdot\left(1-\frac{\lambda\varepsilon}{2n}\right)^{b}\stackrel{{\scriptstyle(c)}}{{\leqslant}}\sum_{i:y_{i}^{t}\geqslant
z}\Lambda_{i}^{t}\cdot e^{-\frac{\lambda\varepsilon}{2n}\cdot b},$

using in $(a)$ that $p_{i}^{t}\leqslant\frac{C}{n}$, in $(b)$ that
$\lambda=\frac{\varepsilon}{4CS}$ and in $(c)$ that $1+v\leqslant e^{v}$ for
any $v$. For the rest of the bins with $i>\delta n$,

$\displaystyle\mathbf{E}\left[\,\left.\Lambda_{i}^{t+b}\,\right|\,\mathfrak{F}^{t}\,\right]$
$\displaystyle\leqslant\Lambda_{i}^{t}\cdot\left(1+\left(p_{i}^{t}-\frac{1}{n}\right)\cdot\lambda+2\cdot
p_{i}^{t}\cdot S\lambda^{2}\right)^{b}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}\Lambda_{i}^{t}\cdot\left(1+\frac{C-1}{n}\cdot\lambda+2CS\cdot\frac{\lambda^{2}}{n}\right)^{b}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\Lambda_{i}^{t}\cdot\left(1+2\cdot\frac{C-1}{n}\cdot\lambda\right)^{b}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leqslant}}\left(1+2\cdot\frac{C-1}{n}\cdot\lambda\right)^{b}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leqslant}}e^{2\cdot\frac{C-1}{n}\cdot\lambda
b}\stackrel{{\scriptstyle(e)}}{{\leqslant}}n,$

using in $(a)$ that $p_{i}^{t}\leqslant\frac{C}{n}$, in $(b)$ that
$2CS\cdot\frac{\lambda^{2}}{n}=\frac{\varepsilon}{2n}\cdot\lambda\leqslant\frac{C-1}{2n}\cdot\lambda$
since $\lambda=\frac{\varepsilon}{4CS}$ and $\varepsilon=C-1$, in $(c)$ that
$\Lambda_{i}^{t}\leqslant 1$, in $(d)$ that $1+v\leqslant e^{v}$ for any $v$
and in $(e)$ that $2\cdot\frac{C-1}{n}\cdot\lambda
b\leqslant\frac{\varepsilon^{2}}{2CS}\cdot\frac{b}{n}\leqslant\log n$ (since
$C>1$ and $S\geqslant 1$).

Aggregating the contributions over all bins,

$\displaystyle\mathbf{E}\left[\,\left.\Lambda^{t+b}\,\right|\,\mathfrak{F}^{t},\Gamma_{2}^{t}\leqslant\widetilde{c}n\,\right]$
$\displaystyle\leqslant\sum_{i:y_{i}^{t}\geqslant z}\Lambda_{i}^{t}\cdot
e^{-\frac{\lambda\varepsilon}{2n}\cdot
b}+\sum_{i:y_{i}^{t}<z}n\leqslant\Lambda^{t}\cdot
e^{-\frac{\lambda\varepsilon}{2n}\cdot b}+n^{2}.\qed$

Now we are ready to complete the proof of 4.1.

###### Proof of 4.1.

First consider the case when $m\geqslant b\cdot\log^{3}n$. Let
$t_{0}=m-b\cdot\log^{3}n$. Let
$\mathcal{E}^{t}:=\big{\\{}\Gamma_{2}^{t}\leqslant\widetilde{c}n\big{\\}}$.
Then using Lemma 4.2,

$\mathbf{Pr}\left[\,\bigcap_{j\in[0,\log^{3}n]}\mathcal{E}^{t_{0}+j\cdot
b}\,\right]\geqslant 1-n^{-3}.$ (4.12)

We define the killed potential $\widetilde{\Lambda}$, with
$\widetilde{\Lambda}^{t_{0}}:=\Lambda^{t_{0}}$ and for $j>0$,

$\widetilde{\Lambda}^{t_{0}+j\cdot b}:=\Lambda^{t_{0}+j\cdot
b}\cdot\mathbf{1}_{\cap_{s\in[0,j]}\mathcal{E}^{t_{0}+s\cdot b}}.$

Since $\widetilde{\Lambda}^{t}\leqslant\Lambda^{t}$, we have that by Lemma
4.10 for $t=t_{0}+j\cdot b$, we have that

$\displaystyle\mathbf{E}\left[\,\widetilde{\Lambda}^{t_{0}+(j+1)\cdot
b}\,\,\left|\,\,\mathfrak{F}^{t_{0}+j\cdot b},\Gamma_{2}^{t_{0}+j\cdot
b}\leqslant\widetilde{c}n\right.\,\right]\leqslant\widetilde{\Lambda}^{t_{0}+j\cdot
b}\cdot e^{-\frac{\lambda\varepsilon}{2n}\cdot b}+n^{2}.$

When $\mathcal{E}^{t_{0}+j\cdot b}$ does not hold, then deterministically
$\widetilde{\Lambda}^{t_{0}+(j+1)\cdot b}=\widetilde{\Lambda}^{t_{0}+j\cdot
b}=0$. Hence, we have the following unconditional drop inequality

$\displaystyle\mathbf{E}\left[\,\widetilde{\Lambda}^{t_{0}+(j+1)\cdot
b}\,\,\left|\,\,\mathfrak{F}^{t_{0}+j\cdot
b}\right.\,\right]\leqslant\widetilde{\Lambda}^{t_{0}+j\cdot b}\cdot
e^{-\frac{\lambda\varepsilon}{2n}\cdot b}+n^{2}.$ (4.13)

Assuming $\mathcal{E}^{t_{0}}$ holds, we have

$\max_{i\in[n]}y_{i}^{t_{0}}\leqslant\frac{1}{\gamma_{2}}\cdot\left(\log\widetilde{c}+\log
n\right)\leqslant\frac{2}{\gamma_{2}}\cdot\log n,$

for sufficiently large $n$. Recalling that $\gamma_{2}=\Theta(\lambda\cdot\log
n)$, there exists a constant $\kappa_{1}>0$ such that

$\widetilde{\Lambda}^{t_{0}}\leqslant n\cdot e^{\lambda\cdot
y_{1}^{t_{0}}}\leqslant e^{\kappa_{1}\log^{2}n}.$

Applying Lemma A.1 to 4.13 with $a:=e^{-\frac{\lambda\varepsilon}{2n}\cdot b}$
and $b:=n^{2}$ for $\log^{3}n$ steps,

$\displaystyle\mathbf{E}\left[\,\widetilde{\Lambda}^{m}\,\,\left|\,\,\mathfrak{F}^{t_{0}},\widetilde{\Lambda}^{t_{0}}\leqslant
e^{\kappa_{1}\log^{2}n}\right.\,\right]$ $\displaystyle\leqslant
e^{\kappa_{1}\log^{2}n}\cdot
a^{\log^{3}n}+\frac{b}{1-a}\stackrel{{\scriptstyle(a)}}{{\leqslant}}1+1.5\cdot
b\leqslant 2n^{2}.$ (4.14)

using in $(a)$ that $\frac{\lambda\varepsilon}{2n}\cdot b=\Omega(\log n)$,
since $\lambda=\frac{\varepsilon}{4CS}$ and $\varepsilon=\sqrt{(n/b)\cdot\log
n}$.

By Markov’s inequality, we have

$\displaystyle\mathbf{Pr}\left[\,\widetilde{\Lambda}^{m}\leqslant
2n^{5}\,\left|\,\mathfrak{F}^{t_{0}},\widetilde{\Lambda}^{t_{0}}\leqslant
e^{\kappa_{1}\log^{2}n}\right.\,\right]\geqslant 1-n^{-3}.$

Hence, by 4.12,

$\displaystyle\mathbf{Pr}\left[\,\widetilde{\Lambda}^{m}\leqslant
2n^{5}\,\right]$
$\displaystyle=\mathbf{Pr}\left[\,\left.\widetilde{\Lambda}^{m}\leqslant
2n^{5}\,\right|\,\mathcal{E}^{t_{0}}\,\right]\cdot\mathbf{Pr}\left[\,\mathcal{E}^{t_{0}}\,\right]\geqslant\left(1-n^{-3}\right)\cdot\left(1-n^{-3}\right)\geqslant
1-2n^{-3}.$

Combining with 4.12, we have

$\displaystyle\mathbf{Pr}\left[\,\Lambda^{m}\leqslant 2n^{5}\,\right]$
$\displaystyle\geqslant\mathbf{Pr}\left[\,\left\\{\widetilde{\Lambda}^{m}\leqslant
2n^{5}\right\\}\cap\bigcap_{j\in[0,\log^{3}n]}\mathcal{E}^{t_{0}+j\cdot
b}\,\right]\geqslant 1-2n^{-3}-n^{-3}\geqslant 1-n^{-2}.$

Finally, $\\{\Lambda^{m}\leqslant 2n^{5}\\}$ implies that

$\max_{i\in[n]}y_{i}^{m}\leqslant z+\frac{\log 2}{\lambda}+\frac{5\log
n}{\lambda}=\mathcal{O}\left(\sqrt{(b/n)\cdot\log n}\right),$

since $\lambda=\frac{\varepsilon}{4CS}=\Theta(\sqrt{(n\log n)/b})$, so the
claim follows.

For the case when $m<b\cdot\log^{3}n$, it deterministically holds that
$\widetilde{\Lambda}^{t_{0}}\leqslant n$, which is a stronger starting point
in 4.14 to prove that $\mathbf{E}[\,\Lambda^{m}\,]\leqslant 2n^{5}$, which in
turn implies the gap bound. ∎

##  5 Lower Bounds on the Gap

In this section, we prove two lower bounds of $\Omega(\sqrt{(b/n)\cdot\log
n})$ on the gap. Both lower bounds hold even in the unit weights case.

######  Observation 5.1.

Consider the $b$-Batched setting with any $b\geqslant n\log n$, and assume all
balls have unit weights. Then, for any process which uses the same probability
allocation vector within each batch with random tie breaking,

$\mathbf{Pr}\left[\,\operatorname{Gap}(b)\geqslant\frac{1}{10}\cdot\sqrt{(b/n)\cdot\log
n}\,\right]\geqslant 1-n^{-2}.$

###### Proof.

Any such process behaves exactly like One-Choice in the first batch and so the
lower bound follows from that of One-Choice for $b$ balls into $n$ bins (cf.
[35] and [24, Lemma A.2]). ∎

The next lower bound is more involved. This bound also applies to processes
which are allowed to adjust the probability allocation vector from one batch
to another arbitrarily; e.g., the probability for a heavily underloaded bin
might be set close to (or even equal to) $1$, and similarly, the probability
for a heavily overloaded bin might be set close to (or equal to) $0$.
Additionally, the lower bound below applies to any two consecutive batches,
and not only to the end of the first batch as in 5.1.

######  Theorem 5.2.

Consider the $b$-Batched setting with any $b=\Omega(n\log n)$ in the unit
weights case. Furthermore, consider an allocation process which may adaptively
change the probability allocation vector for each batch. Then there is a
constant $\kappa>0$ such that for any allocation process (which may adaptively
change the probability for each batch) it holds that for every $t\geqslant 0$
being a multiple of $b$,

$\mathbf{Pr}\left[\,\max\left\\{\operatorname{Gap}(t),\operatorname{Gap}(t+b)\right\\}\geqslant\kappa\cdot\sqrt{(b/n)\cdot\log
n}\,\right]\geqslant 1/2.$

###### Proof.

In the proof, we shall prove a slightly stronger statement:

$\mathbf{Pr}\left[\,\max\left\\{\operatorname{Gap}(t),\operatorname{Gap}(t+b)\right\\}\geqslant\kappa\cdot\sqrt{(b/n)\cdot\log
n}~{}~{}\Bigg{|}~{}~{}\mathfrak{F}^{t}\,\right]\geqslant 1/2.$

That is, there is no load configuration and no probability allocation vector
(depending on $\mathfrak{F}^{t}$) such that the gap is small, both before and
at the end of an arbitrary batch.

For notational convenience, we will prove this statement by assuming that
$t=0$, and $x^{0}$ is an arbitrary load vector satisfying
$\sum_{i\in[n]}x_{i}^{0}=0$ (in other words, we shift time backwards by $t$
steps) and $p=p^{0}$ is the probability allocation vector used by the process.
Consider one arbitrary bin $j\in[n]$. Then,

$\displaystyle\mathbf{E}\left[\,x_{j}^{b}-\frac{b}{n}+z_{j}\,\right]=b\cdot
p_{j}-\frac{b}{n}+z_{j}=:\varphi_{j}$

For a sufficiently large constant $C>0$, let us now assume
$\max_{j\in[n]}z_{j}\leqslant C/2\cdot\sqrt{(b/n)\cdot\log n}$; clearly, if
this is not the case, we already have a large gap already before the next
batch.

Next consider a bin $j\in[n]$ with

$p_{j}\leqslant\frac{1}{n}+\frac{1}{b}\cdot\left(-10C\cdot\sqrt{(b/n)\cdot\log
n}\right).$

We will now apply a Chernoff bound (Lemma A.4) for
$x_{j}^{b}\sim\mathsf{Bin}(b,p_{j})$, with $\delta:=C\cdot\sqrt{(n/b)\cdot\log
n}$, $\mu:=b\cdot p_{j}$ and
$\mu_{H}:=\frac{b}{n}-10C\cdot\sqrt{(b/n)\cdot\log n}\geqslant\mu$ to get that

$\mathbf{Pr}\left[\,x_{j}^{b}\geqslant\frac{b}{n}-C\cdot\sqrt{(b/n)\cdot\log
n}\,\right]\leqslant\mathbf{Pr}\left[\,x_{j}^{b}\geqslant\mu_{H}\cdot(1+\delta)\,\right]\leqslant
e^{-\delta^{2}\mu_{H}/3}=e^{-\frac{C^{2}}{3}\cdot\log n}\leqslant n^{-4},$

using that $C\geqslant 4$. If
$\left\\{x_{j}^{b}\leqslant\frac{b}{n}-C\cdot\sqrt{(b/n)\cdot\log n}\right\\}$
occurs, then

$x_{j}^{b}-\frac{b}{n}+z_{j}\leqslant-C\cdot\sqrt{(b/n)\cdot\log
n}+z_{j}\leqslant-C/2\cdot\sqrt{(b/n)\cdot\log n}\leqslant 0,$

and thus bin $j$ will not contribute to the gap at step $b$.

Hence in the remainder of the proof, we would like to assume that for all bins
$j\in[n]$,

$p_{j}\geqslant\frac{1}{n}+\frac{1}{b}\cdot\left(-10C\cdot\sqrt{(b/n)\cdot\log
n}\right)=:p_{\operatorname{low}}$

Note $p_{\operatorname{low}}\leqslant 1/n$. Consider now a transformation of
the probability vector $(p_{i})_{i\in[n]}$ into
$(\widetilde{p}_{i})_{i\in[n]}$, where $\widetilde{p}$ satisfies for all
$j\in[n]$,$p_{\operatorname{low}}\leqslant\widetilde{p}_{j}\leqslant\max\left\\{p_{\operatorname{low}},p_{j}\right\\}.$
In other words, in $\widetilde{p}$ we only increase probabilities of bins
$j\in[n]$, for which $p_{j}<p_{\operatorname{low}}$. Let us define
$\mathcal{J}:=\left\\{j\in[n]\colon p_{j}<p_{\operatorname{low}}\right\\}$.
For $b\geqslant(20C^{2})n\log n$, this implies
$\widetilde{p}_{j}\geqslant\frac{1}{2n}$ for all $j\in[n]$.

Further, let $(x_{i}^{b})_{i\in[n]}$ be a load vector where the locations of
the next $b$ balls are sampled according to $p$, and
$(\widetilde{x}_{i}^{b})_{i\in[n]}$ be a load vector where these locations are
sampled according to $\widetilde{p}$. Clearly, there is a coupling so that for
every $j\in[n]\setminus\mathcal{J}$, $x_{j}^{b}\geqslant\widetilde{x}_{j}^{b}$
(since $p_{j}^{b}\geqslant\widetilde{p}_{j}^{b}$). Further, for any
$j\in\mathcal{J}$, by a union bound,

$\mathbf{Pr}\left[\,\max_{j\in\mathcal{J}}x_{j}^{b}>0\,\right]\leqslant|\mathcal{J}|\cdot
n^{-4}\leqslant n^{-3}.$

Hence it follows that, for any threshold $T>0$,

$\displaystyle\mathbf{Pr}\left[\,\max_{j\in[n]}x_{j}^{b}\geqslant T\,\right]$
$\displaystyle\geqslant\mathbf{Pr}\left[\,\max_{j\in[n]}\widetilde{x}_{j}^{b}\geqslant
T\,\right]-\mathbf{Pr}\left[\,\max_{j\in\mathcal{J}}x_{j}^{b}\geqslant
T\,\right]\geqslant\mathbf{Pr}\left[\,\max_{j\in[n]}\widetilde{x}_{j}^{b}\geqslant
T\,\right]-n^{-3}.$

Therefore, in the remainder of the proof, we will lower bound
$\mathbf{Pr}\left[\,\max_{j\in[n]\setminus\mathcal{J}}\widetilde{x}_{j}^{b}\geqslant
T\,\right]$ for a suitable value of $T=\Omega(\sqrt{b/n\cdot\log n})$. We will
also use the definition

$\widetilde{\varphi}_{j}:=b\cdot\widetilde{p}_{j}-\frac{b}{n}+z_{j}.$

Finally, we define $\xi=0.1$ as a (sufficiently) small constant.

Case 1: We have at least $n-n^{\xi}$ bins for which
$\widetilde{\varphi}_{j}\leqslant-C\sqrt{b/n}$. Since
$\sum_{i\in[n]}\widetilde{\varphi}_{i}=0$, this implies that there must be at
least one bin with $j\in[n]$ with
$\widetilde{\varphi}_{j}\geqslant\frac{n-n^{\xi}}{n^{\xi}}\cdot
C\cdot\sqrt{b/n}\geqslant 1/2\cdot n^{1-\xi}\cdot\sqrt{b/n}.$ Further, using
that the median of a $\mathsf{Bin}(N,q)$ r.v. is either $\lfloor Nq\rfloor$ or
$\lceil Nq\rceil$, then

$\mathbf{Pr}\left[\,x_{j}^{b}\geqslant\mathbf{E}\left[\,x_{j}^{b}\,\right]-\frac{1}{4}n^{1-\xi}\,\right]\geqslant\mathbf{Pr}\left[\,x_{j}^{b}\geqslant\left\lfloor\mathbf{E}\left[\,x_{j}^{b}\,\right]\right\rfloor\,\right]\geqslant
1/2,$

it follows that with probability at least $1/2$ we will have a large gap.

Case 2: We have at least $n^{\xi}$ bins with
$\widetilde{\varphi}_{j}\geqslant-C\sqrt{b/n}$; call this set $\mathcal{B}$.
We further know that, due to the definition of $\widetilde{p}$, we have for
all bins $j\in[n]$ that $\widetilde{p}_{j}\geqslant\frac{1}{2n}$. Hence, we
set
$T:=b\cdot\widetilde{p}_{j}+\kappa\cdot\sqrt{b\cdot\widetilde{p}_{j}\cdot\log
n}$, and applying Lemma A.3 yields for any bin $j\in\mathcal{B}$,
$\mathbf{Pr}\left[\,\widetilde{x}_{j}^{b}\geqslant T\,\right]\geqslant
n^{-\xi/2}.$ Since $\widetilde{p}_{j}\geqslant\frac{1}{2n}$,
$|\mathcal{B}|\geqslant n^{\xi}$, the claim follows.∎

##  6 Experimental Results

In this section, we complement our theoretical analysis with some experimental
results for the $b$-Batched setting. In Fig. 6.1, we plot the gap of the
$(1+\beta)$-process for various batch sizes and different values of
$\beta\in(0,1]$ (Two-Choice corresponding to $\beta=1$). The plot strongly
suggests the existence of an optimal $\beta$, which seems to increase as the
batch size $b$ grows.

Figure 6.1: Average gap for the $(1+\beta)$-process in the $b$-Batched setting
with unit weights for $n=1.000$ bins, $m=n^{2}$ balls, for various batch sizes
and parameter values $\beta\in(0,1]$ (averaged over $25$ runs).

In Fig. 6.2, we present the corresponding empirical results of Fig. 6.1 for
the Quantile process (mixed with One-Choice). As with the $(1+\beta)$-process,
the optimal mixing factor $\eta$ tends to increase as the batch size grows.
The Quantile with the optimized mixing factor seems to perform slightly worse
than the optimized $(1+\beta)$-process.

Figure 6.2: Average gap for the Quantile process (mixed with One-Choice with
probability $\eta\in(0,1]$) in the $b$-Batched setting with unit weights for
$n=1.000$ bins, $m=n^{2}$ balls, for various batch sizes and parameter values
$\eta\in[0,1]$ (averaged over $25$ runs).

In Fig. 6.3, we plot the gap of Two-Choice, Three-Choice and $(1+\beta)$
versus the batch size. For small values of $b$, the gap of Two-Choice and
Three-Choice is small, but soon grows rapidly, diverging from the
asymptotically optimal $(1+\beta)$-processes as predicted by the theoretical
analysis. Similar, results are observed for weights sampled from an
exponential distribution Fig. 6.4.

Figure 6.3: Average gap for Three-Choice, Two-Choice and $(1+\beta)$ with
$\beta=0.5$, $\beta=\sqrt{(n/b)\cdot\log n}$ and
$\beta=0.7\cdot\sqrt{(n/b)\cdot\log n}$ in the $b$-Batched setting with unit
weights for $n=1.000$ bins, $m=n^{2}$ balls vs batch size
$b\in\\{n,\ldots,50n\\}$ (averaged over $50$ runs). Figure 6.4: Average gap
for Three-Choice, Two-Choice and $(1+\beta)$ with $\beta=0.5$,
$\beta=\sqrt{(n/b)\cdot\log n}$ and $\beta=0.7\cdot\sqrt{(n/b)\cdot\log n}$ in
the $b$-Batched setting with weights from an $\mathsf{Exp}(1)$ distribution
for $n=1.000$ bins, $m=n^{2}$ balls vs batch size $b\in\\{n,\ldots,50n\\}$
(averaged over $50$ runs).

Finally, in Table 6.5, we show the gap of the $(1+\beta)$ and Quantile
compared to Two-Choice and One-Choice with $b$ balls (which is the
theoretically optimal attainable value), for slightly larger values of
$n\in\\{10^{4},10^{5}\\}$. The for large $b$, the $(1+\beta)$ has roughly half
the gap of Two-Choice and is close to the theoretically optimal value of One-
Choice for $m=b$ balls.

|  | Two-Choice | Quantile | $(1+\beta)$ |  $\textsc{One-Choice}^{*}$ for $m=b$
---|---|---|---|---|---
$n=10^{4}$ | $b=20n$ | 36.45 | 30.15 | 26.60 | 19.00
$b=50n$ | 70.10 | 45.75 | 39.00 | 29.75
$b=80n$ | 100.85 | 55.65 | 46.80 | 35.80
$n=10^{5}$ | $b=20n$ | 39.90 | 34.1 | 29.95 | 22.40
$b=50n$ | 75.55 | 50.3 | $\mathbf{44.20}$ | 34.30
$b=80n$ | 111.10 | 64.9 | 55.20 | 41.95

Table 6.5: Average gap for Two-Choice, Quantile (with
$\eta=\sqrt{(n/b)\cdot\log n}$) and $(1+\beta)$ (with
$\beta=0.7\sqrt{(n/b)\cdot\log n}$) in the $b$-Batched setting with
$b\in\\{20n,50n,80n\\}$ and $n\in\\{10^{4},10^{5}\\}$ (averaged over $20$
runs). The last column gives the average gap for One-Choice with $m=b$ balls
which is the theoretically optimal attainable value.

##  7 Conclusions

In this work, we revisited the outdated information setting of [6], where
balls are allocated to bins in batches of size $b$, using the load information
available at the beginning of the batch. We established that by defining the
mixing factor $\beta$ carefully as a function of the batch size $b$,
$(1+\beta)$ achieves the asymptotically optimal gap for any $b\geqslant n\log
n$. That is, by having $\beta$ chosen appropriately small, $(1+\beta)$
circumvents the “herd behavior” (as called in [28]), where some of the
previously underloaded bins are chosen too frequently, turning them into
heavily overloaded bins in the next batch. Similarly, $\beta$ should also not
be too small, as otherwise the process would be too close to One-Choice.

There are several directions for future work. First, recall that our lower
bounds apply to a large class of processes which allocate all balls within the
_same batch_ independently. However, there are processes which allocate
multiple balls in a coordinated way. For example, the process of Park [33]
draws $d$ samples, and then places into each of the $k$ least loaded bins one
ball. It would be interesting to explore the gap of this type of processes in
the $b$-Batched setting. A second avenue is to analyze Two-Thinning processes
(and in particular processes that use a fixed load threshold relative to the
average) in outdated information settings. An experimental study of threshold
processes with outdated information was already conducted in 1989 [26, Figure
8], but no rigorous bounds were proven. A third possibility is to investigate
whether the $(1+\beta)$ and related processes are superior to Two-Choice in
other settings, like the $\tau$-Delay or random noise settings studied in
[23]. Finally, one could study settings where the load information of bins is
updated at different rates, depending on the specific bin. In such a setting,
when deciding between sampled bins, both their reported load estimates and
update rates should be taken into account.

## Bibliography

  * [1]
  * Altman and Nain [1992] Eitan Altman and Philippe Nain. 1992.  Closed-Loop Control with Delayed Information. In _ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems (PERFORMANCE’92)_. ACM, 193–204.  doi
  * Azar et al. [2020] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Michael Mitzenmacher, and Eli Upfal. 2020\.  The ACM Paris Kanellakis Theory and Practice Award.  https://www.acm.org/media-center/2021/may/technical-awards-2020.
  * Azar et al. [1999] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. 1999.  Balanced allocations.  _SIAM J. Comput._ 29, 1 (1999), 180–200.  doi
  * Bansal and Feldheim [2022] Nikhil Bansal and Ohad N. Feldheim. 2022.  The power of two choices in graphical allocation. In _54th Annual ACM Symposium on Theory of Computing (STOC’22)_. ACM, 52–63.  doi
  * Berenbrink et al. [2012] Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, and Lars Nagel. 2012\.  Multiple-Choice Balanced Allocation in (Almost) Parallel. In _16th International Workshop on Randomization and Computation (RANDOM’12)_. Springer-Verlag, 411–422.  doi
  * Berenbrink et al. [2006] Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. 2006.  Balanced allocations: the heavily loaded case.  _SIAM J. Comput._ 35, 6 (2006), 1350–1385.  doi
  * Berenbrink et al. [2008] Petra Berenbrink, Tom Friedetzky, Zengjian Hu, and Russell Martin. 2008.  On weighted balls-into-bins games.  _Theoret. Comput. Sci._ 409, 3 (2008), 511–520.  doi
  * Dahlin [2000] Michael Dahlin. 2000\.  Interpreting Stale Load Information.  _IEEE Trans. Parallel Distributed Syst._ 11, 10 (2000), 1033–1047.  doi
  * Delgado et al. [2016] Pamela Delgado, Diego Didona, Florin Dinu, and Willy Zwaenepoel. 2016.  Job-aware Scheduling in Eagle: Divide and Stick to Your Probes. In _7th ACM Symposium on Cloud Computing (SoCC’16)_. ACM, 497–509.  doi
  * Delgado et al. [2015] Pamela Delgado, Florin Dinu, Anne-Marie Kermarrec, and Willy Zwaenepoel. 2015.  Hawk: Hybrid Datacenter Scheduling. In _2015 USENIX Annual Technical Conference (USENIX’15)_. USENIX, 499–510.
  * Delimitrou et al. [2015] Christina Delimitrou, Daniel Sánchez, and Christos Kozyrakis. 2015.  Tarcil: reconciling scheduling speed and quality in large shared clusters. In _6th ACM Symposium on Cloud Computing (SoCC’15)_. ACM, 97–110.  doi
  * Feldheim and Gurel-Gurevich [2021] Ohad N. Feldheim and Ori Gurel-Gurevich. 2021.  The power of thinning in balanced allocation.  _Electron. Commun. Probab._ 26 (2021), Paper No. 34, 8\.  doi
  * Feldheim and Li [2020] Ohad N. Feldheim and Jiange Li. 2020.  Load balancing under $d$-thinning.  _Electronic Communications in Probability_ 25 (2020), Paper No. 1, 13\.  doi
  * Fox et al. [1997] Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, and Paul Gauthier. 1997.  Cluster-Based Scalable Network Services. In _16th ACM Symposium on Operating Systems Principles (SOSP’97)_. ACM, 78–91.  doi
  * Karp et al. [1996] Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. 1996\.  Efficient PRAM simulation on a distributed memory machine.  _Algorithmica_ 16, 4-5 (1996), 517–542.  doi
  * Kenthapadi and Panigrahy [2006] Krishnaram Kenthapadi and Rina Panigrahy. 2006.  Balanced allocation on graphs. In _17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06)_. SIAM, 434–443.  doi
  * Khelghatdoust and Gramoli [2018] Mansour Khelghatdoust and Vincent Gramoli. 2018.  Peacock: Probe-Based Scheduling of Jobs by Rotating Between Elastic Queues. In _24th International Conference on Parallel and Distributed Computing (Euro-Par’18)_ , Vol. 11014. Springer, 178–191.  doi
  * Kuri and Kumar [1995] Joy Kuri and Anurag Kumar. 1995.  Optimal control of arrivals to queues with delayed queue length information.  _IEEE Trans. Automat. Control_ 40, 8 (1995), 1444–1450.  doi
  * Kutin [2002] Samuel Kutin. 2002\.  _Extensions to McDiarmid’s inequality when differences are bounded with high probability_.  Technical Report. University of Chicago.
  * Los and Sauerwald [2022a] Dimitrios Los and Thomas Sauerwald. 2022a.  Balanced Allocations in Batches: Simplified and Generalized. In _34th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’22)_. ACM, 389–399.  doi
  * Los and Sauerwald [2022b] Dimitrios Los and Thomas Sauerwald. 2022b.  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, 103:1–103:23.  doi
  * Los and Sauerwald [2022c] Dimitrios Los and Thomas Sauerwald. 2022c.  Balanced Allocations with the Choice of Noise. In _41st Annual ACM-SIGOPT Principles of Distributed Computing (PODC’22)_. ACM, 164–175.  doi
  * Los and Sauerwald [2023] Dimitrios Los and Thomas Sauerwald. 2023.  Tight Bounds for Repeated Balls-Into-Bins. In _40th International Symposium on Theoretical Aspects of Computer Science (STACS’23)_ , Vol. 254. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 45:1–45:22.  doi
  * Lu et al. [2011] Yi Lu, Qiaomin Xie, Gabriel Kliot, Alan Geller, James R. Larus, and Albert G. Greenberg. 2011.  Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services.  _Perform. Evaluation_ 68, 11 (2011), 1056–1071.  doi
  * Mirchandaney et al. [1989] Ravi Mirchandaney, Don Towsley, and John A. Stankovic. 1989\.  Analysis of the Effects of Delays on Load Sharing.  _IEEE Trans. Comput._ 38, 11 (nov 1989), 1513–1525.  doi
  * Mitzenmacher [1999] Michael Mitzenmacher. 1999\.  On the analysis of randomized load balancing schemes.  _Theory Comput. Syst._ 32, 3 (1999), 361–386.  doi
  * Mitzenmacher [2000] Michael Mitzenmacher. 2000\.  How Useful Is Old Information?  _IEEE Trans. Parallel Distributed Syst._ 11, 1 (2000), 6–20.  doi
  * Mitzenmacher et al. [2001] Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. 2001.  The power of two random choices: a survey of techniques and results.  In _Handbook of randomized computing, Vol. I, II_. Comb. Optim., Vol. 9. Kluwer Acad. Publ., Netherlands, 255–312.  doi
  * Nasir et al. [2015] Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, David García-Soriano, Nicolas Kourtellis, and Marco Serafini. 2015.  The power of both choices: Practical load balancing for distributed stream processing engines. In _31st IEEE International Conference on Data Engineering (ICDE’15)_. IEEE, 137–148.  doi
  * Nasir et al. [2016] Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, Nicolas Kourtellis, and Marco Serafini. 2016\.  When two choices are not enough: Balancing at scale in Distributed Stream Processing. In _32nd IEEE International Conference on Data Engineering (ICDE’16)_. IEEE, 589–600.  doi
  * Ousterhout et al. [2013] Kay Ousterhout, Patrick Wendell, Matei Zaharia, and Ion Stoica. 2013.  Sparrow: distributed, low latency scheduling. In _24th ACM SIGOPS Symposium on Operating Systems Principles (SOSP’13)_. ACM, 69–84.  doi
  * Park [2011] Gahyun Park. 2011\.  A generalization of multiple choice balls-into-bins. In _30th Annual ACM-SIGOPT Principles of Distributed Computing (PODC’11)_. ACM, 297–298.  doi
  * Peres et al. [2015] Yuval Peres, Kunal Talwar, and Udi Wieder. 2015\.  Graphical balanced allocations and the $(1+\beta)$-choice process.  _Random Structures & Algorithms_ 47, 4 (2015), 760–775.  doi
  * Raab and Steger [1998] Martin Raab and Angelika Steger. 1998.  “Balls into bins”—a simple and tight analysis. In _2nd International Workshop on Randomization and Computation (RANDOM’98)_ , Vol. 1518. Springer, 159–170.  doi
  * Talwar and Wieder [2007] Kunal Talwar and Udi Wieder. 2007.  Balanced allocations: the weighted case. In _39th Annual ACM Symposium on Theory of Computing (STOC’07)_. ACM, 256–265.  doi
  * Wang et al. [2019] Zhijun Wang, Huiyang Li, Zhongwei Li, Xiaocui Sun, Jia Rao, Hao Che, and Hong Jiang. 2019.  Pigeon: an Effective Distributed, Hierarchical Datacenter Job Scheduler. In _10th ACM Symposium on Cloud Computing (SoCC’19)_. ACM, 246–258.  doi
  * Whitt [1986] Ward Whitt. 1986\.  Deciding Which Queue to Join: Some Counterexamples.  _Oper. Res._ 34, 1 (1986), 55–62.  doi
  * Wieder [2017] Udi Wieder. 2017\.  Hashing, Load Balancing and Multiple Choice.  _Found. Trends Theor. Comput. Sci._ 12, 3-4 (2017), 275–379.  doi

##  Appendix A Tools

###  A.1 Auxiliary Probabilistic Claims

For convenience, we add the following well-known inequality for a sequence of
random variables, whose expectations are related through a recurrence
inequality.

######  Lemma A.1.

Consider a sequence of random variables $(X^{i})_{i\in\mathbb{N}}$ such that
there exist $a\in(0,1)$ and $b>0$ such that every $i\geqslant 1$,

$\mathbf{E}\left[\,X^{i}\mid X^{i-1}\,\right]\leqslant X^{i-1}\cdot a+b.$

Then, for every $i\geqslant 1$,

$\mathbf{E}\left[\,X^{i}\mid X^{0}\,\right]\leqslant X^{0}\cdot
a^{i}+\frac{b}{1-a}.$

###### Proof.

We will prove by induction that for every $i\in\mathbb{N}$,

$\mathbf{E}\left[\,X^{i}\mid X^{0}\,\right]\leqslant X^{0}\cdot
a^{i}+b\cdot\sum_{j=0}^{i-1}a^{j}.$

For $i=0$, it trivially holds that $\mathbf{E}\left[\,X^{0}\mid
X^{0}\,\right]\leqslant X^{0}$. Assuming the induction hypothesis holds for
some $i\geqslant 0$, then since $a>0$,

$\displaystyle\mathbf{E}\left[\,X^{i+1}\mid X^{0}\,\right]$
$\displaystyle=\mathbf{E}\left[\,\mathbf{E}\left[\,X^{i+1}\mid
X^{i}\,\right]\mid X^{0}\,\right]\leqslant\mathbf{E}\left[\,X^{i}\mid
X^{0}\,\right]\cdot a+b$ $\displaystyle\leqslant\Big{(}X^{0}\cdot
a^{i}+b\cdot\sum_{j=0}^{i-1}a^{j}\Big{)}\cdot a+b$ $\displaystyle=X^{0}\cdot
a^{i+1}+b\cdot\sum_{j=0}^{i}a^{j}.$

The claims follows using that for $a\in(0,1)$,
$\sum_{j=0}^{\infty}a^{j}=\frac{1}{1-a}$. ∎

For the next lemma, we define for two $n$-dimensional vectors $x,y$, $\langle
x,y\rangle:=\sum_{i=1}^{n}x_{i}\cdot y_{i}$.

######  Lemma A.2 ([21, Lemma A.7]).

Let $(p_{k})_{k=1}^{n},(q_{k})_{k=1}^{n}$ be two probability vectors and
$(c_{k})_{k=1}^{n}$ be non-negative and non-increasing. Then if $p$ majorizes
$q$, i.e., for all $1\leqslant k\leqslant n$,
$\sum_{i=1}^{k}p_{i}\geqslant\sum_{i=1}^{k}q_{i}$ holds, then

$\langle p,c\rangle\geqslant\langle q,c\rangle.$

We continue with an “anti-concentration” result, i.e., a lower bound on the
probability that a binomial random variable is significantly larger than its
expectation.

######  Lemma A.3.

Let $m,n$ be integers such that $m\geqslant n\log n$. Further, let $p$ be a
probability satisfying $p\in[1/(2n),1/2]$ and let $X\sim\mathsf{Bin}(m,p)$.
Then for any constant $\xi\in(0,1)$, there exists a constant $\kappa\geqslant
0$, such that

$\displaystyle\mathbf{Pr}\left[\,X\geqslant m\cdot
p+\kappa\cdot\sqrt{mp\cdot\log n}\,\right]\geqslant n^{-\xi/2}.$

###### Proof.

Since $X\sim\mathsf{Bin}(m,p)$, we know that

$\mathbf{Pr}\left[\,X=m\cdot p\,\right]=\binom{m}{m\cdot p}\cdot p^{m\cdot
p}\cdot(1-p)^{m-m\cdot p}.$

Let $\mu:=m\cdot p$ and $f(z):=\mathbf{Pr}\left[\,X=z\,\right]$ for any
$z\in[0,m]$. Then, for any integer $k\geqslant 1$,

$\displaystyle\frac{f(\mu+k)}{f(\mu+(k-1))}$
$\displaystyle=\frac{\frac{m!}{(\mu+k)!(m-\mu-k)!}}{\frac{m!}{(\mu+k-1)!(m-\mu-k+1)!}}\cdot\frac{p}{1-p}$
$\displaystyle=\frac{m-\mu-k+1}{\mu+k}\cdot\frac{p}{1-p}$
$\displaystyle=\frac{m\cdot(1-\frac{\mu+k-1}{m})}{(1+\frac{k}{\mu})m\cdot
p}\cdot\frac{p}{1-p}$
$\displaystyle=\frac{1-\frac{\mu+k-1}{m}}{1+\frac{k}{\mu}}\cdot\frac{1}{1-p}$
$\displaystyle=\frac{1-p\cdot\frac{\mu+k-1}{\mu}}{1+\frac{k}{\mu}}\cdot\frac{1}{1-p}.$

The first factor is decreasing in $k$. Hence, for any $K\geqslant 1$,

$\displaystyle f(\mu+K)$ $\displaystyle\geqslant
f(\mu)\cdot\left(\frac{\mu\cdot(1-p)-(K-1)p}{\mu+K}\right)^{K}\cdot\left(\frac{1}{1-p}\right)^{K}$
$\displaystyle=f(\mu)\cdot\left(\frac{(\mu+K)\cdot(1-p)-K(1+p)}{(\mu+K)\cdot(1-p)}\right)^{K}$
$\displaystyle=f(\mu)\cdot\left(1-\frac{K(1+p)}{(\mu+K)\cdot(1-p)}\right)^{(\frac{(\mu+K)\cdot(1-p)}{K(1+p)}-1)\cdot\frac{K}{\frac{(\mu+K)\cdot(1-p)}{K(1+p)}-1}}$

We will now make use of the fact that $(1-\frac{1}{N})^{N-1}\geqslant e^{-1}$,
where $N:=\frac{(\mu+K)\cdot(1-p)}{K\cdot(1+p)}$. With this we have,

$\displaystyle f(\mu+K)$
$\displaystyle=f(\mu)\cdot\left(1-\frac{1}{N}\right)^{(N-1)\cdot\frac{K}{N-1}}$
$\displaystyle\geqslant f(\mu)\cdot
e^{-\frac{K}{\frac{(\mu+K)\cdot(1-p)}{K(1+p)}-1}}$ $\displaystyle\geqslant
f(\mu)\cdot e^{-\frac{2K}{\frac{(\mu+K)\cdot(1-p)}{K(1+p)}}}$
$\displaystyle\geqslant f(\mu)\cdot e^{-\frac{8K^{2}}{(\mu+K)}}$
$\displaystyle\geqslant f(\mu)\cdot e^{-\frac{16K^{2}}{\mu}},$

having used that $p\leqslant 1/2$ and $K\leqslant 4\cdot\mu$. Further, by a
concentration bound, e.g., by Chebyshev’s inequality,

$\mathbf{Pr}\left[\,|X-\mu|\geqslant
2\sqrt{\mathbf{Var}\left[\,X\,\right]}\,\right]\leqslant\frac{1}{4}.$

This implies that at least $\frac{3}{4}$ of the probability of $X$ is on the
interval
$[\mu-2\sqrt{\mathbf{Var}\left[\,X\,\right]},\mu+2\sqrt{\mathbf{Var}\left[\,X\,\right]}]$.
Since the mode, i.e., largest probability is $\lfloor(m+1)p\rfloor$ or
$\lceil(m+1)p\rceil-1$, it follows that

$f(\mu)\geqslant\frac{3}{8\cdot\mathbf{Var}\left[\,X\,\right]}=\frac{3}{8\cdot\sqrt{m\cdot
p(1-p)}}\geqslant\frac{3}{8\sqrt{\mu}}.$

Then, it follows that

$\displaystyle\mathbf{Pr}\left[\,\widetilde{x}_{j}\geqslant\mu+\xi/2\cdot\sqrt{\mu\log
n}\,\right]$ $\displaystyle\geqslant\sum_{K=\xi/100\cdot\sqrt{\mu\log
n}}^{m}f(\mu+K)$ $\displaystyle\geqslant\sum_{K=\xi/100\cdot\sqrt{\mu\log
n}}^{\xi/50\cdot\sqrt{\mu\log n}}f(\mu+K)$ $\displaystyle\geqslant
f(\mu)\cdot\sum_{K=\xi/100\cdot\sqrt{\mu\log n}}^{\xi/50\cdot\sqrt{\mu\log
n}}e^{-\frac{16K^{2}}{\mu}}$
$\displaystyle\geqslant\frac{3}{8\sqrt{\mu}}\cdot\xi/100\cdot\sqrt{\mu\log
n}\cdot e^{-16\xi^{2}/2500\cdot\log n}$ $\displaystyle\geqslant
n^{-32/2500\xi^{2}}\geqslant n^{-\xi/2}.$

∎

###  A.2 Concentration Inequalities

We now proceed by stating a standard Chernoff bound.

######  Lemma A.4 (Chernoff Bound).

Let $X^{1},\ldots,X^{n}$ be independent random variables taking values in
$\\{0,1\\}$. Let $X=\sum_{i=1}^{n}X^{i}$, $\mu=\mathbf{E}\left[\,X\,\right]$
and $\delta\geqslant 0$ be arbitrary. Then, for any $\mu_{H}\geqslant\mu$,

$\mathbf{Pr}\left[\,X\geqslant(1+\delta)\cdot\mu_{H}\,\right]\leqslant
e^{-\delta^{2}\mu_{H}/3}.$

Following [20], we will now give the definition for strongly difference-
bounded and then give the statement for a bounded differences inequality with
bad events.

######  Definition A.5 (Strongly difference-bounded – [20, Definition 1.6]).

Let $\Omega_{1},\ldots,\Omega_{N}$ be probability spaces. Let
$\Omega=\prod_{k=1}^{N}\Omega_{k}$ and let $X$ be a random variable on
$\Omega$. We say that $X$ is strongly difference-bounded by
$(\eta_{1},\eta_{2},\xi)$ if the following holds: there is a “bad” subset
$\mathcal{B}\subseteq\Omega$, where
$\xi=\mathbf{Pr}\left[\,\omega\in\mathcal{B}\,\right]$. If
$\omega,\omega^{\prime}\in\Omega$ differ only in the $k$-th coordinate, and
$\omega\notin B$, then

$|X(\omega)-X(\omega^{\prime})|\leqslant\eta_{2}.$

Furthermore, for any $\omega$ and $\omega^{\prime}$ differing only in the
$k$-th coordinate,

$|X(\omega)-X(\omega^{\prime})|\leqslant\eta_{1}.$

######  Theorem A.6 ([20, Theorem 3.3]).

Let $\Omega_{1},\ldots,\Omega_{N}$ be probability spaces. Let
$\Omega=\prod_{k=1}^{N}\Omega_{k}$, and let $X$ be a random variable on
$\Omega$ which is strongly difference-bounded by $(\eta_{1},\eta_{2},\xi)$.
Let $\mu=\mathbf{E}[\,X\,]$. Then for any $\lambda>0$ and any
$\gamma_{1},\ldots,\gamma_{N}>0$,

$\mathbf{Pr}\left[\,X\geqslant\mu+\lambda\,\right]\leqslant\exp\left(-\frac{\lambda^{2}}{2\cdot\sum_{k=1}^{N}(\eta_{2}+\eta_{1}\gamma_{k})^{2}}\right)+\xi\cdot\sum_{k=1}^{N}\frac{1}{\gamma_{k}}.$