時間遅延が存在する有向グラフにおける分散有限時間平均コンセンサス

ほとんどの分散平均化アルゴリズムは、漸近的収束のみを保証します。本論文では、有向グラフ（ダイグラフ）で記述された相互接続トポロジーにおいて、ノードが初期値の正確な平均を有限かつ最小限のステップ数で見つけることを可能にする分散プロトコルを紹介します。具体的には、各コンポーネントが自分の出力リンクの数（すなわち情報を送信するコンポーネントの数）についての知識を持っていると仮定した場合、有限時間間隔にわたる局所観測に基づいて平均値を計算できることを示します。情報交換に遅延があっても、有限のステップ数で平均を取得できます。提案されたアルゴリズムは、遅延のある場合とない場合の両方で、ダイグラフにおいて有限時間内に正確な平均を分散計算することを可能にする文献上初のものです。