Near-perfect load balancing by randomized rounding

We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and minimum load. In every time-step paired processors balance their load as evenly as possible. The direction of the excess token is chosen according to a randomized rounding of the participating loads.

Authors

• Tobias Friedrich 0001
• Thomas Sauerwald

Keywords

• load balancing
• randomized rounding