Tight bounds for parallel randomized load balancing, extended abstract

DOI10.1145/1993636.1993639MaRDI QIDQ5419070zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Roger Wattenhofer

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic boundsload balancingrandomized allocation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Tight bounds for parallel randomized load balancing
• scientific article; zbMATH DE number 1263199
• Allocating weighted jobs in parallel
• Parallel randomized load balancing
• Parallel randomized load balancing: a lower bound for a more general model

Cited in

(20)

• Singletons for simpletons revisiting windowed backoff with Chernoff bounds
• Derandomizing local distributed algorithms under bandwidth restrictions
• Self-stabilizing local k-placement of replicas with local minimum variance
• Load balancing of temporary tasks in the \(\ell _{p}\) norm
• Parallel load balancing on constrained client-server topologies
• A load balancing strategy for parallel computation of sparse permanents.
• Tight bounds for parallel randomized load balancing
• Tight Analysis of Parallel Randomized Greedy MIS
• Revisiting Randomized Parallel Load Balancing Algorithms
• Reducing price of anarchy of selfish task allocation with more selfishness
• scientific article; zbMATH DE number 1263231 (Why is no real title available?)
• scientific article; zbMATH DE number 742953 (Why is no real title available?)
• A generalization of multiple choice balls-into-bins: tight bounds
• Parallel randomized load balancing: a lower bound for a more general model
• Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game
• Deterministic and randomized algorithms for distributed on-line task assignment and load balancing without load states information
• Distributed dispatching in the parallel server model
• An improved drift theorem for balanced allocations
• Balanced allocations with the choice of noise
• Sub-logarithmic distributed algorithms for metric facility location

This page was built for publication: Tight bounds for parallel randomized load balancing, extended abstract

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