１、分散アルゴリズムとは？

今度の発表のために、資料の内容を簡潔にまとめておく。
参考アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ―超入門編)

　近年、ネットワーク網の発達や計算機が安価になるなど、複数の計算機を用い、ネットワークを通じて協調計算させることが重要になっている。具体的には、LAN や WAN を通じて、計算機が接続され計算が行われている。（後で書き換える）
　このように、計算機が分散してあり、通信路でつながれているシステムを分散システムという。このような分散システム上では、各計算機上では、局所的な情報を用いて全体としての整合性がとれた解を求める必要がある。そのような、局所的な情報を交換し、効率的に解を求めるアルゴリズムのことを分散アルゴリズムという。

　次に、実際の分散システム上では、計算機の故障などの問題から、一か所に情報を集めて解くことは信頼性の観点から望ましくない。つまり、１つの特別なプロセスに情報を集めて、問題を解いた際、そのプロセスが故障した時にシステム全体がダウンしてしまう。したがって、分散アルゴリズムでは、各プロセスは均一である必要があり、プロセスが故障した場合、そのプロセスを除けば問題なく動作する。

　分散アルゴリズムの評価では、送信されたメッセージ数の合計で評価する。これは、各計算機で非同期性を仮定しているためである。非同期性とは、各プロセスの実行速度が異なってよく、メッセージ伝達速度においても何も仮定をしない。したがって、計算が終了するまでの時間が問題とならない。