Repository logo
 

Balanced Allocations: Caching and Packing, Twinning and Thinning

Accepted version
Peer-reviewed

Type

Conference Object

Change log

Authors

Los, Dimitrios 
Sauerwald, Thomas 
Sylvester, John 

Abstract

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.

Description

Keywords

Journal Title

https://epubs.siam.org/doi/10.1137/1.9781611977073.74

Conference Name

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Journal ISSN

Volume Title

Publisher

Society for Industrial and Applied Mathematics
Sponsorship
European Research Council (679660)
Thomas Sauerwald was supported by the ERC Starting Grant 679660 (DYNAMIC MARCH)