Balanced Allocations: Caching and Packing, Twinning and Thinning

Conference Object
Change log
Los, Dimitrios 
Sauerwald, Thomas 
Sylvester, John 

We consider the sequential allocation of 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.

In this paper, we present a general framework that allows us to analyze various allocation processes that slightly prefer allocating into underloaded, as opposed to overloaded bins. Our analysis covers several natural instances of processes, including:

The Caching process (a.k.a. memory protocol) as studied by Mitzenmacher, Prabhakar and Shah (2002).

The Packing process: At each round we only take one bin sample. If the load is below some threshold (e.g., the average load), then we place as many balls until the threshold is reached; otherwise, we place only one ball.

The Twinning process: At each round, we only take one bin sample. If the load is below some threshold, then we place two balls; otherwise, we place only one ball.

The Thinning process as recently studied by Feldheim and Gurel-Gurevich (2021).

As we demonstrate, using an interplay between several potential functions our general framework implies for all these processes a gap of O(log n) for any number of balls m ≥ n.

Journal Title
Conference Name
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Journal ISSN
Volume Title
Society for Industrial and Applied Mathematics
European Research Council (679660)
Thomas Sauerwald was supported by the ERC Starting Grant 679660 (DYNAMIC MARCH)