# 確率的障害伝播モデル ## 定義 障害伝播モデル(fault propagation model, FPM)とは、システムのどのコンポーネントの障害がどの症状を発生させ得るかを表す有向グラフモデルであり、グラフ理論的障害箇所特定手法(→ [[障害箇所特定パラダイム分類]])が共通に用いる形式である。因果グラフ(causality graph)$G_c(E, C)$ はノード集合 $E$ が事象、辺集合 $C$ が事象間の因果関係を表す有向非巡回グラフであり、依存グラフ(dependency graph)$G(O, D)$ はノード集合 $O$ がオブジェクト、辺 $D$ がオブジェクト間の障害依存(条件付き故障確率で重み付けされる)を表す。オブジェクトが単一の故障モードしか持たない場合、両表現は等価である(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]])。 ## 定式化と計算量 観測された症状集合を最もよく説明する障害仮説をFPMから求める問題は、一般に **NP-hard** である。この複雑さを抑えるため、実際の手法はしばしばモデルの形状を制限する: (1) 依存関係をOR結合(いずれか1つの原因で発生)またはAND結合(すべての原因が揃って発生)に限る**OR/ANDモデル**、(2) 障害と症状の関係を二部グラフに限る**bipartite化**(→原因-症状マップは外部観測から得やすいが、間接的な依存を表現できない)、(3) 同時に存在する障害数を1個または少数に制限する単一障害仮定。症状処理は時間窓ベース(window-based)と、症状到着ごとに逐次処理するイベント駆動(event-driven)の2方式があり、後者はレイテンシ低減・テストとの統合・FPM変化への頑健性で優る(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]])。 ## FPM上の代表的な求解手法 - **分割統治(divide and conquer)**: 依存グラフを最大相互依存度で再帰的に2分割し、原始的な原因候補を絞り込む。計算量 $O(N^3)$。障害間の依存が無い場合は多項式時間の別アルゴリズムを用いる。 - **文脈自由文法(context-free grammar)**: 階層的なオブジェクト間依存を生成規則で表現し、最小障害集合を貪欲に選ぶアルゴリズムと、紛失・偽症状を許容し木探索で最小コスト解を選ぶアルゴリズムの2種がある。後者は0-1整数計画問題としても定式化される。 - **codebook技術**: 因果グラフを最適化された符号行列(codebook)に変換し、ハミング距離(決定的モデル)または対数尤度距離(確率モデル)で最近傍復号する。符号化は1回のみで済み効率的だが、構成変更ごとの再生成が必要。 - **belief network(ベイジアンネットワークによる推論)**: FPMをbelief networkとして定式化し、観測証拠に対する最尤説明を求める。単連結ネットワークではメッセージパッシングにより多項式時間で解ける。 - **incremental hypothesis updating(IHU)**: bipartite FPM上でイベント駆動・逐次的に仮説集合を更新するアルゴリズム。複数の代替仮説を信念指標付きで保持し続ける。 (Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]]) ## 関連 - ソース: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]] - 概念: [[障害箇所特定パラダイム分類]]