トーラス上の局所多数決と大域多数決

概要

論文の詳細を見る
分散システムにおいて, 大域的に多数を占める意見に全てのプロセッサが合意する方法, 言い替えれば各プロセッサが多数意見を正しく知る方法を考える. ただし各プロセッサは自分の近傍のプロセッサの意見だけしか参照することができないと仮定する. 問題を以下のようにグラフ問題として定式化する. グラフG(V, E)によって分散システムをモデル化する. 頂点集合でプロセッサ集合を, 無向枝集合で双方向通信リンク集合を表す. したがって頂点vは(自分自身を含む)近傍Γ(v)={v}∪{u∈V∣{u, v} ∈ E}に属する頂点と直接情報交換が可能である. 各頂点(プロセッサ)v ∈ Vは(時刻0に)その意見を表す0か1のいずれかをその初期状態として持つ. そして各頂点vは各時刻t=1,2,...に同期的に自分の近傍において多数を占める値に自分の状態を更新する. この状態遷移を何回か繰り返した後に全ての頂点の状態が0となるとき, (初期状態において)状態1の頂点の集合は状態0の頂点の集合に支配されているという. 本稿では, トーラスを対象として被支配頂点数の最大値について検討する.
社団法人電子情報通信学会の論文
1999-04-23