固有の識別番号を仮定しないネットワークにおけるリーダー選挙問題  [in Japanese] Leader Election Problem on a Network whose Processors may not have Unique Identity Numbers  [in Japanese]

ネットワークはプロセッサの集合とプロセッサ間を結ぶ通信リンクの集合から構成される.従来,プロセッサが固有の識別番号をもつという仮定の下で,ネットワーク上の様々な問題,例えば,リーダー選挙問題,生成木構成問題,トポロジー認識問題などを効率良く解く(分散)アルゴリズム(あるいはプロトコル)に関する研究が数多くなされてきた(たとえば,萩原[2]はその概説).事実,プロセッサが固有の識別番号をもつとすると,ネットワーク・トポロジーやプロセッサ数などのネットワークの属性に関する情報が全く利用できないと仮定しても,任意のネットワークに対して,上に挙げたそれぞれの問題を解くアルゴリズムが容易に構成でき,問題はいかに効率の良いアルゴリズムを構成するかという一点に集約される.プロセッサが識別番号をもたない(あるいは全てのプロセッサが同じ識別番号をもつ)ようなネットワークをアノニマス・ネットワークと呼ぶ.アノニマス・ネットワークに対してはAngluin[1]やJohnsonとSchneider[3]が(異なるモデルを用いて)リーダー選挙問題を解くアルゴリズムが存在しないネットワークが存在することを示し,アルゴリズムが存在するための必要条件や十分条件について考察した.また,YamashitaとKameda[4]は以下の3つの場合,(1)ネットワークのプロセッサ数の上限が既知,(2)ネットワークのプロセッサ数が既知,(3)ネットワークのトポロジーが既知,について上に挙げたそれぞれの問題が解けるネットワークのクラスを明らかにした.本稿ではプロセッサが固有の識別番号をもつと仮定できないようなネットワークにおいてリーダー選挙問題が解けるための条件を考察する.従って,本稿の結果はアノニマス・ネットワークに対する同様の結果を特別な場合として含む.直感的に言えば,リーダーが選挙できるための必要十分条件は何らかの意味で特別なプロセッサが存在することである.そこで,プロセッサ間の『類似(similarity)』関係を[4]で用いたプロセッサのビューと呼ばれる概念によって定式化し,任意のプロセッサに対して類似なプロセッサが存在するようなネットワークを特徴付ける.類似関係にある二つのプロセッサは同じ結果を出力する可能性があることが示せ,上記の特徴付けはネットワークの上でリーダーが選挙できるための必要十分条件となっている.