English

分散アルゴリズム

ディペンダンブルシステム学研究室では、分散システムのためのアルゴリズムである分散アルゴリズムの研究を行っています。分散システムとは、複数の計算主体(計算機やプロセス)とそれらの間の通信手段からなるシステム(図1)です。実は、世の中のほとんどのシステムは分散システムといえます。例えば、およそ10億台のコンピュータが通信しながら動作しているインターネットは、ひとつの大規模分散システムといえます。IoT(Internet of Things、モノのインターネット)も、多数のモノが協調動作する分散システムです。Bitcoinなどが用いるブロックチェーンも、取引記録を多数のコンピュータが協調して管理する分散システムです。その他、センサネットワーク、アドホックネットワーク、ITS(高度道路交通システム)、P2Pネットワークなど、分散システムの例を挙げるときりがありません。

図1: 分散システムの例

図1: 分散システムの例

インターネットのような大規模分散システムでは、全てのプロセスを集中管理することは不可能です。そのため、逐次アルゴリズム(CPUが一つの計算機のためのアルゴリズム)とは異なるアルゴリズムが必要となります。分散アルゴリズムとは、自律して動作する(つまり、それぞれ勝手に動作する)複数のプロセスを効率よく協調動作させることを目的としたアルゴリズムです。本研究室では、さまざまなタイプの分散システムに対して、よい特性をもった分散アルゴリズムを研究しています。

しかし、分散アルゴリズムの設計は簡単ではありません。ネットワークの状況を瞬時に把握することは計算機の数が多すぎて不可能なので、各プロセスは周辺から得られる局所情報だけを頼りに動作しなければなりません。また、各プロセスの計算速度や通信速度はバラバラですし、それらはプロセスやネットワークの負荷によって変わってしまいます。これは、分散システムが非同期的であり、分散アルゴリズムを実行するまで、各プロセスや通信がどんな速さで動くか分からないということです。つまり、分散アルゴリズムを設計するときは、局所情報だけを頼りに、各プロセスがどんな速さで動いても、プロセス間の通信がどんな速さで行われても正しく動作するように考える必要があります。そのため、我々は「どうすればいつでも正しく動くアルゴリズムを作れるだろう」とか「作ったアルゴリズムにとって最悪な動き方はどんなのだろう」とかを日々考えながら、分散アルゴリズムを設計しています。設計したアルゴリズムの正当性や計算複雑度を証明するのは一苦労ですが、パズルのピースがはまったかのように証明が完成すると大きな達成感を味わえます。

研究テーマ