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:
- Every worker can pick up their work without extensive communication with other workers, other than knowing
M, their own number
n ≤ Nand knowing all active workers' numbers ni.
- Every unit of work is assigned to one and only one worker at all times.
- Every worker gets the same amount of work,
- 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.
- When a worker leaves, remaining workers know who should take which of his units of work so that all the above conditions hold.
- When a worker
nleaves or joins, no other workers should need to suddently exchange or transfer units of work between them, but only with the
Bonus points if it's possible to scale this algorithm up and down for other
M, such as
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
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:
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.
I think there is a part of solution:
Suppose there's a table on the wall with
M columns and
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?