Load balancing with the multiple choice paradigm

Опубликовано 17 августа 2016, 22:38

Load balancing and resource allocation tasks are prevalent in the design of large data structures and distributed algorithms. The load balancing task can often be modeled by a simple process in which balls are placed sequentially into bins and the goal is to have all bins with approximately the same number of balls. A common approach used in many applications is simply to throw each ball to a random bin. The multiple choice paradigm is a simple, robust and surprisingly effective alternative method for achieving a better load balance. The main idea is to sample a small set of bins and place the ball in the least loaded bin within this set. I will survey a variety of variations for the scheme and show their possible applications and the main ideas that underlie the analysis.