目次
分散アルゴリズムとは？
インターネットのように、多くのコンピュータがお互いに通信できる環境があるとします。 そのような環境では、それぞれのコンピュータがてんでばらばらに動くだけではなく、全体で協調して動く必要があります。 そのときに、それぞれのコンピュータがどのように動けば、全体で協調して動作できるか？、を考えるのが、分散アルゴリズムです。
あるコンピュータAから他のコンピュータBと通信したい、とします。 また、コンピュータは隣のコンピュータとだけ直接通信することができ、それ以外のコンピュータとはバケツリレー方式(パケット交換)で通信するとします。 このとき、一体どうすれば通信できるでしょうか？
このコンピュータ同士が隣にあれば苦労はありませんね。そうでなければ、隣のうちのどのコンピュータに託せばよいか？を考える必要があります。 託された側も同じようにどのコンピュータに託せばよいかを考えなければなりません。また、単純に託せばよいというものではなく、最も早く到着するようにしたい、無駄な通信は出来る限りしたくない、などの要求も満たす必要があります。
すべてのコンピュータがシステム内のコンピュータの繋がり方を示した設計図を知っていると、このような問題は解決できます。しかし、世界中のコンピュータが繋がっていたりすると、その設計図が大き過ぎて、それぞれのコンピュータで扱ってられません。また、インターネットのように時々刻々とつながっているコンピュータが変化していると、 持っている設計図が正しいのかどうかも分かりません。
分散システムとは、このようなコンピュータが通信リンクでお互いにつながっているネットワークです。分散システムでは一般的にシステム全体が見えないため、コンピュータAからコンピュータBへ通信したいという単純な要求に対するアルゴリズムの設計でも困難となっています。
また、分散システムでは、コンピュータの故障や、コンピュータ同士の接続(つながり方)の変化などが発生することが考えられます。そのため、このような状況になってもシステム全体の処理が停止することがないように、耐故障性、柔軟性など性質を持つことが必要とされています。このような性質を持ちながら、かつ、できるだけ無駄な通信を行わない効率のよい分散アルゴリズムを設計するため、多くの研究が行われています。