Balanced Allocations: Caching and Packing, Twinning and Thinning
View / Open Files
Authors
Los, Dimitrios
Sauerwald, Thomas
Sylvester, John
Publication Date
2022-01Journal 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)
ISBN
9781611977073
Publisher
Society for Industrial and Applied Mathematics
Pages
1847-1874
Type
Conference Object
This Version
AM
Metadata
Show full item recordCitation
Los, D., Sauerwald, T., & Sylvester, J. (2022). Balanced Allocations: Caching and Packing, Twinning and Thinning. https://epubs.siam.org/doi/10.1137/1.9781611977073.74, 1847-1874. https://doi.org/10.1137/1.9781611977073.74
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.
Sponsorship
Thomas Sauerwald was supported by the ERC Starting Grant 679660 (DYNAMIC MARCH)
Funder references
European Research Council (679660)
Identifiers
External DOI: https://doi.org/10.1137/1.9781611977073.74
This record's URL: https://www.repository.cam.ac.uk/handle/1810/335067
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk