Balanced Allocations

By Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal. 1999

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “Relatedly, many data structures, systems, and networking applications use different variants of hashing—consistent [49], asymmetric [73], weighted [72], multi-choice [9, 61], cuckoo [8, 63], and others [18, 34]—to achieve the same goal.”
An Improved Construction for Counting Bloom Filters (2006, methodology): “Our approach makes use of d-left hashing, a variation of the balanced allocations paradigm [1] due to Vöcking [20], which we now recall.”
Dispersion games: general definitions and some specific learning results (2002, background): “Perhaps the most natural application is presented by the much studied load balancing problem (see, e.g., Azar et al. 2000).”
Theory and Practice of Bloom Filters for Distributed Systems (2012, background): “in his seminal work on balanced allocations [17].”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, background): “Central to our analytic approach is a new technical connection between averaging decentralized SGD and the line of research studying load-balancing processes in theoretical computer science (e.g. [14, 35, 47, 39]).”
Cuckoo Hashing (2001, methodology): “A more re scheme called T WO-WAY CHAINING [2] will also be investigated.”
Faster Private Set Intersection Based on OT Extension (2014, methodology): “Balanced Allocations The balanced allocations hashing scheme [2] uses two uniformly random hash functions h 1 , h 2 : {0, 1} σ → [1, m].”
How asymmetry helps load balancing (1999, result): “These examples are described exhaustively in [2].”
Resource Management in Clouds: Survey and Research Challenges (2015, unknown): “[30].”
The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation (2007, background): “Since these thresholds coincide with lower bounds for the achievable solution quality, this proves the optimality of our algorithm (as n .”
Tight Thresholds for Cuckoo Hashing via XORSAT (2009, methodology): “This setting describes the o ine load balancing problem corresponding to multiple choice hashing [1] and cuckoo hashing [12,25] with k ≥ 3 choices.”
Balls into Bins Made Faster (2013, unknown): “[1] showed that if each ball is placed into the one which is least loaded at the time of placement then with high probability(1) the maximum load is log logn log 2 + Θ(1), which is an exponential improvement over the previous case.”