【剑桥大学博士论文】不完全信息下均衡分配：新的设置与技术，237页pdf

在平衡分配框架中，有𝑚球被分配到𝑛桶中，目的是最小化任何桶的最大负载，或等效地最小化𝑔𝑎𝑝，即最大负载和平均负载之间的差。在本文中,我们专注于ℎ𝑒𝑎𝑣𝑖𝑙𝑦——𝑙𝑜𝑎𝑑𝑒𝑑𝑐𝑎𝑠𝑒哪里𝑚≫𝑛,这往往是更具挑战性的分析。 在分散的环境中，最简单的过程是单选择，即将每个球分配到随机均匀抽样的箱子中。众所周知，w.h.p. Gap(𝑚)= Θ(sqrt(𝑚/𝑛·log𝑛))用于任何𝑚≫ 𝑛。与此相比，一个很大的改进是二选择过程[ABKU99, KLM96]，它将每个球分配到随机均匀抽样的𝑡𝑤𝑜箱子中负载最小的箱子中。Berenbrink、Czumaj、Steger和Vöcking(2006)表明对于任何𝑚小于𝑛的情况，w.h.p. Gap(𝑚)= log₂log𝑛+ Θ(1)。这种改进被称为“两种选择的力量”。它在哈希、负载均衡和路由等方面有很多应用;它的重要性最近在2020年ACM理论与实践奖中得到了认可。在本文中,我们介绍一组技术基于𝑝𝑜𝑡𝑒𝑛𝑡𝑖𝑎𝑙𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑠。这使我们能够在重负载情况下分析(差距和负载分布)广泛的过程和设置，并在平衡分配框架中建立有趣的见解:-我们分析了交易样本效率、信息完整性和差距保证的两选择过程的变体。对于(0,1]中概率β混合了一选择和二选择的(1+β)-过程，证明了小β和大β的紧界，推广了Peres, Talwar和Wieder(2015)的结果。另一种高效样本族是两细化过程，它以在线方式分配给两个采样箱。对于两个细化过程，将其作为相对于平均负载或秩域阈值的决策函数阈值，建立了严格的界限，并解决了Feldheim和Gurel-Gurevich(2021)的猜想。量化了两样本过程在查询数量和差距界限之间的权衡，建立了"两个查询的力量"现象。-我们分析了具有随机、对抗性和延迟噪声的二选择过程，证明了各种设置的紧边界。在对抗性环境中，对手可以决定球被分配到两个采样箱中的哪一个，只有当两个负载最多相差𝑔时。对该设置的分析意味着随机噪声和延迟设置的界限。设置负载信息的定期更新每个𝑏步骤,𝑏=𝑛我们收紧(BCEFN12)的绑定Θ(日志𝑛/日志日志𝑛),并证明了两个附加在此设置为任何最佳[𝑛 · exp(-logᶜ 𝑛), 𝑛 log 𝑛]为任意常数𝑐> 0。在[𝑛 log 𝑛, 𝑛³],我们显示了两个附加达到w.h.p.Θ(𝑏/𝑛)gap,而令人惊讶的是(1 +β)process与适当选择β达到Θ( sqrt( 𝑏/𝑛 · log 𝑛) ) gap,这是流程优化族。这证明了在过时信息存在的情况下，较不激进的策略可以胜过贪婪过程(如Two-Choice)，这是自2000年以来在集中式进程的排队设置[D00, M00]中根据经验观察到的，但据我们所知，尚未得到正式证明。-接下来，我们分析图形设置中的二选择，其中桶是图的顶点，每个球被分配到随机采样边相邻的负载较轻的顶点。我们扩展了Kenthapadi和Panigrahy(2006)的结果，证明对于密集扩展器，在重载情况下，差距是w.h.p.o (log log𝑛)。在权重存在的情况下，通过证明对于电导φ的图，间隙为w.h.p. Ο(log𝑛/ φ)，我们朝着[开放问题1,PTW15]取得了进展。-此外，我们介绍并分析了可以将多个球分配到采样箱的过程。本文证明，这些过程实现了w.h.p. O(log𝑛)差距(这也适用于任何𝑑-regular图)，同时仍然比单一选择(“填充的力量”)更有效。-对于可以在缓存中存储箱子的内存进程，我们将Mitzenmacher, Prabhakar和Shah(2002)提出的O(log log𝑛)缺口界限推广到重负载情况，并证明了一个匹配的下界。此外，在异构采样分布的存在下，我们在两选择(甚至𝑑-Choice，𝑑= O(1))和内存之间建立了显著的差异，表明对于后者，差距是有限的，而对于前者，众所周知是发散的W07。