How asymmetry helps load balancing

DOI10.1145/792538.792546zbMath1325.68254OpenAlexW2061468734MaRDI QIDQ3452503

Berthold Vöcking

Publication date: 12 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/792538.792546

zbMATH Keywords

probabilistic analysisrandomized algorithmsballs and bins processes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items (33)

Efficient set intersection with simulation-based security ⋮ Balanced Allocation: Patience Is Not a Virtue ⋮ Tight bounds for parallel randomized load balancing ⋮ Sharp load thresholds for cuckoo hashing ⋮ New techniques and tighter bounds for local computation algorithms ⋮ On weighted balls-into-bins games ⋮ Graphical balanced allocations and the (1 + β)-choice process ⋮ Parallel load balancing on constrained client-server topologies ⋮ Scalable Load Balancing in Networked Systems: A Survey of Recent Advances ⋮ Balanced allocation on hypergraphs ⋮ An improved version of cuckoo hashing: average case analysis of construction cost and search operations ⋮ Unnamed Item ⋮ Balls into bins with related random choices ⋮ Efficient set operations in the presence of malicious adversaries ⋮ Revisiting randomized parallel load balancing algorithms ⋮ Chains-into-bins processes ⋮ Self-stabilizing repeated balls-into-bins ⋮ Chains-into-Bins Processes ⋮ Balancing sums of random vectors ⋮ Balanced allocation on dynamic hypergraphs ⋮ A generalization of multiple choice balls-into-bins: tight bounds ⋮ Layered hashing algorithm for real-time systems ⋮ Parallel randomized load balancing: a lower bound for a more general model ⋮ Scalable Multi-party Private Set-Intersection ⋮ Balls into bins via local search: Cover time and maximum load ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses ⋮ Balanced Allocation on Graphs: A Random Walk Approach ⋮ On the \(k\)-orientability of random graphs ⋮ The power of thinning in balanced allocation ⋮ Revisiting Randomized Parallel Load Balancing Algorithms ⋮ Singletons for simpletons revisiting windowed backoff with Chernoff bounds ⋮ Two-way chaining for non-uniform distributions

This page was built for publication: How asymmetry helps load balancing