超安定化とは、分散コンピューティングにおけるフォールトトレランスの概念です。超安定化分散アルゴリズムは、自己安定化アルゴリズムと動的アルゴリズムの特徴を組み合わせたものです。超安定化アルゴリズムは、他の自己安定化アルゴリズムと同様に、任意の状態から開始することができ、最終的には適切な状態に収束します。さらに、超安定化アルゴリズムは、ネットワークトポロジの単一の変更（ネットワーク内のエッジまたはノードの追加または削除）から 迅速に回復します。
あらゆる自己安定アルゴリズムは、ネットワークトポロジの変化から回復します。つまり、トポロジ変化後のシステム構成は、他の任意の初期構成と同様に扱うことができます。しかし、自己安定アルゴリズムでは、ネットワークトポロジの単一変化後の収束は、任意の初期状態からの収束と同じくらい遅くなる可能性があります。超安定アルゴリズムの研究では、ネットワークトポロジの単一変化からの回復にかかる時間に特に注目しています。
定義
超安定化アルゴリズムの安定化時間は、自己安定化アルゴリズムの場合と全く同様に定義されます。つまり、任意の構成から正当な状態に収束するまでにかかる時間です。計算モデルに応じて、例えば同期通信ラウンド単位や非同期サイクル単位で測定されます。
超安定化時間とは、単一のトポロジ変更から回復するまでの時間です。システムは当初、正当な構成にあると仮定します。その後、ネットワークトポロジが変更されます。超安定化時間とは、システムが再び正当な構成に到達するまでにかかる最大時間です。同様に、調整尺度とは、そのような変更後に状態を変更しなければならないノードの最大数です。
1 つのトポロジの変更後に発生する「ほぼ正当な構成」は、通過述語を使用して正式にモデル化できます。通過述語は、ネットワーク トポロジの単一の変更後、および正当な構成への収束中に保持される述語です。
参考文献
- Dolev, Shlomi ; Herman, Ted (1997)、「動的分散システムのための超安定化プロトコル」、Chicago Journal of Theoretical Computer Science、3 : 1– 40、doi : 10.4086/cjtcs.1997.004、第4条。
- Dolev, Shlomi (2000), Self-Stabilization , MIT Press , ISBN 0-262-04178-2、セクション7.1。
