Balanced allocation: patience is not a virtue

DOI10.1137/1.9781611974331.CH48MaRDI QIDQ4575626zbMATH OpenOpenAlexFDO

Authors Amanda Redlich, Eli Upfal, John Augustine, William K. jun. Moses

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08298

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm $mathsfGreedy[d]$ of Azar et al. places each ball by probing $d>1$ random bins and placing the ball in the least loaded of them. With high probability, the maximum load under $mathsfGreedy[d]$ is exponentially lower than the result when balls are placed uniformly randomly. V"ocking showed that a slightly asymmetric variant, $mathsfLeft[d]$, provides a further significant improvement. However, this improvement comes at an additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called $mathsfFirstDiff[d]$ that combines the simplicity of $mathsfGreedy[d]$ and the improved balance of $mathsfLeft[d]$. The key idea in $mathsfFirstDiff[d]$ is to probe until a different bin size from the first observation is located, then place the ball. Although the number of probes could be quite large for some of the balls, we show that $mathsfFirstDiff[d]$ requires only at most $d$ probes on average per ball (in both the standard and the heavily-loaded settings). Thus the number of probes is no greater than either that of $mathsfGreedy[d]$ or $mathsfLeft[d]$. More importantly, we show that $mathsfFirstDiff[d]$ closely matches the improved maximum load ensured by $mathsfLeft[d]$ in both the standard and heavily-loaded settings. We further provide a tight lower bound on the maximum load up to $O(logloglogn)$ terms. We additionally give experimental data that $mathsfFirstDiff[d]$ is indeed as good as $mathsfLeft[d]$, if not better, in practice.

Recommendations

• Balanced Allocation: Patience Is Not a Virtue
• Balanced allocations (extended abstract)
• How asymmetry helps load balancing
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocations: the heavily loaded case

Cited in

(5)

• The power of thinning in balanced allocation
• A power-of-two-choices unbalanced allocation process
• Studying Balanced Allocations with Differential Equations
• Balanced Allocation: Patience Is Not a Virtue
• The Power of Filling in Balanced Allocations

This page was built for publication: Balanced allocation: patience is not a virtue

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