Load balancing with the multiple choice paradigm

Speaker  Udi Wieder

Affiliation  MSR SVC

Host  mcastro

Duration  01:09:25

Date recorded  13 December 2010

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.

©2010 Microsoft Corporation. All rights reserved.
> Load balancing with the multiple choice paradigm