Balanced allocations: Caching and Packing, Twinning and Thinning

The task in the balanced allocation problem is to sequentially allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small `gap' between the maximum load and the average load. If each ball is allocated to a uniformly sampled bin the gap diverges as m (# balls) grows (one choice), whereas if each bin chooses the least loaded of two uniformly chosen bins the gap remains bounded by a function of n (# bins) for any m (two choice). 

We present a general framework that allows us to analyse various processes that slightly prefer allocating into underloaded, as opposed to overloaded bins. Our analysis covers several natural instances of processes, including:
-The Caching process (Mitzenmacher, Prabhakar & Shah, 2002): The process can store (cache) a single bin location. At each round sample one bin, place a ball in the least loaded of the bin or cache and update the cache.
-The Twinning process: At each round sample one bin. If the load is below some threshold, then we place two balls; otherwise, we place only one ball.
Our framework also covers a variant of Twinning called Packing, and the Thinning process (Feldheim & Gurel-Gurevich, 2021).

We prove that any process within the framework (including those above) have a gap of O(log n) for any m with high probability. We prove this using an interplay between several potential functions. Furthermore, any process in the framework uses at most two samples per ball placed, and we show that some use less than one.

This talk is based on joint work with Dimitrios Los & Thomas Sauerwald.