6K-04
ビザンチンエージェントが混在するモバイルエージェント群による乱択集合アルゴリズム
集合問題とは、グラフ上に任意に配置されたエージェント群をひとつの頂点に集めるという問題である。本稿では、任意の敵対的な動作をするエージェント(ビザンチンエージェント) がエージェント群に混在したときの集合問題について考える。ビザンチンエージェントを含めてひとつの頂点に集合させることはできないので、すべての正常エージェントがひとつのノードに集合すればよいとする。本稿では、エージェント群の同期性と認証付き白板の存在およびエージェント数の上界Kの知識を仮定することで集合問題をO(m+\alpha nK\lamda)ラウンド、成功率1-2^{-\alpha}で解く乱択アルゴリズムを提案する。ここで、m,nはグラフの辺数および頂点数であり、\lambdaは最小のエージェントIDのビット長である。