Balanced allocations: the weighted case

By Kunal Talwar, Udi Wieder. 2007

59 citations recorded by the source corpus.

We investigate balls-and-bins processes where m weighted balls areplaced into n bins using the "power of two choices" paradigm,whereby a ball is inserted into the less loaded of two randomly chosen bins. The case where each of the m balls has unit weight had been studied extensively. In a seminal paper Azar et.al. showed that when m=n the most loaded bin has Θ(log log n) balls with high probability. Surprisingly, thegap in load between the heaviest bin and the average bin does not increase with m and was shown by Berenbrink etal tobe Θ(log log n) with high probability for arbitrarily large m. We generalize this result to the weighted case where balls have weights drawn from an arbitrary weight distribution. We show that aslong as the weight distribution has finite second moment andsatisfies a mild technical condition, the gap between the weight of the heaviest bin and the weight of the average bin is independent ofthe number balls thrown. This is especially striking whenconsidering heavy tailed distributions such as Power-Law andLog-Normal distributions. In these cases, as more balls are thrown,heavier and heavier weights are encountered. Nevertheless with high probability, the imbalance in the load distribution does notincrease. Furthermore, if the fourth moment of the weight distribution is finite, the expected value of the gap is shown to beindependent of the number of balls.

Subfields: Artificial Intelligence, Management Science and Operations Research, Marketing

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Marketing

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.”
The (1 + β)-choice process and weighted balls-into-bins (2010, methodology): “We note that it is not obvious how to apply the coupling techniques in [2, 7] to these processes.”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, methodology): “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]).”