论文标题
平衡分配：大量加载的外壳带有删除
Balanced Allocations: The Heavily Loaded Case with Deletions
论文作者
论文摘要
在2个选择分配问题中，$ m $球被放入$ n $ bins，每个球都必须在分配给它的两个随机bins $ i，j \ in [n] $之间选择。已经知道了二十年来，如果每个球都遵循贪婪的策略（即，始终选择不足的垃圾箱），则最大负载为$ m / n + o（\ log \ log \ log \ log \ log \ log \ log n）$，具有$ n $的可能性很高（$ n $（和$ m / n + o（\ log m）$（\ log M）$，具有$ m $的可能性很高）。无论是否在同一游戏的动态版本中保持相同的界限，在该界限中插入/删除了最多$ m $ $球。 我们表明，这些界限在动态设置中不存在：已经在$ 4 $的垃圾箱中，存在一系列插入/删除，导致{Greedy}的最大负载为$ M/4 +ω（\ sqrt {m} $ ch），并以可能的情况与每个BALL分配了BIN！ 这就提出了一个问题，即是否有2个选择分配策略可以在动态环境中提供强大的限制。我们的第二个结果以肯定的方式回答了这个问题：我们提出了一种称为ModualdedGreedy的新策略，可确保在任何给定时刻的最大负载$ m / n + O（\ log M）$，并且$ m $的可能性很高。概括调制的greedy，我们获得了$（1 +β）$ - 选择设置的动态保证，以及图表上的球和bins的设置。 最后，我们考虑了一个设置，在删除球后可以重新插入球，以及在插入之间给定球使用的$ i，j $的设置。这种看似很小的修改使得不可能进行紧密的负载平衡：在4个垃圾箱上，任何遗忘了球的策略都必须在第一个$ poly（m）$ insertions/删除的某个时候允许$ m/4 + poly（m）$的最大负载，并具有$ m $的可能性很高。
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 + Ω(\sqrt{m})$ with probability $Ω(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 + β)$-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$.
