English

モバイルエージェントのアルゴリズム

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

図12: 最大マッチング

図12: エージェントシステムの例

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

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

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

集合アルゴリズム

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

図13: 初期状況

図13: 初期状況

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

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

図14: 目印つきの初期状況

図14: 目印つきの初期状況

アイデアは簡単で、目印と目印の間の距離を使って集合します。まず、各エージェントはノード数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つあるため、集合位置を一つに定めることができません。実は、このような周期的な初期配置の場合、エージェントが同じアルゴリズムを実行する限り、どんなアルゴリズムを作っても集合することができません。

図15: 周期的な初期状況

図15: 周期的な初期状況

最近の研究テーマ

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

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

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

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

図16: ビザンチン環境

図16: ビザンチン環境

図17: ビザンチン環境における集合

図17: ビザンチン環境における集合

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

以下の研究では、任意の形のネットワークにおいて、各エージェントが同期的に動作する場合(エージェントのスピードが同じ場合)に、ビザンチン故障を起こすエージェントの上限がf、リンクの数がmのとき、認証機能付き白板を用いることでO(fm)時間で集合を実現するアルゴリズムを提案しました。認証機能付き白板の説明はここでは省略します。従来のアルゴリズムは、認証機能付き白板を用いずに、ノード数がnのときに、だいたいO(n9)くらいの時間(大雑把に書いています)で集合を実現していました。つまり、我々のアルゴリズムは、認証機能付き白板を用いることで、集合に必要な時間をO(n9)からO(fm)に大きく削減できることを示しています。

Masashi Tsuchida, Fukuhito Ooshita, and Michiko Inoue, "Byzantine-tolerant gathering of mobile agents in arbitrary networks with authenticated whiteboards", IEICE Transactions on Information and Systems, vol. E101-D, no. 3, pp. 602-610, Mar. 2018.

また、以下の研究では、認証機能付き白板を用いることで、各エージェントが非同期的に動作する場合(エージェントのスピードがバラバラの場合)でも、集合を実現できることを示しました。

Masashi Tsuchida, Fukuhito Ooshita, and Michiko Inoue, "Gathering of mobile agents in asynchronous Byzantine environments with authenticated whiteboards", Proceedings of the 6th Edition of the International Conference on Networked Systems (NETYS), pp. 85-99, May 2018.

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

本研究では、エージェントシステムの基盤となるノードが故障を起こし、故障を起こしたノードに訪問したエージェントは全て消えてしまうという状況を考えました。訪問したエージェントを全て消してしまうノードのことをブラックホールと呼びます。ブラックホールが存在すると、エージェントは安心してシステム内を移動することができません。そこで、複数のエージェントを用いて、ブラックホールの場所を特定するためのアルゴリズムを開発しました。本アルゴリズムでは、いくつかのエージェントがビザンチン故障を起こしたとしても、ブラックホールの場所を特定することができます。

Masashi Tsuchida, Fukuhito Ooshita, and Michiko Inoue, "Black hole search despite Byzantine agents", Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Oct. 2019.