0

Quorumの概念に基づく分散型相互排除アルゴリズムを研究しています。

引用: Coterie C は集合の集合として定義され、各集合 g ∈ C は定足数と呼ばれます。

次のプロパティは、グループ内の定足数に適用されます。

1) 交差特性: クォーラム g, h ∈ C ごとに、g ∩ h= ∅. たとえば、セット {1,2,3}、{2,5,7}、および {5,7,9} は、最初と 3 番目のセットに共通の要素がないため、グループ内の定足数になることはできません。

2) 最小性: g ⊇ h となる集団 C には定足数 g, h が存在しない。たとえば、セット {1,2,3} と {1,3} は、最初のセットが 2 番目のセットのスーパーセットであるため、コテリーの定足数になることはできません。

分散システム内の一連のノードが与えられた場合、そのようなノードからそのようなコテリまたはクォーラムのセットがどのように形成されるかを知りたいですか? これを行うためのアルゴリズムまたは手法は何ですか?

更新: 問題を言い換えると、「「N」個のノードが与えられた場合、そのうちの 2 つが共通の「J」個のノードを持つように「K」個の定足数を形成する最良の方法は何ですか?

4

1 に答える 1

0

読み取りまたは書き込みの単純なアルゴリズムは、クォーラム内のすべてのノードから読み取り、クォーラム内のすべてのノードに書き込む必要があるというものです。このようにして、システム内の他のすべての関係者が最新の書き込み項目を確実に読むことができます。

あなたのタイトルは相互排除に関するものであるため、システム内のピアは、クォーラム内のすべてのノードにリソースへのロックを要求できます。最初のルールにより、他のピアはクォーラム全体からロックを取得できません。

私が知る限り、実際にはランダムなノードに接続してクォーラムとして使用しn/2 + 1ますが、ご覧のとおり、より洗練されたディストリビューションを定義して、クォーラムを小さくすることもできます。これにより、パフォーマンスが再び向上します。

アップデート：

このような 9 台のサーバーを持つ定足数の例は、次のようになります。

  • 2 つの定足数: サーバー 1 ～ 5 が 1 つの定足数であり、5 ～ 9 が別の定足数 (単純過半数)
  • 3 つの定足数: サーバー 1、2、3、4。4,5,6,7; 7,8,9,1 は 3 つの異なる定足数になる可能性があります
  • より多くの定足数: サーバー 1、2、3。3,4,5; 5,6,1; 6,7,3; 8,3,1; 9,3,1; 6 つの異なる定足数になる可能性があります。ただし、ここでは、サーバー 1 と 3 がそれぞれ 4 つのクォーラムの一部であり、この理由でより多くのトラフィックを処理する必要があることがわかります。
  • 1,2 のような定足数を作成することもできます。1,3; 1,4; 1,5; 1,6; 1,7; 1,8; 1,9; しかし、これは単にサーバー 1 を持っているのと同じです。
于 2014-03-05T14:52:10.240 に答える