Tight Load Balancing via Randomized Local Search

arXiv1706.09997MaRDI QIDQ6288480FDOQ6288480

Authors: Petra Berenbrink, Peter Kling, Christopher Liaw, Abbas Mehrabian 

Publication date: 29 June 2017

Abstract: We consider the following balls-into-bins process with $n$ bins and $m$ balls: each ball is equipped with a mutually independent exponential clock of rate 1. Whenever a ball's clock rings, the ball samples a random bin and moves there if the number of balls in the sampled bin is smaller than in its current bin. This simple process models a typical load balancing problem where users (balls) seek a selfish improvement of their assignment to resources (bins). From a game theoretic perspective, this is a randomized approach to the well-known Koutsoupias-Papadimitriou model, while it is known as randomized local search (RLS) in load balancing literature. Up to now, the best bound on the expected time to reach perfect balance was $Oleft({(lnn)}^2+ln(n)cdot{n}^2/might)$ due to Ganesh, Lilienthal, Manjunath, Proutiere, and Simatos (Load balancing via random local search in closed and open systems, Queueing Systems, 2012). We improve this to an asymptotically tight $Oleft(ln(n)+n^2/might)$. Our analysis is based on the crucial observation that performing "destructive moves" (reversals of RLS moves) cannot decrease the balancing time. This allows us to simplify problem instances and to ignore "inconvenient moves" in the analysis.

This page was built for publication: Tight Load Balancing via Randomized Local Search

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