Balanced Allocations with Incomplete Information: The Power of Two Queries
summary
Proves any adaptive one-quantile or one-threshold scheme has gap at least Omega(log n / log log n) in the heavily loaded regime, disproving the conjectured small gap; constructs a uniform k-quantile process with gap O(k·(log n)^{1/k}) so k=2 gives Θ(√log n) and k=Θ(log log n) recovers the classical two-choice Θ(log log n) bound; techniques combine layered induction over super-exponential potential functions, two-sided exponential potentials, boundary-difference concentration, and Markov-type arguments.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:16Balanced allocations setting
- 1:03ONE-CHOICE and Two-CHOICE processes
- 2:30(1+3) process: Definition
- 3:15Adaptive 1-THRESHOLD
- 4:22Adaptive l-QUANTILE
- 5:311-THRESHOLD as TWO-CHOICE with incomplete information
- 7:03Our results
- 9:22Lower bound proof (1)
- 11:55The exponential potential function
- 13:55Technique 1: Super-exponential potential functions
- 16:56Technique 2: Proving is linear w.h.p.
- 18:22Conclusion
- 19:52Questions?
related talks
27mConsensus Division in an Arbitrary Ratio
10mQuery, Communication and Discrepancy
26mCounting Distinct Elements in the Message Passing Model
58mCharacterization of Cutoff for Reversible Markov Chains, and Surprise Probabilities
27mOn Distributed Differential Privacy and Counting Distinct Elements
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
19mDistributed load balancing: a new framework and improved guarantees
43mLimited Communication Gradient Methods for Distributed Resource Allocation Optimization