Tight bounds for parallel randomized load balancing
Given a distributed system of n balls and n bins, how evenly can we distribute the balls to the bins, minimizing communication? The fastest non-adaptive and symmetric algorithm achieving a constant maximum bin load requires Θ(loglogn) rounds, and any such algorithm running for r∈O(1) rounds incurs a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2016
|
| Online Access: | http://hdl.handle.net/1721.1/104872 |