  In the 2-choice allocation problem, $m$ balls are placed into $n$ bins, and
each ball must choose between two random bins $i, j \in [n]$ that it has been
assigned to. It has been known for more than two decades, that if each ball
follows the Greedy strategy (i.e., always pick the less-full bin), then the
maximum load will be $m/n + O(\log \log n)$ with high probability in $n$ (and
$m / n + O(\log m)$ with high probability in $m$). It has remained open whether
the same bounds hold in the dynamic version of the same game, where balls are
inserted/deleted with up to $m$ balls present at a time.
  We show that these bounds do not hold in the dynamic setting: already on $4$
bins, there exists a sequence of insertions/deletions that cause {Greedy} to
incur a maximum load of $m/4 + \Omega(\sqrt{m})$ with probability $\Omega(1)$
-- this is the same bound as if each ball is simply assigned to a random bin!
  This raises the question of whether any 2-choice allocation strategy can
offer a strong bound in the dynamic setting. Our second result answers this
question in the affirmative: we present a new strategy, called ModulatedGreedy,
that guarantees a maximum load of $m / n + O(\log m)$, at any given moment,
with high probability in $m$. Generalizing ModulatedGreedy, we obtain dynamic
guarantees for the $(1 + \beta)$-choice setting, and for the setting of
balls-and-bins on a graph.
  Finally, we consider a setting in which balls can be reinserted after they
are deleted, and where the pair $i, j$ that a given ball uses is consistent
across insertions. This seemingly small modification renders tight load
balancing impossible: on 4 bins, any strategy that is oblivious to the specific
identities of balls must allow for a maximum load of $m/4 + poly(m)$ at some
point in the first $poly(m)$ insertions/deletions, with high probability in
$m$.
