On Balls and Bins with Deletions
On Balls and Bins with Deletions
复制标题
在删除的球和垃圾箱上
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
E. Upfal
中科院分区：
文献类型：
--
作者：
R. Cole;A. Frieze;B. Maggs;M. Mitzenmacher;A. Richa;R. Sitaraman;E. Upfal
我们考虑的问题，扩展球和箱子的过程中，一个球被放置在最少的d随机选择的箱子，以涵盖删除的分析。特别是，我们感兴趣的情况下，系统保持一个固定的负载，并删除由对手确定的过程开始之前。我们表明，具有很高的概率，在任何bin中的负载是O（log log n）。事实上，这一结果来自于科尔等人最近的工作，涉及蝴蝶网络中更困难的路由问题。
本文的主要贡献是给出了一个不同的证明这个界限，这遵循了Azar，Broder，Karlin和Upfal对相应的静态负载平衡问题的分析。我们还给出了一个专门的（因此更简单）版本的论点从文件的科尔等人。球和箱子的情况。最后，我们提供了一个替代的分析方法的基础上，阿扎尔，布罗德，卡林，和Upfal的特殊情况下，项目被删除，根据他们的年龄。虽然这种分析并没有比我们对一般情况的论证产生更好的界限，但它很有趣，因为它利用了一个二维随机变量族来解释物品的年龄。这种技术可能有更广泛的用途。
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions are determined by an adversary before the process begins. We show that with high probability the load in any bin is O(log log n). In fact, this result follows from recent work by Cole et al. concerning a more difficult problem of routing in a butterfly network.
The main contribution of this paper is to give a different proof of this bound, which follows the lines of the analysis of Azar, Broder, Karlin, and Upfal for the corresponding static load balancing problem. We also give a specialized (and hence simpler) version of the argument from the paper by Cole et al. for the balls and bins scenario. Finally, we provide an alternative analysis also based on the approach of Azar, Broder, Karlin, and Upfal for the special case where items are deleted according to their age. Although this analysis does not yield better bounds than our argument for the general case, it is interesting because it utilizes a two-dimensional family of random variables in order to account for the age of the items. This technique may be of more general use.