2

n 台のコンピューターがあるとします。それぞれに整数のセットがあります。各コンピューターに同じセットはありません。

つまり、コンピュータ 1 には {1,2,3,4}、コンピュータ 2 には {4, 5,10,20,21}、コンピュータ 3 には {-10,3,5} などがあります。

このデータを複製して、すべてのコンピューターがすべての整数を持つようにします。つまり、すべてのコンピューターが {-10,1,2,3,4,5,10,20,21} を持つようにします。

各コンピューターが送信するメッセージの数を最小限に抑え、時間も最小限に抑えたいと考えています。(つまり、コンピュータ 1 が最初に全員と通信し、不足しているデータを取得し、次にコンピュータ 2 が同じことを行うというシリアル アプローチを避けます。

これを行う効率的な方法は何ですか？

ありがとう。

4

4 に答える 4

1

最小限のアプローチは次のとおりです。すべてのコンピューターが 1 つの (マスター) コンピューターに情報を送信し、結果を取得します。

信頼性のために、少なくとも 2 台のコンピューターをマスター コンピューターと見なすことができます。

仮定:

  1. 合計 n 台のコンピューター
  2. コンピューターの 1 つがマスターと見なされます

アルゴリズム :

  1. すべてのコンピュータinput-infoがマスターに送信 (合計 n-1 メッセージ)
  2. マスターは情報を処理します
  3. マスターresult-infoがすべてのコンピューターに送信します (合計 n-1 メッセージ)

信頼性 ：

このアルゴリズムに基づくシステム全体の障害は、すべてのマスターに障害が発生した場合にのみ発生します。

効率 ：

With 1 master  , total messages : 2 * (n-1)
With 2 masters , total messages : 2 * 2 * (n-1)
With 3 masters , total messages : 3 * 2 * (n-1)
于 2013-10-25T23:20:20.387 に答える
0

これを 2*n - 2 手で行う 1 つの方法を次に示します。リンク リスト内のノードとしてマシンをモデル化し、1..n から番号を付けます。

  1. ノード 1 がすべてのデータを 1 つのメッセージでノード 2 に送信できるようにします。
  2. ノード 2 は、ノード 1 が送信したメッセージを記憶し、その内容とノード 1 の内容を結合して、統合されたメッセージをノード 3 に送信します。次に、ノード 2 はノード 3 からの応答を待ちます。
  3. ノード 3 は、ノード 'n' に到達するまで上記と同じことを行います。ノード 'n' には完全なセットが含まれています。
  4. ノード「n」は、ノード「n - 1」が送信したメッセージをすでに認識しているため、差分をノード「n - 1」に送り返します。
  5. ノード 'n - 1' は上記のように結合を実行します。ノード 'n - 2' のメッセージを (上記のステップ 2 で) 記憶しているため、差分をノード 'n - 3' に送り返すことができます。

等々。

上記がネットワークで送信される 2 * (n - 1) メッセージにつながることを示すのは複雑ではないと思います。

各ノードに固有の要素があると考えると、2n - 2 が必要であることが証明できると思います。2n - 2 が必要であることを証明するには、数学的帰納法を少し練習する必要があります。

于 2013-10-25T22:47:07.457 に答える
0

ええと、これを行うシステムがすでにあり、広く採用され、十分に文書化され、広く利用可能であり、おそらく完璧ではありませんが (完璧のさまざまな定義について)、実用的です。

それは RSync と呼ばれます。

ここから開始できます: http://www.samba.org/~tridge/phd_thesis.pdf

于 2013-10-25T22:52:18.567 に答える