ModelsEdit
コンピュータを使って自動化したい作業の多くは、質問をしてコンピュータが答えを出すという質問応答型のものです。 理論計算機科学では、このような作業を「計算問題」と呼びます。 形式的には、計算問題は、インスタンスと各インスタンスに対する解答から構成されます。
理論計算機科学では、どのような計算問題がコンピュータを使って解決できるか（計算可能性理論）、どのように効率よく解決できるか（計算複雑性理論）を理解することを目指しています。 伝統的には、与えられたインスタンスに対して正しい解を生成するアルゴリズムを設計できれば、コンピュータを使って問題を解くことができると言われています。 このようなアルゴリズムは、汎用コンピュータ上で動作するコンピュータプログラムとして実装することができる。プログラムは、問題のインスタンスを入力として読み込み、何らかの計算を行い、解を出力として生成する。
同時並列・分散コンピューティングの分野では、同様の問題を、複数のコンピュータや、相互作用するプロセスのネットワークを実行するコンピュータの場合にも研究します。 しかし、並列・分散システムの場合、「問題を解決する」とは何を意味するのかは、全く明らかではありません。例えば、アルゴリズム設計者のタスクは何か、並列・分散システムは逐次型汎用コンピュータの何に相当するのか、などです。
以下の議論は、複数のコンピュータの場合に焦点を当てていますが、問題の多くは単一のコンピュータ上で実行される同時実行プロセスにも共通しています。
一般的には次の3つの視点が用いられます。 アルゴリズム設計者は、各プロセッサで実行されるプログラムを選択します。
メッセージパッシングモデルにおける並列アルゴリズム
- アルゴリズム設計者は、ネットワークの構造や各コンピュータが実行するプログラムを選択します。
- ブール回路やソートネットワークなどのモデルが使用されます。 ブール回路は、コンピュータ ネットワークと見なすことができます。各ゲートは、極めて単純なコンピュータ プログラムを実行するコンピュータです。
メッセージパッシングモデルにおける分散アルゴリズム
- アルゴリズム設計者は、コンピュータプログラムを選択するだけです。 すべてのコンピュータが同じプログラムを実行する。 ネットワークの構造にかかわらず、システムは正しく動作しなければなりません。
- 一般的に使用されるモデルは、ノードごとに1つの有限状態マシンを持つグラフです。
分散アルゴリズムの場合、計算問題は一般的にグラフに関連しています。 多くの場合、コンピュータネットワークの構造を記述したグラフが問題のインスタンスとなります。
An exampleEdit
与えられたグラフGのカラーリングを求めるという計算問題を考えてみます。分野によって次のようなアプローチが考えられます。 並列アルゴリズム
- ここでも、グラフGは文字列としてエンコードされています。 しかし、複数のコンピュータが同じ文字列に並行してアクセスすることができます。 各コンピュータは、グラフの一部分に注目し、その部分のカラーリングを生成するかもしれません。
- 複数のコンピュータの処理能力を並列に利用する高性能な計算が中心となります。
分散アルゴリズム
- グラフGは、コンピュータネットワークの構造です。 初期状態では、各コンピュータはグラフG内の直近の隣人についてしか知らず、Gの構造についてより詳しく知るためには、コンピュータ同士がメッセージを交換しなければなりません。各コンピュータは出力として自分の色を出さなければなりません。
並列アルゴリズムの分野は、分散アルゴリズムの分野とは異なる焦点を持っていますが、この2つの分野の間には多くの相互作用があります。
さらに、並列アルゴリズムは、並列システム (共有メモリを使用) または分散システム (メッセージ パッシングを使用) のいずれかで実装することができます。
Complexity measuresEdit
並列アルゴリズムでは、時間と空間に加えて、もう一つのリソースであるコンピュータの数が重要になります。 実際、多くの場合、実行時間とコンピュータの数はトレードオフの関係にあります。つまり、より多くのコンピュータが並列に実行されると、問題はより速く解決されます (スピードアップを参照)。 ある決定問題が、多項式数のプロセッサを用いて多項式時間で解ける場合、その問題はクラスNCに属すると言われます。
分散アルゴリズムの解析では、通常、計算ステップよりも通信処理に注意が払われます。 分散コンピューティングの最も単純なモデルは、すべてのノードがロックステップ方式で動作する同期システムです。 このモデルは、一般的にLOCALモデルとして知られています。 各通信ラウンドにおいて、すべてのノードは並行して、（1）隣のノードから最新のメッセージを受信し、（2）任意のローカル計算を実行し、（3）隣のノードに新しいメッセージを送信する。
この複雑さの尺度は、ネットワークの直径と密接な関係があります。 ネットワークの直径をDとします。
一方で、計算可能な問題は、同期分散システムにおいて、約2Dの通信ラウンドで自明に解決することができます。単純に、すべての情報を1つの場所に集め（Dラウンド）、問題を解決し、その解決策を各ノードに通知します（Dラウンド）。
一方で、アルゴリズムの実行時間がD通信ラウンドよりはるかに小さい場合、ネットワークのノードは、ネットワークの遠い部分に関する情報を得る可能性を持たずに、出力を生成しなければなりません。 言い換えれば、ノードは、自分のローカルなD近傍で得られる情報に基づいて、グローバルに一貫した判断をしなければならない。 Dラウンドよりもはるかに小さい実行時間を持つ多くの分散アルゴリズムが知られており、そのようなアルゴリズムでどのような問題が解決できるかを理解することは、この分野の中心的な研究課題の1つである。
もう一つの一般的な指標は、ネットワークで送信されるビットの総数です (通信の複雑さを参照)。
その他の問題
従来の計算問題では、ユーザーが質問をし、コンピュータ (または分散システム) がその質問を処理し、答えを出して終了するという視点がありました。 しかし、ダイニング・フィロソフィー問題などのように、システムが停止しないことが求められる問題もあります。
また、フォールトトレランスの問題など、分散コンピューティングならではの基本的な課題もあります。
また、分散システムの非同期性を理解するために、多くの研究が行われています。
- 同期装置は、非同期システムで同期アルゴリズムを実行するために使用することができます。
- 論理的なクロックは、イベントの因果的な起こった前の順序を提供します。
- クロック同期アルゴリズムは、グローバルに一貫した物理的なタイム スタンプを提供します。
ElectionEdit
コーディネータ選挙 (またはリーダー選挙) は、複数のコンピュータ (ノード) に分散しているタスクのオーガナイザーとして、単一のプロセスを指定するプロセスです。 タスクが開始される前、すべてのネットワーク ノードは、どのノードがタスクの「コーディネーター」（またはリーダー）として機能するかを知らないか、または現在のコーディネーターと通信できない状態になっています。
ネットワークノードは、どのノードが「コーディネーター」の状態になるかを決めるために、自分たちの間でコミュニケーションをとります。 そのためには、ノード間の対称性を崩すための方法が必要です。
この問題の定義はLeLann氏によるものとされていますが、彼はこの問題を、トークンが失われたトークンリングネットワークで新しいトークンを作成する方法として公式化しました。
Gallager、Humblet、Spiraが提案した一般的な無向グラフに対するアルゴリズムは、分散アルゴリズムの設計に強い影響を与え、分散コンピューティングに影響を与えた論文としてダイクストラ賞を受賞しました。
無向リング、一方向リング、完全グラフ、グリッド、有向オイラーグラフなど、さまざまな種類のネットワークグラフに対して、他にも多くのアルゴリズムが提案されました。
分散システムでは、コーディネーションを行うために、コーディネータという概念があります。 コーディネータ選挙問題とは、分散システム内の異なるプロセッサ上のプロセス群の中から、中央のコーディネータとして機能するプロセスを選択することです。
分散システムの特性
これまでは、与えられた問題を解決する分散システムを設計することが中心でした。
中央集権的な計算の分野からの類似の例として、停止問題があります。 しかし、興味深い特殊なケースでは、決定可能なものがたくさんあります。 特に、有限状態機械のネットワークの挙動を推論することは可能です。 例えば、（非同期かつ非決定論的な）有限状態機械の相互作用するネットワークがデッドロックに達するかどうかを判断することができます。 この問題は、PSPACE-complete、つまり決定可能ですが、大規模なネットワークの場合、この問題を解決する効率的な (中央、並列、または分散) アルゴリズムが存在する可能性は高くありません。