停止故障耐性を有する一般化されたFrench Flag Problemのための分散アルゴリズムについて

摘要

French Flag Problem は, 格子状に配置されている色のないそれぞれのセルを, 分散的な手法を用いて, 青, 白,赤の3 つの色を均等に出力させるパターン問題の一つである. 具体的には,2 次元格子上に配置されたプロセス(以下, エージェント) を自律的に動作させ, 隣接エージェントと通信を行いながら色を決定し, 全体としてフランス国旗のような形で収束させる問題である. さらに, 色の数を3 色からk 色に一般化させた問題をk-Flag Problemと呼ぶ(図1). Albert ら[1] は, 格子状で配置されたエージェントにおけるFrench Flag Problem 収束時間やメモリ, メッセージサイズなどのいくつかの観点に着目した様々なアルゴリズムを提案している. [1] では, ある１行において色を決める1 ことが可能であれば, その結果を伝搬させることで, 格子状に配置された全てのエージェントの色を決めることができることから, 直線上に配置されたエージェントに対するアルゴリズムが提案されている. しかし, 停止故障エージェントがひとつでも存在すると情報交換が不能となり, 既存研究[1] の手法はそのまま適用できない. 本研究では, 停止故障耐性を有するk-Flag Problem を解く分散アルゴリズムを提案する.