分散アルゴリズム
分散アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/20 20:08 UTC 版)
分散アルゴリズム（ぶんさんアルゴリズム、英語: Distributed algorithm）とは、相互接続されたプロセッサにより構成されるハードウェア上で実行するために設計されたアルゴリズムである。分散アルゴリズムは分散コンピューティングの多くの応用分野において使われ、その例として、通信、科学計算、分散情報処理、リアルタイムプロセス管理などがある。分散アルゴリズムによって解決された標準的な問題として、リーダー選出、合意、分散検索、全域木生成、ミューテックス、リソース割り当てなどがある[1][2]。
典型的な分散アルゴリズムは、並列に実行され、アルゴリズムの各部が独立したプロセッサ上で同時に実行され、アルゴリズムの他の部分については限定的な情報しか持たない。分散アルゴリズムを開発し、実装する上での大きな課題となるのが、プロセッサ障害が発生し、通信接続が不確実であるような環境において、アルゴリズムの独立した部分の動作を統制することである。与えられた問題に対し、適切な分散アルゴリズムを選択することは、問題の特徴と、アルゴリズムが実行されるシステムの特徴の両方に依存する。ここでシステムの特徴とは、プロセッサの性能や、通信接続の障害、可能なプロセス間通信の種類、プロセス間の同期を行う際の精度などを指す[1]。
標準的な問題
- アトミックコミット
- アトミックコミットとは異なる変更の集合が一つの処理として実行されるような処理のことである。もしアトミックコミットが成功すれば、全ての変更が実行されたことを意味する。もしアトミックコミットが完了するまでに障害があった場合、"コミット"が中止され、どの変更も実行されない。
- アトミックコミットプロトコルを実現するアルゴリズムとして、2相コミットプロトコルおよび、3相コミットプロトコルがある。
- 合意
- 合意アルゴリズムはいくつかのプロセスが共通の決定に合意する問題を解くものである。
- より詳細には、合意プロトコルは以下の4つの特徴を備えなければならない。
-
- 終了: 全ての正常なプロセスはある値を決定する。
- 有効性: もし全てのプロセスが同じ値
分散アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/24 15:14 UTC 版)
「レイヤ4スイッチ」の記事における「分散アルゴリズム」の解説
ラウンドロビン 単純に順番ごとにセッションを分散する方式。最も無難な方式であり、負荷も少ないが応用性も低い。 ハッシュ ハッシュ関数を用いて、ソースIPアドレスを元にサーバを選択し、なるべく同じユーザは同じサーバへ接続するようにする意図がある場合に好んで用いられる方式。だが、プロキシ経由などでNAT越えをして接続するユーザが極端に多いと、うまくバランスされないことになる。 リーストコネクション カレントセッション数の最も少ないサーバに接続する方式。セッションを開放したサーバに優先接続されるために、分散効率が良い。ただし、能力差のあるサーバを使って分散構成を組む場合は、能力の大きいサーバの稼動効率が落ちる。応答が障害レベルまでに遅くなったサーバに、優先接続されてしまうリスクもある。 リーストトラフィック トラフィックが最も少ないサーバーに接続する方式。FTPサーバなどの分散に適している。経路帯域の分散も兼ねることになる。 リーストプロセッシング 負荷が最も少ないサーバに接続する方式。サーバにエージェントのインストールが必要となる。 ファーストアンサー 最も応答の早いサーバに接続する方式。数年のスパンで拡張されるシステムであれば、世代の異なるサーバを使うことにならざるを得ず、サーバ単体能力に差が出て来る。こういった場合には、ファーストアンサーが有効である。 L7分散 HTTPパケットのCookie情報などを元に分散する方式。この時点でL4スイッチではなく、アプリケーション(L7)スイッチとしての動作になるが、2000年時点で殆どのL4スイッチに実装されている。ハッシュ方式と合わせて分散性を高めるために使われたり、マルチセッション時に同一サーバへの接続を維持したい場合に有効である。
※この「分散アルゴリズム」の解説は、「レイヤ4スイッチ」の解説の一部です。
「分散アルゴリズム」を含む「レイヤ4スイッチ」の記事については、「レイヤ4スイッチ」の概要を参照ください。
分散アルゴリズムと同じ種類の言葉
- 分散アルゴリズムのページへのリンク
