技術要約：分散コンピューティングシステムのための生成マルコフモデル

問題定義

コンピューティング・コンティニュアムのような新興の分散コンピューティング・パラダイムは、固有のヘテロジェニティ（異質性）、確率性、および複雑性を特徴としている。クラウドコンピューティングはオンデマンドのプロビジョニングなどの利点を提供する一方で、増大する需要を満たすためにAI推論インフラをスケールアップすることは、多大なコストと環境負荷をもたらす。ボランティアコンピューティングや、ユーザーデバイス、エッジ、クラウドを統合するコンピューティング・コンティニュアムのような代替パラダイムは、効率性の向上の可能性を秘めている。しかし、これらのシステムは、リソースのヘテロジェニティやユーザーの可用性の断続性により、安定したサービス品質（QoS）の保証に苦慮している。

特定された核心的な課題は、リソースのヘテロジェニティ、確率的な可用性、およびシステム状態の高次元性を考慮できる統一された形式的モデルの欠如である。このようなモデルがなければ、パフォーマンスのトレードオフに関する推論や、大規模な意思決定ポリシーの最適化を行うことは困難であり、大規模な展開を阻害することになる。

手法

著者らは、分散コンピューティングシステムをモデル化するための**生成マルコフモデル（GMM）**フレームワークを提案する。この手法は、計算の実行可能性を確保するために、システム状態の構造化された因子分解に基づいている。

1. 理論的枠組み

時刻 $t$ におけるシステム状態 $s_t$ は、$N$ 個の高次元変数のタプルとして定義される。結合分布の複雑さを管理するため、モデルはマルコフ性を課し、2レベルの疎な因子分解を利用する。

• 変数因子分解（Variable Factorization）: 結合分布 $p(s_t | s_{t-1})$ は、現在の状態および前の状態からの特定の親変数 $Pa(v_t)$ に条件付けられた各高レベル変数 $v_t$ の条件付き分布（ファクター）へと分解される。
• 要素因子分解（Element Factorization）: 各高次元変数 $v_t$ は、さらに個々の要素 $v_t \in v_t$ にわたって因子分解される。これは、分散システムにおける疎な依存関係構造（例：ノードやタスクなどのコンポーネントは、グローバルな状態ではなくローカルな情報に基づいて進化する）を利用したものである。

この因子分解により、本来であれば計算不可能なほど高次元なシステム状態に対しても、シミュレーション、推論、およびポリシー学習を可能にする、扱いやすいモデルが得られる。

2. ケーススタディ：協調型分散AI推論

本フレームワークは、専用サーバー（$v_0$）と一連のユーザーノード（$I$）を含む、協調型AI推論シナリオに対して具体化される。

• システム状態: システム状態ベクトル $s_t$ には、ユーザーの可用性（$o_t$）、リクエスト状態（$q_t$）、リソース割り当て（$a_t$）、準備状態（$x_t$）、実行状態（$y_t$）、リソース消費（$c_t$）、および期間変数（$d_t$）が含まれる。
• 依存関係: モデルは、リソースの自己相関（履歴バッファによって処理される）や、データ転送フェーズと実行フェーズの結合など、複雑な依存関係を捉える。
• ポリシー: 意思決定は2つのポリシー因子によって制御される。
  • スケジューラ ($\pi$): サーバー上で動作し、サブタスクのダウンロードと実行の割り当てを決定する。
  • エグゼキュータ ($\varsigma$): 各ノード上で動作し、ローカルのリソース制約（例：中断、一時停止）を強制する。
• 最適化問題:
  • スケジューラ・ポリシーの最適化: 長期的なQoS（レイテンシの最小化）を最大化するための、平均報酬強化学習（RL）問題として定式化される。
  • 専用リソースの最適化: 固定されたポリシーの下で、特定のタスクタイプに対して特定のレイテンシ閾値を満たすために必要な最小限の公称サーバーリソースを見つけるための、チャンス制約付き最適化問題として定式化される。

主な貢献

1. 生成マルコフモデリング: 本論文は、分散コンピューティングシステム全体を生成マルコフモデルとしてモデル化するフレームワークを導入する。特定の意思決定問題をMDP（マルコフ決定過程）として定式化する従来の研究とは異なり、このアプローチはシステムダイナミクスそのものをモデル化しており、分散コンピューティングとマルコフ連鎖理論および強化学習を結びつけている。
2. 新しい因子分解構造: フレームワークは、新しい2レベルの疎な因子分解（変数レベルおよび要素レベル）とモジュール構造を採用している。これにより、条件付き分布を、特定のシステム変数に適した手法を用いて独立して推定することが可能となり、高次元性にもかかわらずモデルの計算可能性が維持される。
3. 実用的な具体化: 著者らは、協調型AI推論のための具体的な具体化を提供し、専用サーバーのリソースとボランティア提供されたユーザーリソースの相互作用をモデルがどのように扱うかを実証している。

結果

フレームワークは、最大10,000人のユーザーと変動するサーバー容量を持つ分散推論システムのシミュレーションを通じて評価された。2つのスケジューリングポリシーが比較された：集中型（すべてのサブタスクをサーバー上で実行）および分散型（サブタスクをサーバーとオンラインユーザーに均等に分散）。

• レイテンシ性能: ユーザー数が増加するにつれ、集中型ポリシーはボトルネックとなり、P99レイテンシが著しく増大した。対照的に、分散型ポリシーは、単純な配布戦略であっても、集中型アプローチを段階的に上回り、より低いレイテンシを実現した。
• リソース効率: 分散型ポリシーは、集中型ポリシーと比較して、サーバーのCPUおよびメモリ使用量において一貫して低い値を示した。特筆すべきは、1,000人のユーザーにおいて、両方のポリシーが同等のP99レイテンシを達成したが、分散型ポリシーは大幅に少ないサーバーリソース消費でそれを実現したことである。
• スケーラビリティ: 結果は、計算をユーザーデバイスに分散させることで、レイテンシとサーバーリソース消費の両方を削減できることを示しており、このような環境における適応的な意思決定の有効性を裏付けている。

意義と主張

本論文は、提案されたフレームワークが、複雑でヘテロジェニティを持つ分散システムにおけるパフォーマンスのトレードオフを推論し、意思決定を最適化するための必要な形式的モデルを提供すると主張している。疎な因子分解を通じてシステム状態を扱いやすくすることで、本フレームワークは以下を可能にする：

• シミュレーションと評価: 完全な規模の物理的デプロイメントを必要とせずに、様々な条件下（負荷、リソースの可用性など）でのシステム挙動をシミュレートする能力。
• ポリシーの最適化: 最適なスケジューリングポリシー（最適化問題として定義される）を学習するための、強化学習手法への直接的な架け橋。
• モジュール性: フレームワーク全体を再設計することなく、新しいリソースタイプ、タスク構造、またはノードの振る舞いへとモデルを拡張できる能力。

著者らは、集中型スケジューリングはスケール時に失敗する一方で、計算をユーザーデバイスに分散させることは大きな効率性の向上をもたらすと結論付けている。彼らは、適応的な意思決定戦略の開発と最適化は、彼らの提供する統一された確率的構造なしには不可能であることを強調している。今後の課題として、実環境での検証、スケーラビリティの調査、およびスケジューラとリソース割り当てポリシーのさらなる最適化に焦点を当てる計画である。