Tight bounds for parallel randomized load balancing

DOI10.1007/s00446-014-0225-4zbMath1356.68018OpenAlexW2116269179MaRDI QIDQ287991

Christoph Lenzen, Roger Wattenhofer

Publication date: 23 May 2016

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/104872

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (3)

Stochastic coordination in heterogeneous load balancing systems ⋮ A lower bound on the queueing delay in resource constrained load balancing ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Allocating weighted jobs in parallel
• Exploiting storage redundancy to speed up randomized shared memory simulations
• Approximate equilibria and ball fusion
• Efficient PRAM simulation on a distributed memory machine
• On weighted balls-into-bins games
• Randomized allocation processes
• The round complexity of distributed sorting
• Parallel Randomized Load Balancing: A Lower Bound for a More General Model
• Revisiting Randomized Parallel Load Balancing Algorithms
• How asymmetry helps load balancing
• Distributed Selfish Load Balancing
• Balanced allocation on graphs
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Locality in Distributed Graph Algorithms
• Balanced Allocations
• Balls and bins: A study in negative dependence
• The Tree Model for Hashing: Lower and Upper Bounds
• The log-star revolution
• Hundreds of impossibility results for distributed computing
• Load balancing without regret in the bulletin board model
• Optimal deterministic routing and sorting on the congested clique
• A new technique for distributed symmetry breaking
• Tight bounds for parallel randomized load balancing
• Distributed verification and hardness of distributed approximation
• What cannot be computed locally!
• Distributed MST for constant diameter graphs

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