Balanced Allocations: The Heavily Loaded Case

DOI10.1137/S009753970444435XMaRDI QIDQ5470738zbMATH OpenDBLPWikidataFDO

Authors Petra Berenbrink, Angelika Steger, Berthold Vöcking, Artur Czumaj

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S009753970444435X

zbMATH Keywords

balls-into-bins processesoccupancy problemsrandomized resource allocation

Mathematics Subject Classification ID

Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Balanced allocations: the heavily loaded case
• Balanced allocations: a simple proof for the heavily loaded case
• Balanced allocations (extended abstract)
• Balanced Allocations
• A class of balanced allocation problems
• Multidimensional balanced allocations
• Perfectly balanced allocation
• The power of thinning in balanced allocation
• Balance in resource allocation problems: a changing reference approach
• Efficient allocation of heterogeneous commodities with balanced transfers

Cited in

(40)

• On the k-orientability of random graphs
• Self-stabilizing repeated balls-into-bins
• Self-stabilizing balls and bins in batches. The power of leaky bins
• The power of thinning in balanced allocation
• Singletons for simpletons revisiting windowed backoff with Chernoff bounds
• Thresholds for extreme orientability
• On weighted balls-into-bins games
• The power of online thinning in reducing discrepancy
• Parallel load balancing on constrained client-server topologies
• Multidimensional balanced allocations
• A power-of-two-choices unbalanced allocation process
• Chains-into-Bins Processes
• Multiple-choice balanced allocation in (almost) parallel
• Balanced allocations: the heavily loaded case
• How asymmetry helps load balancing
• Graphical balanced allocations and the (1+ )-choice process
• Anonymity and k-Choice Identities
• Chains-into-bins processes
• Balanced allocation: memory performance tradeoffs
• Balanced allocation: patience is not a virtue
• Contention resolution with constant throughput and log-logstar channel accesses
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• On the power of choice for Boolean functions
• Balanced allocations: a simple proof for the heavily loaded case
• A generalization of multiple choice balls-into-bins: tight bounds
• The \((1 + {\beta})\)-choice process and weighted balls-into-bins
• STACS 2005
• Balls into bins via local search: cover time and maximum load
• Two-way chaining for non-uniform distributions
• Balanced Allocation: Patience Is Not a Virtue
• A simple approach for adapting continuous load balancing processes to discrete settings
• Perfectly balanced allocation
• Balanced Allocations with the Choice of Noise
• Long-term balanced allocation via thinning
• The Power of Filling in Balanced Allocations
• An asymptotically optimal algorithm for generating bin cardinalities
• Efficient assignment of identities in anonymous populations
• An improved drift theorem for balanced allocations
• Balanced allocations with the choice of noise
• A simple yet exact analysis of the MultiQueue

This page was built for publication: Balanced Allocations: The Heavily Loaded Case

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