6
$\begingroup$

The following is a fun problem we stumbled into today.

We have work we wish to distribute on machines $1..n$. Each piece of work is given a list of machines to try, in order. If any machine fails, the work is passed on to the next machine. We desire to make this as fair as possible. That is to say, all work is initially divided as evenly as possible. If any one machine fails, the leftover work should be distributed among all remaining machines as close to equally as possible. If two machines fail, we wish the same property to hold, all the way up to $n-1$ machines.

If we generate all permutations, and assign each piece of work one of the permutations (cycling through after exhausting them), in sequence, then this property should hold, assuming a large enough quantity of work.

But now we add a requirement that we want good results for small quantities of work, and generally quantities of work that aren't evenly divided by the number of permutations, and things get harder. We want a suitable ordering on permutations such that for any $m$, the optimal distribution/optimal redistribution property holds as closely as possible.

Here's an example of the first four elements of an optimal distribution/redistribution list for four machines:

a) 1 2 3 4
b) 2 1 4 3
c) 3 4 1 2
d) 4 3 2 1

Trivially, if any one number is removed, its work goes to one other location. Similarly, if any three numbers are removed, all work falls to the remaining machine. However, also note that for any choice of two failures, the remaining work remains evenly distributed. I.e. if 1 and 4 fail, list $a$ falls back to 2, and the list $d$ falls back to 3, preserving fairness.

Given an optimal list of length $n$ consisting of choice lists also of length $n$, we can treat it as a matrix. It should, I think, always have the property that there is not only only one entry of any number per row, but also per column (shades of generalized soduku). If this is the case, then by holding the first column fixed, we can generate all remaining permutations (and optimal lists of length $n$) by taking permutations on the remaining columns.

Has this problem been studied before? Under what name? Is the production of a list that preserves optimal distribution/redistribution for any $m$ possible? How close can we get? What is the nicest algorithm for it?

Or, more basically, what is the simplest algorithm for generating an optimal distribution list of length $n$?

$\endgroup$
  • 1
    $\begingroup$ Don't you get fairness (even in case of inhomogeneous hosts) if you let machines pull work rather than push it to them? $\endgroup$ – Raphael Oct 13 '11 at 11:49
  • $\begingroup$ I'm not sure if I understand the problem correctly, but are you looking for Latin squares? en.wikipedia.org/wiki/Latin_square $\endgroup$ – Yoshio Okamoto Oct 13 '11 at 13:45
  • $\begingroup$ A latin square isn't sufficient (and I'm not sure its necessary). For example, look at the bottom left example on the linked wikipedia page. If 1 and 2 fail, that leaves 3 jobs for machine 3, and 1 each for 4 and 5. Just using latin squares was in fact my initial naive approach, until it was pointed out that this was still not optimally fair. $\endgroup$ – sclv Oct 13 '11 at 14:47
  • $\begingroup$ And yes, you can get fairness easily if you allocate work dynamically though any number of schemes. The fun puzzle element arises when you try to ensure fairness statically up-front. $\endgroup$ – sclv Oct 13 '11 at 14:48

Your Answer

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

Browse other questions tagged or ask your own question.