# 障害箇所特定パラダイム分類 ## 定義 障害箇所特定(fault localization)技術は、依拠する形式手法に応じて**専門家システム**・**モデル走査**・**グラフ理論的手法**・**codebook手法**の4パラダイムに大別できる、という [[A survey of fault localization techniques in computer networks]](Steinder & Sethi, 2004)による分類である。この分類は人工知能・グラフ理論・情報理論・オートマトン理論という異なる計算機科学の分野に由来する(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 1 Introduction]])。 ## 4パラダイムの特徴 - **専門家システム(expert-system techniques)**: rule-based(表層知識・forward-chaining推論)、model-based(システムの依存関係グラフという深層知識)、case-based(過去事例からの学習)の3種。rule-basedは構成変更への追従が困難で、学習・未知問題への対応に弱い。model-basedはこれらの弱点を克服するが、モデルの構築・維持が難しい(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 2 Expert-system techniques for fault localization]])。 - **モデル走査(model traversing techniques)**: オブジェクト指向でモデル化されたシステム上を、アラームを報告したエンティティから関係リンクをたどって探索し、イベント相関を行う。構成変更に頑健で分散化しやすい一方、複数コンポーネント故障の論理的組み合わせ(AND/OR)をモデル化できない(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 3 Model traversing techniques]])。 - **グラフ理論的手法(graph-theoretic techniques)**: 障害伝播モデル(fault propagation model, FPM)として依存グラフ・因果グラフを用い、観測された症状集合を最もよく説明する障害仮説を求める。この問題は一般に NP-hard であり、bipartite化・OR/ANDモデルへの制限・単一障害仮定などで計算量を抑える(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]])。 - **codebook手法**: イベント伝播を離散無記憶通信路上のデータ伝送とみなし、事象相関を受信符号の復号問題として定式化する。符号化は事前に1回だけ行われるため実行時は効率的だが、構成変更のたびに符号帳(codebook)を再生成する必要がある(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 4 Graph-theoretic techniques]])。 ## 未解決の問い - multi-layer環境において4パラダイムのどれも単独では十分でなく、症状フィルタリングにrule-based、隣接層のアラーム相関にmodel-based、複雑なトポロジ下の診断にグラフ理論的非決定手法を組み合わせる必要があるが、これらを一貫した multi-layer 解へ統合する方法は未解決である(Source: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 5 Open research problems]])。 ## 関連 - ソース: [[@2004__SCP__A survey of fault localization techniques in computer networks - Chapter 1 Introduction]] - 概念: [[Fault Localization]]、[[確率的障害伝播モデル]]