ナノスケール分散システムのためのアルゴリズム

近年ナノテクノロジーの発展に伴い、ナノスケール、分子スケールのシステムの実現が現実味を帯びています。実際に、DNAを用いたセンサー、アクチュエータ、演算回路などが実現されており、それらを組み合わせた分子ロボットの開発が進んでいます。分子ロボットが実現されれば、それを用いて体内にネットワークを形成し、体内の情報を収集したり、病気の細胞へ薬を届けたりできるようになります。

このようなナノスケールの自律分散システムでは、正確な計算、正確な通信、豊富なメモリなど、コンピュータで当たり前に仮定できた性質を仮定することができません。本研究では、現実のコンピュータよりはるかに弱い能力のナノスケールコンピュータを想定して、さまざまなタスクを実行するための分散アルゴリズムを開発しています。

個体群プロトコルモデルに対するアルゴリズム

ディペンダブルシステム学研究室では、ナノスケール分散システムへ応用可能なアルゴリズムを開発するために、個体群プロトコルモデルに対するアルゴリズムを開発しています。個体群プロトコルモデルでは、図19のように個体（物体）が好き勝手に動いている状況をモデル化しています。そして、2つの個体が十分に近づいたときに、個体間で交流が発生し、2つの個体の状態が変化します。このモデルによって、例えば、分子が溶液中をふわふわと漂っていって、分子が衝突したときに化学反応によって分子の状態が変わる、という状況をモデル化することができます。本研究では、このような非常にシンプルなシステムで、どのようなタスクが実現できるかを研究しています。

リーダ選択アルゴリズム

例として、シンプルなタスクを考えてみましょう。初期状況では、全個体が赤状態であるとします。このとき、最終的に一つの個体だけを赤状態のまま残し、他の個体を全て青状態にするにはどうすればよいでしょうか？この場合は簡単で、「赤と赤が交流したときに、片方を青にする」というアルゴリズムで実現できます。図20のように、これだけのルールで、交流が何度も発生していくうちに一つの個体だけが赤で残ります。この問題は、全個体の中から一つ（リーダ）を選ぶという意味で、リーダ選択問題として知られています。リーダ選択問題は基本的な問題ですが、さまざまな応用がある重要な問題です。

さて、上の例では、初期状況から始まって、リーダ（赤の個体）が一つだけ残れば問題が解けたと考えました。しかし、ナノスケールの個体はコンピュータのように安定しておらず、環境ノイズの影響で個体の状態が予期せず変わってしまったり、個体が壊れたりする可能性があります。つまり、青の個体が赤に変わって複数のリーダが産まれたり、赤の個体が壊れてリーダが消えたりするかもしれません。そのため、このような場合でも、自動的にリーダを再度一つだけ選ぶような性質が望まれます。先ほどのアルゴリズムはこの性質を満たしているでしょうか？赤の個体が複数になった場合は、それらが交流していくことで一つだけが残り、リーダを選ぶことが可能です。赤の個体がいなくなった場合はどうでしょう？この場合、赤を作るルールはないので、いつまでたっても全ての個体が青のままです。

半数分割アルゴリズム

真面目な説明は次のパラグラフからすることにして、まず考えた状況の一部のイメージをクイズとして説明します。あなたの目の前にたくさんの偶数個のボールが入った箱があります。各ボールには、赤0、赤1、青0、青1の4種類のラベルのいずれかが貼ってあります。箱の中全体をまとめて見ることはできません。ボールが何個入っているのかも、どんなラベルが貼ってあるのかも分かりません。4種類のラベルがでたらめに貼ってあるかもしれないし、全部が赤0かもしれません。あなたができることは、「箱の中からランダムにボールを1個取り出して、そのラベルを確認し、4種類のラベルのうちのどれかに張り替えて（同じラベルも可）箱に戻す」ということだけです。これをずっと繰り返すことで、ある時点以降、箱の中の赤と青のラベルの数をちょうど等しくし、赤と青の数が等しいという状況を維持するようにしてください。

上のクイズは、個体群を同数の２グループに分割するという半数分割問題に対するアルゴリズム（図21）の一つのイメージです。多数の個体が存在していても、それらが全く同じタスクを実行していては効率的ではありません。半数分割を繰り返すことで、個体群を任意の数のグループに分割することができ、それぞれのグループに別のタスクを割り当てることができます。我々の細胞も分化を繰り返すことで、さまざまな機能をもった細胞へと変化していきます。半数分割アルゴリズムは、個体群プロトコルモデルにおいて個体の分化を実現するアルゴリズムといえます。

本研究の成果を以下の表にまとめています。表にはアルゴリズムを実現可能な最小状態数を示しています。Nは個体数の最大値を表します。「不可」は、「アルゴリズムの実現が不可能なことを証明した」という意味です。

基地局とは強力な能力をもつ特別な個体のことで、「基地局あり」では1台だけ基地局が存在することを仮定しています。弱公平では、各個体間で交流が無限回発生することだけを仮定しています。そのため、都合の悪い順序の交流が無限回繰り返されることも考慮しています。一方、全体公平では、そのようなことが起こらないと仮定しています。非対称遷移とは、同じ状態の個体が交流したときに別々の状態に遷移することです。分子ロボットのようなナノスケールの個体では、非対称遷移のあるアルゴリズムの実装が難しいため、非対称遷移のないアルゴリズムの方が望まれています。初期値が一定とは、アルゴリズムの実行開始時に、全ての個体の状態が特定の初期値であることを意味しています。そのため、この設定では、実行開始時に全ての個体を何らかの方法で初期化することが必要となります。一方で、初期値が任意の場合は、基地局以外の個体の初期化が必要ありません。そのため、自己安定アルゴリズムに似た性質を実現でき、一時故障が発生して個体が任意の状態になったとしても、基地局を初期化するだけで半数分割を達成することができます。

最初のクイズは、基地局あり、全体公平、初期値が任意、非対称遷移なしのアルゴリズムに対応しています。箱からボールを1個取り出してラベルを張り替えるという動作が、基地局と個体の交流を表しています。個体と個体が交流したときに状態を変化させてもよいのですが、提案したアルゴリズムではそのような動作を行なっていません。以下に提案したアルゴリズムの簡単なデモを置いています。真ん中の四角が基地局で、各個体は基地局にぶつかったときに状態を変化させます。

k分割アルゴリズム