自己安定アルゴリズムって何?

自己安定アルゴリズムとは，どんな状況からアルゴリズムの計算を始めても，いずれ目的の解を得られる分散アルゴリズムです．

自己安定アルゴリズムは，どんな数，どんな種類の故障からでも自律的に復帰できる分散アルゴリズムを設計する上で，非常に有用な設計パラダイムです．

分散アルゴリズムと初期状況

分散アルゴリズムで，アルゴリズムの計算をはじめる時点での分散システムの状況を「初期状況」と呼びます．分散システムに参加している，各プロセスの状態すべてのことです．
多くの分散アルゴリズムでは，理想的な初期状況からアルゴリズムを開始することを前提としています．（たとえば，すべてのプロセスが同じ情報を持っている，などです．）つまり，理想的な初期状況から計算をはじめられた場合のみ，計算結果を得られることを保証してくれます．
C言語やJavaを使ったプログラミングでも，宣言した変数は必ず初期化してから使いますよね？初期化を忘れてプログラムがおかしな振る舞いをする，という経験は誰にでもあるはずです．
しかし，実際のネットワークでは，いつも理想的な初期状況からアルゴリズムの計算を開始できるとは限りません．インターネットのように参加しているプロセスが膨大な分散システムでは，すべてのプロセスで足並みをそろえることは非常に大変です．
自己安定アルゴリズムはどんな初期状況からアルゴリズムの計算を開始しても，やがて正しい計算結果を得られることを保証します．言い替えれば，「理想的な初期状況」から計算を開始できない場合にも，目的の計算結果を得られることを保証してくれます．

故障耐性という要求

コンピュータの故障は避けられません．分散システムは多数のプロセス（コンピュータ）で構成されているので，システムのどこかで故障が発生する可能性は潜在的に高くなっています．
プロセスで故障が発生すると，そのプロセスの持っていたデータが壊れてしまいます．また，正常なプロセスも故障したプロセスの影響を受けて，自分のデータを書き換えてしまう可能性があります．このように，ひとつのプロセスで発生した故障によって分散システム全体の状況が変わってしまう可能性があります．
分散システムでは，それぞれのプロセスに故障があっても，システム全体としては運用し続けられることが望ましいアプリケーションがたくさんあります．このため，故障耐性をそなえた分散アルゴリズムは古くから，多くの研究者が取り組んでいます．

故障耐性と自己安定アルゴリズム

自己安定アルゴリズムは，故障直後の状態を「初期状態」ととらえ，どのような初期状態からも計算を正しく行なうことを保証しています．どのような数，種類の故障が発生しても，自己安定アルゴリズムは「初期状態」と見なすので，自己安定アルゴリズムはとても強力な故障耐性を持っていると言えます．

ダイクストラの自己安定相互排除アルゴリズム

自己安定という概念がはじめて提案されたのは，1974年，E.W. Dijkstra （ダイクストラ）によってでした．
以下のフラッシュはダイクストラが初めて提案した自己安定相互排除アルゴリズムのデモです．（各プロセスの状態数はn（全ノード数）のバージョンです．）

相互排除とは，ある「特権」をみんなで順番に回し合う問題です．
5人がしゃべりたいのにマイクが１つしかなければ，5人で順番にマイクを回しますよね？
例えば「マイクを誰が持つのか」を決めるのが，相互排除問題です．
当然，永遠にマイクを取り合って結局誰もしゃべれない事態や，誰か1人が永遠にマイクを占有し続けるといった事態は避けられなくてはいけません．

デモでは，P1，P2，...と書かれた○がそれぞれプロセスを表しています．今回は5個のプロセスP1, P2, P3, P4, P5がリング上に繋がったネットワークを考えます．
restartボタンをクリックすると，プロセスの状態をランダムに「壊した」状況からの実行を開始します．
にょーんと拡大表示されたプロセスが「特権」を持っているプロセスです．
最初は複数のプロセスが「特権」を持っている状態になりますが (みんなでマイクを取り合っている状態)，やがて「特権」はひとつに減り (誰か1人がマイクを確保)，順番にプロセスの間をぐるぐるとまわり始めます．
ここまでくればマイクが規則的にまわって，皆が順番に話せる状態です．

[出典] E.W. Dijkstra. Self stabilizing systems in spite of distributed control. Communication of the ACM.Vol.17(11), pp.643--644. 1974.

<分散システムとは
home