2
$\begingroup$

I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize the maximum load of any bin. However there is something I don't understand.

Why not just keep a priority queue of the loads of the bins and allocate any new ball to the bin with the lowest current load? This seems to give you the optimal load without any complications.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Ah, but there's significant overhead involved with keeping track of each bin's current load. If you have a thousand bins operating independently of each other and independently of you, how do you know what each bin's load is at any given time? Guessing is an option, but then how much better than random are you doing? Asking everybody is another option, but asking people takes time from everybody, including you. $\endgroup$ – Patrick87 May 20 '13 at 20:20
  • $\begingroup$ Oh so you don't assume that the bins only get balls that you allocate? $\endgroup$ – Thomas May 20 '13 at 20:28
  • $\begingroup$ Sure you can. But how do you know when the bin dequeues a ball? In realistic load balancing applications - i.e., scheduling tasks to processors - I think a common assumption is that the processors begin processing immediately, and when they're done with a task, their load is reduced. You're trying to reduce the total time, after all, not the fairness of allocation of tasks to processors. $\endgroup$ – Patrick87 May 21 '13 at 15:37
2
$\begingroup$

You are correct that using a priority queue is a good idea. It doesn't give an optimal answer though. (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.) This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal. See, for example, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. The wikipedia page on Job Shop Scheduling also gives some information.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In an unweighted balls into bins model, if you always allows allocate to the least loaded bin, the max difference between loads is $1$ isn't it? I see it is hard if the balls have weights. $\endgroup$ – Thomas May 20 '13 at 20:30
  • $\begingroup$ If the jobs all have the same length then the optimal algorithm is to just assign round-robin, priority-queue is total overkill. It sounds like the point of this is really to learn about how to calculate collision probabilities in hash tables. $\endgroup$ – Wandering Logic May 20 '13 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.