# 分散実行最小化 ## 定義 分散実行最小化(Distributed Execution Minimization)とは、分散システムの障害実行トレースから不変条件違反を再現するために**必要最小限のイベント列**を自動的に探索する技法である。外部イベント(プロセス起動・クラッシュ回復・外部メッセージ送信)と内部イベント(プロセス間メッセージ配送)を区別して段階的に最小化する点が、逐次プログラムのテスト入力最小化と本質的に異なる。 具体的には、外部イベントの部分列 E' であって、E' を含む何らかのスケジュール(内部イベントの配送順序)のもとで不変条件違反 P が再現し、かつ E' から任意の 1 イベントを除去すると再現できなくなるもの(**最小因果列 MCS: Minimal Causal Sequence**)を求めることが目標となる。(Source: [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]]) DEMi(Distributed Execution Minimizer)はこの問題を解く代表的な実装である。デルタデバッギングで外部イベントを絞り込み、DPOR(動的部分順序簡約)で内部イベントのスケジュール空間を有界時間内に探索する。スケジュール探索には「原実行に近い構造を優先する」という経験則を活用し、型ベースマッチング(TFB: Type Fingerprints with Backtracks)によって内容依存の停滞を回避する。 ## 横断的知見 - **デルタデバッギングからの系譜**: Zeller らのデルタデバッギング [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]] は逐次テスト入力を対象とする。分散実行最小化はこれを拡張し、並行プロセス間のメッセージ配送スケジュールという第 2 の自由度を追加で探索しなければならない。階層型デルタデバッギング (HDD) [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] が構造化入力の最小化に木を利用するのと同様に、DEMi は外部イベント列→内部イベント列→メッセージ内容という階層的な最小化を採用する。これは「入力の構造を手掛かりに探索空間を削減する」という共通の戦略を異なる対象ドメインで実現した例と見なせる。(Source: [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]], [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]], [[@2006__ICSE__HDD - Hierarchical Delta Debugging]]) > [!note] 2 ソース目以降に追記予定 > 現時点では DEMi(NSDI 2016)が主要ソースである。デルタデバッギング系論文が ingest されたあとに、逐次手法との定量的比較を横断的知見として積み増す。 ## 未解決の問い - 単一物理マシン・Akka フレームワーク限定という制約はどのように解除できるか? 他のフレームワーク(例: gRPC ベースのサービスメッシュ、Kubernetes Pod)への適用コストはどの程度か? - 本番トレースへの適用には完全な部分順序記録が必要とされるが、大規模本番環境でそれを低コストで実現する現実的な方法は何か? - ライブネスバグ(非終了・性能劣化など)への拡張は理論的にどこまで可能か? 安全性違反と異なり終了が保証されない検査をどう有界化するか? - 外部イベントが互いに依存する場合(例: あるメッセージを除去すると別のメッセージが意味を失う)の最小化は、補集合を考慮する ddmin の O(|E|²) 版で十分か、それとも文法ベースの制約が必要か? - スケジュール探索の優先化戦略(TFB)は「原実行に近い構造が違反を再現しやすい」という経験則に依存する。この経験則が成り立たない系(敵対的プログラム)はどの程度実際に問題になるか? ## 関連 - ソース: [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]] - デルタデバッギング(逐次): [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]] - 階層型デルタデバッギング: [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] - エンティティ: [[Colin Scott]] / [[Aurojit Panda]] / [[Scott Shenker]] ## 出典 - [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]]