Long-term balanced allocation via thinning

DOI10.1214/23-AAP1978MaRDI QIDQ6126120zbMATH OpenFDO

Authors Ohad Noy Feldheim, Ori Gurel-Gurevich, Jiange Li

Publication date 9 April 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.05009, https://projecteuclid.org/journals/annals-of-applied-probability/volume-34/issue-1A/Long-term-balanced-allocation-via-thinning/10.1214/23-AAP1978.full

zbMATH Keywords

balls-and-binsload balancingtwo-choicetwo-thinning

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Abstract: We study the long-term behavior of the two-thinning variant of the classical balls-and-bins model. In this model, an overseer is provided with uniform random allocation of $m$ balls into $n$ bins in an on-line fashion. For each ball, the overseer could reject its allocation and place the ball into a new bin drawn independently at random. The purpose of the overseer is to reduce the maximum load of the bins, which is defined as the difference between the maximum number of balls in a single bin and $m/n$, i.e., the average number of balls among all bins. We provide tight estimates for three quantities: the lowest maximum load that could be achieved at time $m$, the lowest maximum load that could be achieved uniformly over the entire time interval $[m]:=1,2,cdots,m$, and the lowest emph{typical} maximum load that could be achieved over the interval $[m]$, where the typicality means that the maximum load holds for $1-o(1)$ portion of the times in $[m]$. We show that when $m$ and $n$ are sufficiently large, a typical maximum load of $(logn{)}^{1/2+o(1)}$ can be achieved with high probability, asymptotically the same as the optimal maximum load that could be achieved at time $m$. However, for any strategy, the maximal load among all times in the interval $[m]$ is $$ with high probability. A strategy achieving this bound is provided. An explanation for this gap is provided by our optimal strategies as follows. To control the typical load, we restrain the maximum load for some time, during which we accumulate more and more bins with relatively high load. After a while, we have to employ for a short time a different strategy to reduce the number of relatively heavily loaded bins, at the expanse of temporarily inducing high load in a few bins.

Recommendations

• The power of thinning in balanced allocation
• Load balancing under \(d\)-thinning
• Balanced Allocations
• Balanced allocations (extended abstract)
• Randomized allocation processes

Cites work

• An Introduction to the Theory of Point Processes
• An Introduction to the Theory of Point Processes
• Balanced allocation on graphs
• Balanced allocation: memory performance tradeoffs
• Balanced Allocations
• Balanced allocations: a simple proof for the heavily loaded case
• Balanced Allocations: The Heavily Loaded Case
• Balls into non-uniform bins
• Choice-memory tradeoff in allocations
• Fast concurrent access to parallel disks
• Graphical balanced allocations and the (1+ )-choice process
• scientific article; zbMATH DE number 5485459 (Why is no real title available?)
• scientific article; zbMATH DE number 5764855 (Why is no real title available?)
• scientific article; zbMATH DE number 1263199 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Large deviations techniques and applications.
• Load balancing under \(d\)-thinning
• Probability and Computing
• The power of thinning in balanced allocation

Cited in

(1)

• An improved drift theorem for balanced allocations

This page was built for publication: Long-term balanced allocation via thinning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126120)