# group testing ## 定義 グループテスト(group testing)は、多数の要素のうち少数だけが「陽性」(故障・感染など)である疎な設定で、要素を個別にではなく複数まとめたグループ単位でテストし、テスト回数を全数検査より大幅に減らしながら陽性個体を特定する統計的・情報理論的な検査戦略である。適応的グラフ制約付きグループテスト(adaptive graph-constrained group testing)は、要素間の関係をグラフとして表現し、1 回のテストがグラフ上の頂点集合とその間の辺を同時に検査対象にできるという制約のもとで、テスト結果を見ながら次のテスト集合を適応的に選ぶ変種である。 ## 未編纂の観察 - **[GPU クラスタの障害箇所特定への応用] FaultSense はレプリカを無向完全グラフ(頂点=GPU、辺=通信経路)として抽象化し、グループテストを二段階(貪欲被覆によるグローバル被覆 Phase 1 → 健全頂点でパディングした適応的drill-down Phase 2)に構造化することで、100-GPU レプリカの診断プローブ数を全数対テスト(4950回)から約250回(約20倍削減)まで減らした。障害が疎である(大多数の GPU・通信経路は健全)という前提のもとで、MoE モデルの top-k ルータが持つスパースな選択性を利用し、1 回のプローブで k 個の GPU とそれらの間 k(k-1)/2 本の通信経路を同時にテストする。(Source: [[@2026__APSys__FaultSense - Fault Localization in Large-Scale Mixture-of-Experts Model Serving Infrastructure]]) - [グラフ制約下での応用] ノード故障局所化の識別可能条件(k-identifiability)は、combinatorial group testing の disjunct 行列の考え方(k 列のブール和が他の列を「含まない」)を応用して定式化できる(Source: [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]])。ただし通常の group testing と異なり、テスト可能な部分集合(測定パス)がネットワークトポロジー・モニター配置・プロービング機構によって制約される点が本質的な違い([[Graph-constrained group testing]]との関係)。 ## 未解決の問い - Phase 1 のグローバル被覆は NP-hard な最適被覆問題を貪欲近似で解いているが、複数の無関係な障害が同時発生した場合に貪欲被覆の疎密(プローブサイズ k の選び方)が Phase 2 の drill-down コストに与える影響はどこまで定量化できるか。(Source: [[@2026__APSys__FaultSense - Fault Localization in Large-Scale Mixture-of-Experts Model Serving Infrastructure]]) ## 関連 - 概念: [[Fault Localization]] / [[Mixture-of-Experts]] - ソース: [[@2026__APSys__FaultSense - Fault Localization in Large-Scale Mixture-of-Experts Model Serving Infrastructure]] / [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]] ## 出典 - [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]](group testing の disjunct 行列の考え方をネットワーク経路制約下の故障局所化に応用)