リングネットワークにおけるリーダ選挙アルゴリズムの実験的評価

池川 幸徳  山下 雅史  阿江 忠  

誌名
電子情報通信学会論文誌 D   Vol.J73-D1   No.3   pp.261-268
発行日: 1990/03/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(661.3KB)>>
論文を購入




あらまし: 
リーダ選挙問題は,選出されたリーダ(プロセッサ)は自分が選出されたことを,選出されなかったプロセッサは自分が選出されなかったことを知っているという意味で,唯一のリーダプロセッサを選出する問題である.各プロセッサが固有の識別子をもつという仮定のもとでは,この問題は最大値(識別子)発見問題とみなすことができる.本論文では,リングネットワークに対する10通りの典型的なリーダ選挙アルゴリズムを対象とし,各アルゴリズムを計算中に交換された平均メッセージ数により評価する.