6K-05
Dieudonneらの集合アルゴリズムの時間計算量の改善
集合問題とは、グラフ上に任意に配置されたエージェント群をひとつの頂点に集める問題である。本稿では、任意の敵対的な動作をするエージェント(ビザンチンエージェント) がエージェント群に混在したときの集合問題について考える。当然ながら、ビザンチンエージェントが混在する場合はすべてのエージェントをひとつの頂点に集合させることはできない。したがって、すべての正常エージェントがひとつのノードに集合すればよいとする。ビザンチンエージェントの数に依らず集合問題を解く手法としてDieudonneらのアルゴリズムが良く用いられる。本稿では、このアルゴリズムの時間計算量を改善する。