分散処理を勉強した記録～その1～

分散処理周りの参考書籍が少なく、なんだかなあと思って自分なりに勉強した記録の備忘録です。
Nancy Lynchさんの本とか翻訳されてれば良かったんですが、
探した感じ見当たりませんでした。

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。
「何言ってんのコイツ」と思ったらそちらを参照してください。

なお、内容が膨大なので分割して記事にしていきます。

<分散システムのモデルについて>

これは完全グラフというらしいです。
プロセス同士がちゃんと通信路で結ばれています。
分散システムでは、
この「プロセス」と「通信路」から構成される「グラフ」でシステムを説明するらしいです。
ちなみに、正確にはプロセスの記号は四角いのですが便宜上丸くしています。

<システムは順番通りに処理するか？>

普通のシステムは順番通りにちゃんと処理されますね。
プロセス1からプロセス2宛にメッセージを発信した順番に
プロセス2がメッセージを受信するハズです。

ところがどっこい、現実的な話をすると間にルータとか色んな機器が挟まること、ありますよね？
このルータのどの経路を辿ったのかとか通信速度とか諸々の事情が重なって、
プロセス1からプロセス2宛にメッセージを発信した順番に
プロセス2がメッセージを受信する
ということが保証されません。

<同じ条件で同じ命令が実行されるか？>

普通のアルゴリズムの定義を
「変数」と「メッセージ」が分かれば、
「プロセス」はどの「命令」をすればいいのかが分かる。
つまり、変数とメッセージがあればプロセスのやることが決まり切ってるのが
「普通のアルゴリズム」としましょう。

「普通」じゃないアルゴリズムは命令の候補があって決まり切りません。
同じ変数とメッセージの組み合わせを与えてもどの命令が実行されるかはランダムです。

分散システムではこういうややこしい問題を解くために、
分散アルゴリズムを使います。

<分散アルゴリズムの評価方法>

プロセスがn個あるシステムで、
各プロセスが全員にメッセージを送信したいとします。

パターン1:とりあえず全員に送信する

全員にメッセージを送信します。
受信は次のステップで行います。

2ステップで完了しました。
では、メッセージの量はどうでしょうか。

n個のプロセスが(n-1)分のメッセージを送信するので、
O(n^2)です。

分散アルゴリズムはステップ数とメッセージの量で性能を評価します。

パターン2:代表に送信してもらう

ここではプロセス1を代表として扱います。
各プロセスは、プロセス1にメッセージを送信します。

プロセス1は、受信したメッセージを各プロセスに送信します。

各プロセスは、プロセス1からのメッセージを受信します。

パターン2では3ステップ必要です。
メッセージの量は、

(n - 1)個のプロセスがメッセージを送受信するので、2(n - 1)となります。
O(n)ですね。

パターン1はステップ数は少ないですが、オーダーが大きく、
パターン2はステップ数は多いですが、オーダーが小さいです。

今回はここまでです。ありがとうございました。