Speaker Udi Wieder
Affiliation MSR SVC
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.