Technical reports
Balanced allocations under incomplete information: New settings and techniques
November 2023, 230 pages
This technical report is based on a dissertation submitted April 2023 by the author for the degree of Doctor of Philosophy to the University of Cambridge, St John’s College.
| DOI | https://doi.org/10.48456/tr-989 |
Abstract
In the balanced allocations framework, there are 𝑚 balls to be allocated into 𝑛 bins with the aim of minimising the maximum load of any of the bins, or equivalently minimising the “gap”, i.e., the difference between the maximum load and the average load. In this dissertation, we focus on the “heavily-loaded case” where 𝑚 ≫ 𝑛, which tends to be more challenging to analyse.
In a decentralised setting, the simplest process is One-Choice, which allocates each ball to a bin sampled uniformly at random. It is well-known that w.h.p. Gap(𝑚) = Θ( sqrt( 𝑚/𝑛 · log 𝑛 ) ) for any 𝑚 ≫ 𝑛. A great improvement over this is the Two-Choice process [ABKU99, KLM96], which allocates each ball to the least loaded of two bins sampled uniformly at random. Berenbrink, Czumaj, Steger, and Vöcking (2006) showed that w.h.p. Gap(𝑚) = log₂ log 𝑛 + Θ(1) for any 𝑚 ≥ 𝑛. This improvement is known as the “power of two choices”. It has found several applications in hashing, load balancing and routing; and its importance was recently recognised in the 2020 ACM Theory and Practice Award.
In this dissertation, we introduce a set of techniques based on “potential functions”. These enable us to analyse (both in terms of gap and load distribution) a wide range of processes and settings in the heavily-loaded case and to establish interesting insights in the balanced allocations framework:
• We analyse variants of the Two-Choice process which trade sample efficiency, completeness of information and gap guarantees. For the (1+β)-process which mixes One-Choice and Two-Choice with probability β in (0, 1], we prove tight bounds for small and large β, extending the results of Peres, Talwar and Wieder (2015). Another sample efficient family is that of Two-Thinning processes, which allocate to the two sampled bins in an online manner. For Two-Thinning processes that use as a decision function thresholds relative to the average load or thresholds in the rank domain, we establish tight bounds and also resolve a conjecture by Feldheim and Gurel-Gurevich (2021). We also quantify trade-offs for two-sample processes between the number of queries and the gap bound, establishing a “power of two queries” phenomenon.
• We analyse the Two-Choice process with random, adversarial and delay noise, proving tight bounds for various settings. In the adversarial setting, the adversary can decide in which of the two sampled bins the ball is allocated to, only when the two loads differ by at most 𝑔. The analysis of this setting implies bounds for settings with random noise and delay.
For the setting where load information is updated periodically every 𝑏 steps, for 𝑏 = 𝑛 we tighten the bound of [BCEFN12] to Θ( log 𝑛 / log log 𝑛 ) and prove that Two-Choice is optimal in this setting for any in [𝑛 · exp(−logᶜ 𝑛), 𝑛 log 𝑛] for any constant 𝑐 > 0. For 𝑏 in [𝑛 log 𝑛, 𝑛³], we show that Two-Choice achieves w.h.p. a Θ(𝑏/𝑛) gap, while surprisingly the (1+β)-process with appropriately chosen β achieves w.h.p. a Θ( sqrt( 𝑏/𝑛 · log 𝑛) ) gap, which is optimal over a large family of processes. This proves that in the presence of outdated information, less aggressive strategies can outperform the greedy processes (such as Two-Choice), which has been empirically observed in the queuing setting [D00, M00] for centralised processes since 2000, but to the best of our knowledge has not been formally proven.
• Next we analyse Two-Choice in the graphical setting, where bins are vertices of a graph and each ball is allocated to the lesser loaded of the vertices adjacent to a randomly sampled edge. We extend the results of Kenthapadi and Panigrahy (2006) proving that for dense expanders in the heavily-loaded case the gap is w.h.p. O(log log 𝑛). In the presence of weights, we make progress towards [Open Problem 1, PTW15] by proving that for graphs with conductance φ, the gap is w.h.p. Ο(log 𝑛 / φ).
• Further, we introduce and analyse processes which can allocate more than one balls to a sampled bin. We prove that these processes achieve w.h.p. an O(log 𝑛) gap (which also applies for any 𝑑-regular graph), while still being more sample-efficient than One-Choice (“power of filling”).
• For the Memory process that can store bins in a cache, we generalise the O(log log 𝑛) gap bound by Mitzenmacher, Prabhakar and Shah (2002) to the heavily-loaded case and prove a matching lower bound. Further, in the presence of heterogeneous sampling distributions, we establish a striking difference between Two-Choice (or even 𝑑-Choice with 𝑑 = O(1)) and Memory, showing that for the later the gap is bounded, while for the former it is known to diverge [W07] (“power of memory”).
Full text
PDF (3.4 MB)
This report is licensed under a Creative Commons Attribution 4.0 International (CC BY 4.0) licence.
BibTeX record
@TechReport{UCAM-CL-TR-989,
author = {Los, Dimitrios},
title = {{Balanced allocations under incomplete information: New
settings and techniques}},
year = 2023,
month = nov,
url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-989.pdf},
institution = {University of Cambridge, Computer Laboratory},
doi = {10.48456/tr-989},
number = {UCAM-CL-TR-989}
}