自己安定アルゴリズム

自己安定分散アルゴリズムとは？

自己安定分散アルゴリズムとは、「自己安定」という良い特性をもった分散アルゴリズムのことです。自己安定とは、システムがどのような異常な状況に陥っても、自動的に目的の状況へ到達するという性質です。もしシステム全体の状況をすぐに把握することができるなら、どのプロセスを修正すればよいかがすぐに分かります。しかし、大規模な分散システムではそのようなことができず、局所情報だけを頼りに異常な状況を修正する必要があります。もしかすると、各プロセスの周囲は正しそうにみえても、全体としてはおかしな状況ということが起こるかもしれません。このような場合でも、システム全体として目的の状況に到達するようにアルゴリズムを設計する必要があります。

自己安定全域木生成アルゴリズム

例として、自己安定全域木生成アルゴリズムを説明してみます。まず、図2のような分散システムを考えましょう。目的は、分散システムに図3のような全域木（全プロセスを接続する木）を作成することです。全域木は、全プロセスを最小限のリンク数で接続することができるので、多くの分散アルゴリズムのバックボーンとして利用することができます。各プロセスが親へのポインタ（周囲のノードのうちのどれが親か？）を持っていれば、図3のように木を表現することができます（根は自分を指すとします）。

さて、自己安定全域木生成アルゴリズムでは、どのような異常な状況からでも、目的の状況へ到達する必要があります。つまり、図4のように全域木ができていない状況から、全域木を作る必要があります。では、どのように動けばいいでしょうか？プロセスP1の局所情報（周囲の情報）を見ると、P1がP2を指していて、P2がP1を指しているというおかしな状況に気づきます。例えば、P1がポインタをP3向きに変えたとしましょう。次の状況は図5のようになります。図5でもまだ全域木になっていないので、いずれかのプロセスが動く必要があります。では、どのプロセスが動けばよいでしょう？P1はプロセスP3を指していて、P3はまた別のプロセスを指しています。P1もP3も、局所的には木の一部として問題ありません。実は、他のどのプロセスも、局所的には木の一部として問題ありません。つまり、全体としては全域木になっていないのに、局所的には問題が発生していないということになります。自己安定アルゴリズムを設計するためには、このような状況をうまく発見して、修正する方法を実装する必要があります。

では、どうすればよいでしょう？実は各プロセスが親へのポインタを持っているだけでは、局所的に異常を発見することができません。そこで、もう一つ変数を用意して、全域木における根からの距離を保存することにします。図6は、目的の状況、すなわち、全域木が完成していて根からの距離も正しく保持している状況を表しています。定義から明らかなように、各プロセスの「根からの距離」は、自分の親プロセスの「根からの距離」に1を足したものとなっています。では、図5のような異常な状況ではどうなるでしょう？図7が、図5に根からの距離を追加したものです。これを見ると、プロセスP3の「根からの距離」は、親プロセスの「根からの距離」に1を足したものになっていません。つまり、プロセスP3は全域木がおかしな状況であるということに気づき、動くことができます。

では、実際に動作する自己安定全域木アルゴリズムを以下に示します。

• 根プロセスの動作
  ポインタが自分を指していない、または、「根からの距離」が0でない
  　→ポインタを自分に向けて、「根からの距離」を0にする

• 根以外のプロセスの動作
  ポインタが周囲の誰かを指していない、または、
  　自分の「根からの距離」が親プロセスの「根からの距離」に1を足したものになっていない
  　→ポインタを周りのプロセスのうち「根からの距離」が一番小さいものに向け、
  　かつ、自分の「根からの距離」を（上で設定した）親プロセスの「根からの距離」に1を足したものにする

簡単にいえば、周りのプロセスのうち、「根からの距離」が一番小さいものを親にする、というアルゴリズムです。このアルゴリズムによって、どのように異常な状況に陥ったとしても、自動的に全域木を作ることができます。

自己安定1-極大マッチングアルゴリズム

ディペンダブルシステム学研究室では、これまでに様々な自己安定アルゴリズムの設計に取り組んできました。最近の成果である、自己安定1-極大マッチングアルゴリズムについて簡単に説明します。

まず、このアルゴリズムが作る1-極大マッチングを順に説明していきます。図8のような分散システムを考えましょう。マッチングとは、図9のように直接通信できるプロセス同志でペアを作ったものです。各プロセスはたかだか一つのペアにしか含まれていないことに注意してください。プロセス間でペアを作るというのは非常に重要で、例えばペアをクライアントとサーバとしてサービスを提供するなど、さまざまなアプリケーションで利用することができます。このようなペアはできるだけ多いほうが都合がよいため、以下で説明する1-極大マッチングなどを作ることが重要です。さて、実は図9のマッチングは、極大マッチングでもあります。極大マッチングとは、「ペアを解消せずに、これ以上ペアを増やせない」ようなマッチングのことです。図9を確認してみると、確かにペアを組んでないプロセスの周りはペアを組んでいるプロセスしかおらず、ペアを解消しない限り新たにペアを作ることができません。ここで、「極大」と「最大」の違いに注意してください。最大マッチングとは、ペア数が最大のマッチングのことです。とはいえ、極大マッチングも最大マッチングの良い近似といえ、極大マッチングのペア数は最大マッチングのペア数の半分以上であることが知られています。

では、本題である1-極大マッチングを説明しましょう。1-極大マッチングとは、極大マッチングの条件に加えて、「どの一つのペアを解消しても、新たに二つのペアを作ることができない」という条件を満たすマッチングです。例えば、図9のマッチングは1-極大マッチングではありません。なぜかというと、プロセスP2とP3のペアを解消することで、P1とP2、P3とP4という新たに二つのペアを作ることができるからです。この変更によって作った図10のマッチングは、1-極大マッチングとなっています。先ほど、極大マッチングは最大マッチングの良い近似になっていると言いましたが、1-極大マッチングはさらに良い近似となっています。具体的には、1-極大マッチングのペア数は、最大マッチングのペア数の2/3倍以上ということが知られています。ちなみに、最大マッチングは図11のもので、5つのペアを作ることができます。

ディペンダブルシステム学研究室では、図10のような1-極大マッチングを生成する自己安定アルゴリズムを開発しました。つまり、どのような異常な状況（1-極大マッチングができていない状況、マッチングができていない状況、でたらめなマッチングになっている状況など）からも自動的に1-極大マッチングを生成するアルゴリズムを作りました。実はこのようなアルゴリズムは既に存在したのですが、我々が提案したアルゴリズムではそのステップ数（1-極大マッチングを作るまでのプロセスの動作回数）を大きく削減しました。具体的には、プロセス数nの分散システムについて、既存研究でO(n4)のステップ数が必要だったところを、我々はO(n2)まで減らしました。4乗を2乗に減らしたということで、我々の提案アルゴリズムは既存研究よりかなり効率的であるといえます。

アルゴリズムの詳細は複雑なので省略しますが、興味のある人は以下の論文を読んでみてください。

Yuma Asada, Fukuhito Ooshita, and Michiko Inoue, “An efficient silent self-stabilizing 1-maximal matching algorithm in anonymous networks”, Journal of Graph Algorithms and Applications, Vol. 20, No. 1, pp.59-78, Feb. 2016.