自己安定化

自己安定化は、分散システムにおけるフォールト トレランスの概念です。任意の初期状態が与えられると、自己安定化分散システムは有限数の実行ステップで正しい状態に到達します。

一見すると、自己安定化の保証は、特定の種類の状態遷移においてシステムが常に正しい状態を維持することを保証することを目的とする、より伝統的なアルゴリズムのフォールト トレランスほど期待できないように思えるかもしれません。しかし、その伝統的なフォールト トレランスは、常に達成できるわけではありません。たとえば、システムが誤った状態で起動された場合や、侵入者によって破壊された場合は、達成できません。さらに、分散システムは複雑であるため、デバッグや分析が非常に困難です。したがって、分散システムが誤った状態に到達するのを防ぐのは非常に困難です。実際、いくつかの形式の自己安定化は、アルゴリズムの設計では予見できなかった障害に対処する能力を与えるため、多くの現代のコンピューターネットワークや通信ネットワークに組み込まれています。

1974年にエドガー・ダイクストラが独創的な論文を発表してから何年も経った今でも、この概念は自己管理型コンピュータシステムとフォールトトレラントシステムの重要な基盤を提示しており、依然として重要です。その結果、ダイクストラの論文は、分散コンピューティングコミュニティで最も高い評価の1つである2002 ACM PODC Influential-Paper Awardを受賞しました。^[1] さらに、ダイクストラの死後、この賞は改名され、現在はダイクストラ賞と呼ばれています。

EW ダイクストラは1974 年に自己安定化の概念を発表し、この分野でのさらなる研究を促しました。^{[2]彼のデモンストレーションでは、自己安定化}相互排他アルゴリズムが紹介されました。^[3]また、システムに対する強い仮定に依存しない最初の自己安定化アルゴリズムも示されました。実際に使用されていた以前のプロトコルの中には、実際に安定化するものもありましたが、システム全体にわたるクロックの存在と、各システム遷移の期間の上限が既知であると仮定しているものだけでした。研究者^{[4]がこの洗練されたフォールト トレランスの概念に注目したのは、それから 10 年後の 1983 年の}シンポジウム「分散コンピューティングの原理に関するシンポジウム」でレスリー ランポートがダイクストラの研究の重要性を指摘してからのことでした。講演でランポートは次のように述べています。

私はこれをダイクストラの最も優れた研究、少なくとも彼が発表した論文の中で最も優れたものだと考えています。ほとんど知られていませんが、フォールトトレランスの研究における画期的なものだと考えています。自己安定化はフォールトトレランスにおいて非常に重要な概念であり、研究にとって非常に豊かな分野であると考えています。^[3]

その後、ダイクストラの研究はACM-PODCの影響力のある論文賞を受賞し、それがACM（計算機協会）の分散コンピューティングにおけるダイクストラ賞となり、毎年開催されるACM-PODCシンポジウムで授与されるようになりました。^[5]

分散アルゴリズムが自己安定型であるとは、任意の状態から始めて、正当な状態に収束し、その後も正当な状態セットに留まることが保証されている場合です。状態が正当であるとは、この状態から始めて、アルゴリズムがその仕様を満たす場合です。自己安定の特性により、分散アルゴリズムは、その性質に関係なく、一時的な障害から回復することができます。さらに、自己安定アルゴリズムは、初期状態に関係なく、最終的には正しく動作し始めるため、初期化する必要はありません。

自己安定化の概念を紹介したダイクストラの論文では、「トークン リング」という、円状に並べられたコンピュータのネットワークを例に挙げています。ここでは、各コンピュータまたはプロセッサは、その直前の 1 つのプロセッサの状態全体を「見る」ことができ、この状態はプロセッサが「トークンを持っている」か「トークンを持っていない」かを示す可能性があります。^{[5] [6]}要件の 1 つは、常にそれらの 1 つだけが「トークンを保持している」必要があることです。2 つ目の要件は、各ノードが「トークンを次のコンピュータ/プロセッサに渡す」ことで、トークンが最終的にリングを循環するようにすることです。^{[5] [6]}

• トークンを保持していないことは、このネットワーク内の各コンピュータにとって正しい状態です。トークンは別のコンピュータによって保持される可能性があるためです。ただし、すべてのコンピュータが「トークンを保持していない」状態である場合、ネットワーク全体が正しい状態ではありません。
• 同様に、複数のコンピュータが「トークンを保持している」場合、これはネットワークの正しい状態ではありませんが、個々のコンピュータを見てもそれが間違っていることは確認できません。各コンピュータは隣接する 2 台のコンピュータの状態しか「確認」できないため、コンピュータがネットワーク全体が正しい状態にあるかどうかを判断するのは困難です。

最初の自己安定化アルゴリズムは、エラーを明示的に検出して後で修復することはしませんでした。代わりに、システムを常に正当な状態へと押し進めました。エラーを検出するための従来の方法^[7]は、非常に困難で時間がかかることが多かったため、このような動作が望ましいと考えられていました。(上記の論文で説明されている方法では、ネットワーク全体から大量の情報を 1 か所に収集し、その後、収集したグローバル状態が正しいかどうかを判断しようとしますが、その判断だけでも困難な作業になる可能性があります)。

最近では、研究者らは、局所的なチェックを用いた自己安定システムの軽量なエラー検出のための新しい手法を発表している。^{[8] [9]}そして一般的なタスクについても。^[10]

ローカルという用語は、コンピュータ ネットワークの一部を指します。ローカル検出を使用すると、ネットワーク内のコンピュータは、エラーを検出するためにネットワーク全体と通信する必要がありません。各コンピュータが最も近いコンピュータとのみ通信することで、エラーを検出できます。これらのローカル検出方法により、自己安定アルゴリズムの設計作業が大幅に簡素化されました。これは、エラー検出メカニズムと回復メカニズムを個別に設計できるためです。これらの検出方法に基づく新しいアルゴリズムも、はるかに効率的であることがわかりました。さらに、これらの論文では、非自己安定アルゴリズムを自己安定アルゴリズムに変換するための、かなり効率的な汎用トランスフォーマーが提案されています。そのアイデアは次のとおりです。

1. 同時に非自己安定化プロトコルを実行し、
2. 上記の検出方法を使用して（特定のプロトコルの実行中に）障害を検出する。
3. 次に、（自己安定化）「リセット」プロトコルを適用してシステムを所定の初期状態に戻します。そして最後に、
4. 指定された（非自己安定化）プロトコルを再起動します。

これら4つの部分の組み合わせは自己安定化している（修正故障フェーズ中に故障のトリガーがない限り、例えば^[11]）。初期の自己安定化プロトコルも上記の論文で提示された。より効率的なリセットプロトコルは後に提示された。例えば^[12]

さらなる効率性は、時間適応型プロトコルの概念によって導入されました。^[13]これらの背後にある考え方は、少数のエラーしか発生しない場合は、回復時間を短くすることができる（そして短くすべきである）というものです。ダイクストラのオリジナルの自己安定化アルゴリズムには、この特性がありません。

自己安定化アルゴリズムの有用な特性は、層が循環依存関係を示さない限り、層で構成できることである。その場合、構成の安定化時間は、各層の個々の安定化時間の合計によって制限される。^[6]

ダイクストラの研究に対する新しいアプローチは、後にクリストフ・アプトの事例やエフサン・ショヤの提案などによって登場し、戦略ゲームの標準的な概念、特に改善パスの概念を使用して自己安定化が自然に定式化される方法を実証しました。^[14]この特定の研究は、自己安定化とゲーム理論のつながりを実証しようとしました。

自己安定化アルゴリズムの 時間計算量は、（非同期の）ラウンドまたはサイクルで測定されます。

• ラウンドは、各プロセッサが少なくとも 1 つのステップを実行する最短の実行トレースです。
• 同様に、サイクルは、各プロセッサが繰り返し実行されるコマンドのリストの少なくとも 1 つの完全な反復を実行する最短の実行トレースです。

出力安定化時間を測定するために、状態変数のサブセットが外部から見えるように定義されます（出力）。出力の特定の状態は正しい（正当）と定義されます。システムのすべてのコンポーネントの出力セットは、追加の障害が発生しない限り、無期限に正しいままであれば、正しくなり始めた時点で安定化したと言われます。出力安定化時間は、出力が安定するまでの時間（（非同期）ラウンドの数）です。 ^[8]

システムが自己安定化するのは、次の場合のみです。

1. どのような状態から始めても、システムが最終的に正しい状態（収束）に到達することが保証されます。
2. システムが正しい状態にある場合、障害が発生しない限り、正しい状態を維持することが保証されます (閉鎖)。

システムがランダム化自己安定化であるとは、システムが自己安定化しており、正しい状態に到達するのに必要なラウンドの期待値が何らかの定数で制限されている場合に限ります。^[15]${\displaystyle k}$

前述の意味での自己安定化の設計は、難しい仕事であることがよく知られています。実際、分散アルゴリズムのクラスには、ローカル チェックの特性がありません。つまり、ネットワーク状態の正当性を単一のプロセスで評価することはできません。最も明白なケースは、上で定義した Dijkstra のトークン リングです。隣接していないプロセスに複数のトークンが存在する場合、どのプロセスもネットワーク状態が正当かどうかを検出できません。これは、分散システムの自己安定化が、各コンポーネントがローカルな知識に基づいてローカルなアクションを実行する一種の集合知であることを示唆していますが、最終的にはこれがグローバルな収束を保証します。

上記で定義した自己安定化を設計する難しさを克服するために、他のタイプの安定化が考案されました。たとえば、弱い安定化は、分散システムがあらゆる可能な状態から正当な動作に到達する可能性があるという特性です。^{[16]弱い安定化は、分散システムのすべての実行で収束するのではなく、いくつかの実行で収束する}可能性 を保証するだけなので、設計が簡単です。

自己安定アルゴリズムは、アルゴリズムが使用する通信レジスタの値が固定されたままのグローバル状態に収束する場合にのみ、サイレントになります。 ^[17]

自己安定化の概念の拡張は超安定化の概念である。^[18] ここでの意図は、トポロジーの変化を受ける動的分散システムに対処することである。古典的な自己安定化理論では、任意の変化はエラーと見なされ、システムが再び安定するまで保証はない。超安定化システムでは、システムのトポロジーが再構成されている間、常に満たされる 通過述語がある。

自己安定化の領域から始まった理論は、ネットワーク内のノードの状態の集合が何らかの述語に従うことを（分散方式で）検証するというものです。その理論は自己安定化を超えて、「分散 NP」（NP（複雑性）の分散バージョン）、分散ゼロ知識（ゼロ知識の分散バージョン）などの概念につながりました。2024 年の国際構造情報通信複雑性コロキウム （SIRROCO）分散コンピューティングにおけるイノベーション賞は、その理論の創始に対して授与されました。

• libcircle - 終了時にトークン パッシングを使用する自己安定化の実装。