Load balancing with the multiple choice paradigm

  • Udi Wieder | MSR SVC

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.

    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Udi Wieder

      Udi Wieder

Watch Next