モバイルエージェント（以下、エージェント）とは、ネットワーク上を自律的に移動可能なソフトウェアのことで、分散システムの設計手法のひとつとして注目を集めています。エージェントを用いた分散システムでは、エージェントがネットワーク上を移動しながら、データを集めたり、移動先でタスクを行なったりします。例えば、図12のようなエージェントを用いた商取引システムでは、予算・買い物リストなどを持ったエージェントがネットワーク上の店を回り、情報収集をしながら効率的な商取引を行ないます。複数のエージェントを同時に動かし、エージェント間で協力させることで、より効率的にタスクを行なうこともあります。

エージェントの利点として、以下のような点が挙げられます。

• 設計の容易化：エージェントは、そのメモリとプログラムがセットになっており、他のエージェントによって自分のメモリが書き換えられるということはありません。そのため、各ノードで情報を集めながら処理を行なうプログラムを自然に書くことができ、分散システムの設計を容易化することができます。

• 処理の効率化：ネットワーク内に存在する膨大なデータを処理する際、エージェントはデータを通信しながら処理するのではなく、自分自身がデータのある場所に移動して処理を行ないます。エージェント自身のサイズ（プログラムと内部メモリ）は、処理するデータに比べてはるかに小さいため、ネットワークトラフィックを抑えることができます。近年、ビッグデータと呼ばれるように扱うデータのサイズが大きくなっており、エージェントを用いる大きな利点といえます。

• ディペンダビリティの向上：エージェントは自律的に移動先を決めることができるため、移動予定の計算機が故障していたり、負荷が高い状態になっていれば、それを避けて別の計算機に移動することができます。また、一時的にネットワークの接続が切れたとしても、エージェントは自身の存在する計算機に留まっておくことができ、ネットワーク接続が復活したタイミングで移動を続けることができます。このように、エージェントは環境変化に対して柔軟な対応ができ、システムのディペンダビリティを高めることができます。

ディペンダブルシステム学研究室では、エージェントを効率的に動作させるための分散アルゴリズムを開発しています。具体的には、以下のようなアルゴリズムを開発しています。

• 集合アルゴリズム：複数のエージェントを一か所に集めるためのアルゴリズム。一か所に集めることで、エージェント間の情報共有を実現し、仕事を分担することができます。

• 探索アルゴリズム：エージェントにネットワーク全体を訪問させるためのアルゴリズム。ネットワーク全体を訪問することで、全計算機から情報を取得することができます。

• 均一配置アルゴリズム：エージェントをネットワーク全体に均一に配置するためのアルゴリズム。均一に配置することで、各エージェントにネットワークの担当範囲を均一に割り当てることができます。

しかし、エージェントのためのアルゴリズムの開発も簡単ではありません。エージェントもネットワーク全体の情報を瞬時に把握することはできないので、初期状況では各エージェントはネットワークのどこに他のエージェントがいるか分かりません。そのような状況から、各エージェントはネットワーク内を移動し、目的を達成する必要があります。

集合アルゴリズム

例として、とても単純な集合アルゴリズムを紹介します。ネットワークもとても単純なもの、すなわち、図13のようなリングネットワークを考えます。エージェントの移動方向も時計回りだけとします。エージェントは全く同じアルゴリズムを実行しなければならず、他のエージェントがどこにいるのかは分かりません。計算機数8という情報だけは与えられているとしましょう。このような状況で、図の3つのエージェントが一か所に集合することはできるでしょうか。

まず、出会うまでひたすら進むという方法が考えられますが、これはうまく集合できません。他のエージェントも同じようにひたすら進むので、結局永遠に追いかけっこを続けることになります。ひたすら進むのが駄目なら、1歩進んで1回止まって、2歩進んで2回止まって、3歩進んで3回止まって、、、ということを繰り返すのはどうでしょうか？これもうまく集合できません。全エージェントが同じアルゴリズムを実行しなければならないので、全エージェントが全く同じスピードで動くと、結局いつまでたっても追いつくことができません。実は、全エージェントが同じアルゴリズムを実行する場合、計算機に何も情報を残せないと集合することができません。

では、図13のように、計算機に目印を置けるとしましょう。最初に自分がいた計算機に目印をつけて進むとすると、ネットワーク中に3つの目印が置かれることになります。このうちの1つを選べれば良いわけですが、どうすればよいでしょうか？

アイデアは簡単で、目印と目印の間の距離を使って集合します。まず、各エージェントはノード数8という情報を頼りに一周します。その際、目印と目印の間の距離を覚えておきます。例えば、エージェントA1は、順に(2,3,3)という距離を観測することになります。同じように、エージェントA2は(3,3,2)、エージェントA3は(3,2,3)という距離を観測します。このとき、各エージェントは観測する距離が違いますが、他のエージェントが観測する距離を推測することができます。すなわち、エージェントA1は(2,3,3)という列の要素を一つずつずらした列を作ることで、他のエージェントが(3,3,2)、(3,2,3)を観測することが分かります。観測する列の集合{(2,3,3),(3,3,2),(3,2,3)}は全エージェントで共通なので、辞書順で一番先頭の要素を選ぶことができ、その要素を観測したエージェントの初期位置のところで集合することができます。例えば、図14では、エージェントA1の(2,3,3)が辞書順番で一番先頭なので、エージェントA1の初期位置に全員が集合できます。

さて、この方法に欠点はないでしょうか？例えば、図15のように、エージェントが4つで(1,3,1,3)と距離を観測したらどうなるでしょう？この場合、(1,3,1,3)に対応するエージェントが2つあるため、集合位置を一つに定めることができません。実は、このような周期的な初期配置の場合、エージェントが同じアルゴリズムを実行する限り、どんなアルゴリズムを作っても集合することができません。

最近の研究テーマ

上記の説明ではリングネットワークを例に挙げましたが、我々は木ネットワークや任意のネットワークを対象とした集合アルゴリズムも提案しています。また、上記の説明で、「周期的な初期配置では、同じアルゴリズムを実行する限り集合できない」と書きましたが、この表現は正確ではなく、正確には「同じ”決定性”アルゴリズムを実行する限り集合できない」です。決定性アルゴリズムとは乱数を使わないアルゴリズムのことで、実は乱数を使うことで周期的な初期配置でも高確率で集合できる乱択アルゴリズムを提案しています。

また、大規模な分散システムでは、ノードやエージェントに故障が発生することも考えられます。少数のエージェントが突然停止しても残りのエージェントでタスクを完了させられるアルゴリズム、訪問するだけでエージェントが消えてしまうノード（ブラックホール）が存在してもタスクを完了させられるアルゴリズムなど、ディペンダビリティの高いエージェントアルゴリズムの開発も行っています。

ビザンチン環境における集合アルゴリズム

ディペンダブルシステム学研究室の最近の成果であるビザンチン環境における集合アルゴリズムについて簡単に説明します。

先述の通り、大規模な分散システムでは、エージェントの故障が発生する可能性があります。本研究では、最も扱いが難しい故障であるビザンチン故障をエージェントが起こす場合でも集合を実現するアルゴリズムを提案しました（図16）。ビザンチン故障を起こしたエージェントはどんな行動をするか分かりません。止まってしまうかもしれませんし、ランダムに動くかもしれませんし、他の正常なエージェントに都合が悪いように動くかもしれません。例えば、あるエージェントに対してはノードAが集合場所だよと教えつつ、別のエージェントにはノードBが集合場所だよと教えるかもしれません。ビザンチン故障は、ソフトウェアが故障を起こした状況や悪意あるクラッカーに乗っ取られた状況などをモデル化しています。本研究では、このようなビザンチン故障が存在する状況でも、図17のように正常なエージェントが集合できるアルゴリズムを考えています。

ビザンチン環境におけるブラックホール探索アルゴリズム