Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256.

Is there an algorithm that allows every worker to pick all units of work for them to do, while:

  1. Every worker can pick up their work without extensive communication with other workers, other than knowing M, their own number n ≤ N and knowing all active workers' numbers ni.
  2. Every unit of work is assigned to one and only one worker at all times.
  3. Every worker gets the same amount of work, ± 1
  4. When a new worker joins, he knows which units of work are now assigned to him, and who to take them from, and after the transition is complete, previous conditions hold.
  5. When a worker leaves, remaining workers know who should take which of his units of work so that all the above conditions hold.
  6. When a worker n leaves or joins, no other workers should need to suddently exchange or transfer units of work between them, but only with the n.

Bonus points if it's possible to scale this algorithm up and down for other M, such as 128 or 512.

I'm pretty sure that the distribution exists and not too hard to find, given that the numbers are fairly small, but I'm interested in formula F(n, N, M, [ni]) which returns all the units of work belonging to n.

Flavour to make sense of the above: think of it as of fishermen checking their nets. There's 256 nets, there's ~60 fishermen, they have to check nets from time to time. Sometimes they're sick or take vacations. Retire and enlist. This work is never done, it never goes away, but it has to be distributed fairly.

Examples of solutions which don't satisfy all the points above:

Naive distribution, F(n, N, M, [ni]) = all i < M if i mod N == index(n in [ni]), fails 6. When a worker joins or leaves, all units of work after N-th have to be transferred.

Rendezvouz hashing fails 3. As number of workers grow, deviation of units of work per worker increases.

If this is proven impossible, you could probably relax either 3. for small constant number, or 6. for a small constant number of transferred units of work.

edit

I think there is a part of solution:

Suppose there's a table on the wall with M columns and N rows. Over every column a unit of work, every cell contains some worker's number n. In each column cell values are unique.

Workers scan every column top-down until they spot number of some worker currently present (skipping absent workers). That worker is assigned to this unit of work.

The only problem now is generating this schedule table. Here is an example of such table for N = 4, M = 8:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |; units of work
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 2 | 1 | 3 | 3 | 0 |; most preferred worker
| 1 | 0 | 0 | 3 | 3 | 1 | 0 | 3 |
| 2 | 2 | 1 | 1 | 2 | 2 | 2 | 2 |
| 3 | 3 | 3 | 0 | 0 | 0 | 1 | 1 |; last resort worker

any ideas on how it can be generated to satisfy 1.-6. for other N and M values?

So, I have found a solution that seems to work for M = 2k, k > 4, N <= M.

The table contains workers in order of increase of (n XOR u), where n is number assigned to worker (0 based) and u is number assigned to unit of work, 0-based.

When a worker joins, they are assigned some vacant number under N.

Sanity tests pass. I would call this xorula partitioning if it really works.

UPD Nope, it doesn't work, continuing search.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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