分散アルゴリズム研究グループ紹介

Introduction to Distribute Algorithm Research and Development Group

分散アルゴリズム研究グループでは，よりよいネットワーク環境の実現のための理論的アプローチとして，分散アルゴリズムの研究・開発を行っています．

このページでは，本グループで行っている研究内容とともに，研究対象である分散アルゴリズムについても簡単に説明しています．以下の目次のリンクから，興味ある部分を選択して読んでください．手っ取り早く研究内容を知りたい方は， 4.から見ていただければ結構です．分散アルゴリズムがはじめての方は， 1.から順に読んでいただくことをお勧めします．内容的には，できるだけ平易な内容にとどめています．

1.分散アルゴリズムって？

分散アルゴリズムを一言で言うと，ネットワークにつながった計算機同士で，与えられた問題をどうやって解くかを規定するものです．もう少し定式化していうと，通信リンクで互いに接続されたプロセス同士が，情報を交換し協調しながら問題を解くためのアルゴリズムです．具体的な問題としては「リーダー選択問題」「相互排除問題」など，さまざまな問題が，さまざまなモデルの上で考えられています．

現実的にネットワークで利用されている分散アルゴリズムの例としては，インターネットの世界で古くから利用されている「RIP(Routing Information Protocol)」があげられます．これはBellman-Ford アルゴリズムといわれる距離ベクトル型ルーティングプロトコルで，さまざまな改良が加えられ，今日でも多くのネットワーク(主にLAN)で利用されています． IGRP(Interior Gateway Routing Protocol)も Bellman-Ford アルゴリズムを利用したルーティングプロトコルのひとつです．

2.故障耐性のある分散アルゴリズム

ネットワーク，中でもインターネットは，通信の確実性を強く保障するものではありません．したがって，ネットワークを利用したアプリケーションを使っているときでも，急にネットワークが切断されてしまい，それ以上仕事が進まなくなることは，多くの人が経験していることでしょう

ネットワークの切断(障害)と一口に言っても，さまざまな原因がありますが，大きく分けると次のふたつになるでしょう．

ネットワークに接続された計算機やルータの障害
ハブやケーブルを含めた通信路の障害

これらの障害は，分散アルゴリズムのモデル上では，それぞれプロセッサの故障，通信リンクの故障として扱います．そして，このような障害がおきても正しく問題を解くことができるアルゴリズムを「故障耐性のある分散アルゴリズム(fault tolerant distributed algorithm あるいは dependable distributed algorithm)」と呼びます．ネットワークが大規模になるにつれ，たった一箇所の障害が大規模な障害に発展する可能性が増大しています．そのような状況で，故障耐性のある分散アルゴリズムの開発が期待されています．

3.理論としての分散アルゴリズムの研究とは？

アルゴリズムというと，とかく理論的なものばかりが目に付き，実際の応用はあまり考慮されていないように考えられがちです (実際そういう側面がほとんどなのですが)．しかしRIPの例を見てもわかるように，分散アルゴリズムは，今日のネットワークを支える「基盤技術」の一つとして捉えられます．

一方，純粋に理論的な研究としての楽しみも十分にあります．理論的研究は，「出来上がり」としての「もの」を想像することが困難で，研究を進めていく上での目標が見えづらいという印象もあるでしょう．しかし，逆にとらえると，頭の中で純粋に思考のみで問題を解決し，結果を出すことも可能であることを意味します．実際，研究を始めて3ヶ月で結果を出し，論文に仕立て上げる人もいます．このような「アルゴリズムを思いつけばそれで成果」というのは，ある意味理論的研究の特権なのかもしれません．何せ，結果を出すまでに，早い人は早いのです．

しかし，みんながそんな簡単にはいきません(というか，普通は簡単ではないのです)．システムを構築しようとすると，まずはプログラミングの勉強，システム設計の手法，実現方法など，さまざまな知識を動員する必要があります．また，それらの知識を得るために，多くの時間が必要です．アルゴリズムも同じなのです．プログラミング言語を覚える代わりに，分散アルゴリズムが考えられているさまざまなモデルを勉強し，システム設計手法・実現方法を勉強する代わりに，今まで考えられてきた分散アルゴリズムの資産を学ばなければなりません．そのためにたくさんの論文を読み，議論・討論する必要があります．そういう土台ができて，初めて新たなアルゴリズムなりパラダイムなりが創造できるのです．

もちろん，理論的学習一辺倒では，よいアルゴリズムは生まれません．分散アルゴリズムはネットワーク上でその威力を発揮します．その土俵であるネットワークについての基礎知識も持っているに越したことはありません．そうして初めて，理論と実践に乖離のないモデルを構築し，分散アルゴリズムを設計することができるものと考えています．

そういう意味では，実践に強い理論的研究者が求められています．あなたはどうでしょう？

4.具体的にどんな問題を考えているの？

本研究グループでは，現在主に以下のような問題を考えています．

ad-hoc ネットワークでのトークン巡回問題
ad-hoc ネットワークとは，ネットワークに接続するために特別な設定が不要で，かつネットワークへの参加・退出が自由に行えるようなものです．つまり，ネットワーク中のノードやリンクが頻繁に出現・消滅するようなネットワークモデルです．このようなネットワーク中で，トークンを安全確実に巡回させるためのアルゴリズムを開発しています．
モバイルエージェントの効率のよい巡回問題
昨今，モバイルエージェントを用いたネットワークアプリケーションがさまざま提案・実現されつつあります．たとえば，モバイルエージェントを用いてネットワーク中に存在するさまざまな情報を収集しようとするとき，エージェントをどのような戦略で巡回させれば効率よく(すばやく・確実に) 収集できるでしょうか？そのような目的のための巡回アルゴリズムの開発を行っています．
自己安定アルゴリズム一般
自己安定アルゴリズムとは，任意の一時故障(リンクやノードの一時的な停止，伝搬中のメッセージの内容改変など) にかかわらず問題を解くことのできるアルゴリズムで，非常に高度な故障耐性を持っています．現在知られている分散アルゴリズムの自己安定化を含めて，さまざまな問題に自己安定のパラダイムを適用し，高度な故障耐性を持つ分散アルゴリズムの開発を行っています．

上記の問題は，あくまでも一例です．本研究グループでは，最新の論文などの輪講を行い，常に分散アルゴリズムの可能性を探っています．その過程で，他にもさまざまな問題を扱うことになります．

5.分散アルゴリズム研究グループの未来

理論と実践のバランスが取れた研究を進めていくのが，ひとつの目標です．「分散アルゴリズムとは？」の中で述べている， Bellman-Ford のアルゴリズムは，理論的に考えられたアルゴリズムが実践で大いに利用されている，もっとも顕著な例でしょう．本研究グループでも，そんなアルゴリズムが開発できるといいな…と考えています．

もちろん，純粋に理論的な研究も同時に行っていきたいと考えています．むかしチューリング(Turing)が「チューリングマシン」を提案し，それは今でも計算機科学の基礎として利用し続けられています．そんな提案ができるとすばらしいですね．夢は「チューリング賞」でしょうか．「そんな大それた…」とはいえ，夢は大きく持っていたいものです．

分散アルゴリズム研究グループ