3

ゴシップベースのプロトコルでは、すべてのノードがメッセージに感染することをどのように保証しますか?

ランダムな数のノードを選択してこれらのノードにメッセージを送信し、これらのノードが同じことを行った場合、一部のノードがメッセージを受信しない可能性があります。

計算はできませんでしたが、小さいようです。ただし、システムが長時間稼働していると、ある時点で 1 つのノードが運悪く残ります。

4

3 に答える 3

2

次の 2 つの理由から、答えるのが少し難しいです。

  1. ゴシップベースのプロトコルは実際にはありません。せいぜい、ゴシップベースのアルゴリズムのファミリがあります。

  2. アルゴリズムは、実際には特定の仮定の下でのみ感染を保証します。たとえば、あなたが言うように、「システムが長時間実行されている」場合、特定のリンクが指数関数的なプロセスで永続的に失敗する場合 (非常に可能性の高いシナリオ)、確率 1 で一部のノードが完全に分離され、プロトコルはありません。それを克服できます。

ただし、IIUC さんは、次の前提でプロトコルについて質問しています。

  1. ノードの任意のグループV' ⊂ Vに対して、アクティブなリンクu ∈ V' → v ∈ V ∖ V' があります。

ここに画像の説明を入力

  1. 各ノードは、状態、他のノードによる選択、合計更新状態などに関係なく、各ステップで均一にd個の隣接ノードを選択します。

ここに画像の説明を入力

これらの条件下では、あなたが提起した問題の確率は 0 になります。

感染は、 iノードが感染した場合にシステムが状態iになるマルコフ連鎖と考えることができます。何らかの変化がs ∈ Vで発生したと仮定すると、システムは状態iで開始します。

  • プロパティ 1. により、 i個の感染したノードからn - i 個の他のノードの 1 つへのリンクがあります。

  • プロパティ 2. により、このリンクを選択する確率は少なくとも1 / nです。これは、リンクがたまたまカットを横切るノードの隣接ノードは最大でn 個ですが、カットを横切る隣接ノードは少なくとも 1 つあるためです。その選択が完全にステートレスで情報がない場合でも、それがこのネイバーを選択する可能性があります。

したがって、jステップでこれが発生しない確率は(1 - d/n) jです。Union Boundを使用すると、任意の状態iでこれが発生する確率は最大でn (1 - 1/n) jです。j = n 2とすると、これはne - nになります。j = n 3とすると、これはne - n 2になります。等。

(もちろん、ゴシップ アルゴリズムの感染ははるかに早く発生します。これは、考えられる最悪の条件の上限です。)

そのため、システムが十分長く実行されている場合、一部のノードが感染しない可能性は (非常に急速に) 0 に減少します。Anti-Entropy Gossip Protocolの場合、これで十分です。他のいくつかのプロトコルでは、ご想像のとおり、更新のために一部のノードが失われる可能性があります。

于 2015-07-04T22:39:49.640 に答える
0

あなたは問題を理解していないため、回答を提供できません (したがって、質問があいまいです)。

  • ネットワークのトポロジーは不明ですが、答えはそれに依存します
  • アルゴリズムの停止条件は何ですか? 止まるか止まらないか

特定のノードが他のすべてのノード (トポロジ) に接続されており、各ノードがメッセージを受信した場合に同じアクションを実行するとします。

問題をより小さなサブ問題に単純化することができます (これが分割とインペラのアプローチです)。任意のノードが 1 回だけ試行 (つまりi = 1) を実行すると想像してください。

任意のノードが受信者を完全にランダムに選択し、この操作が無限に行われるため、最終的にすべてのノードがメッセージを受信します。特定の信頼度 (メッセージを受信したノードの比率 / すべてのノードの数) に到達するために必要な反復回数は、あなた次第です。

これを取得したら、繰り返し試行するのiは簡単です。

于 2015-09-04T18:32:31.653 に答える
0

あなたがやろうとしていることを少しシミュレーションしました。 http://jsfiddle.net/ut78sega/

function gossip(nodes, tries, startNode, reached) {
    var stack = [startNode, tries];
    while(stack.length > 0) {
        var ttl = stack.pop();
        var n = stack.pop();
        reached[n] = 1;
        if(ttl <= 0) { continue; }
        for(var i=0; i < ttl; i++) {
            stack.push(Math.floor(Math.random() * nodes), ttl - 1);
        }
    }
    return reached;
}
  • node - 総ノード数
  • 試行回数- ランダム選択の開始量
  • startNode - 最初のメッセージを取得するノード
  • 到達- 現在のシミュレーションによって到達されたノードのハッシュ セット

再帰の各レベルで、試行回数が 1 ずつ減ります。65536 (2^16) ノードを 100% カバーするには、最大 9 回の試行が必要です。

于 2015-09-04T18:47:15.747 に答える