フェイルオーバによる連続作業分散アルゴリズム

たとえば、 N≤64M = 256
のように、N人の作業者とM個の作業単位が存在するシステムがあるとします。

すべての作業者が作業のすべての単位を選択できるようにするアルゴリズムはありますか?

  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.

128512 などの M
のためにこのアルゴリズムを上下に拡大することができる場合のボーナスポイント。

数値がかなり小さいので、配布が存在し、見つけるのが難しくないと確信していますが、式
F(n、N、M、[ni]) n に属するすべての作業単位を返します。

上記のことを理解するための風味:ネットをチェックしている漁師のように考えてください。
256のネットがあり、60名の漁師がいます。ネットをチェックする必要があります。時には病気になったり、休暇を取ることもあります。退職して入隊する。この仕事は決して行なわれず、決して去ることはありませんが、公平に配らなければなりません。

上記のすべての点を満たさないソリューションの例:

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.

これが不可能であることが判明した場合は、小定数の場合は3.を、譲渡単位の小規模な定数の場合は6.を緩和することができます。

編集

私は解決策の一部があると思う:

M の列と N の行を持つテーブルが壁にあるとします。
すべての列に作業単位があり、すべてのセルにはある労働者の番号nが含まれています。各列のセル値は一意です。

労働者は現在存在する一部の労働者の数を特定するまで、各列のトップダウンをスキャンします(不在の労働者はスキップします)。その作業者はこの作業単位に割り当てられます。

唯一の問題は、このスケジュール表を生成することです。次に、 N = 4M =
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

それをどのように生成して、1.-6を満たすことができるかについてのアイデア。他のN値とM値については?

ベストアンサー

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

この表には、(n XOR
u)の増加順に従業員が含まれています.nは作業者(0ベース)に割り当てられた番号で、uは作業ユニット(0ベース)に割り当てられた番号です。

作業員が参加すると、Nの下に空き番号が割り当てられます。

サニティテストは合格です。実際に動作する場合は、このxorulaパーティショニングと呼んでいます。

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

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です