自己安定リーダー選挙MPPにおける領域複雑度の上下界について

概要

論文の詳細を見る
本論文は,自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (SS-LE MPP) の領域複雑度に関する研究結果である.Cai,Izumi and Wada (2009) は n エージェントに対する自己安定リーダー選挙ポピュレーションプロトコル (SS-LE PP) は少なくとも n 個のエージェント状態を必要とすることを示した.さらに n エージェントに対する SS-LE MPP のうちエージェント状態数が n であるプロトコルを与えた.MPP は Chatzigiannakis,Michail and Spirakis (2009) によって紹介された.MPP は分散ネットワークモデルの 1 つで,各エージェント間に局所的なメモリを追加した PP の拡張モデルである.一般的に MPP は PP よりも計算能力が高いことが知られている.一方で SS-LE のエージェント状態に対する空間複雑度の減少可能性については知られていない.本稿では,n エージェントの SS-LE MPP のうちエージェント状態数が n-1 であり,各エージェント間に 1 ビットのメモリが与えられたプロトコルを与える.
2010-11-12