故障発生時の連結性判定問題を解く分散アルゴリズムについて

情報処理学会

書誌事項

タイトル別名
  • Distributed Algorithms for the Connectivity of Networks with Faulty Elements

この論文をさがす

抄録

計算機網の複数台の計算機が各々の局所的な情報から,互いにメッセージを交換することにより,ある問題を解くアルゴリズムを分散アルゴリズムと呼ぶ.従来,種々の分散アルゴリズムが提案されているが,これらの多くは連結な計算機網を対象として考えられている.しかし,実際の計算機網では,リンクや計算機に故障が発生することが少なくなく,これらの故障により計算機網が非連結になることがある.計算機網が非連結であると,計算機網に通信不可能な計算機が存在することになり,従来の分散アルゴリズムがうまく動作しない場合がある.従って,計算機網におけるリンクや計算機で故障が発生した場合に計算機網が連結であるかどうかを判定することは重要である.本稿では,まず故障をリンクに限定し,非同期式計算機網においてリンクに故障が発生した場合に計算機網が連結であるかどうかを判定する問題(リンク故障時の連結性判定問題(CLFと呼ぶ))を解く分散アルゴリズムを,以下の1～3の場合について考察する. 1.各計算機が基本情報(自分自身の識別子と接続しているリンク数)だけを保持している場合(基本情報モデル). 2.各計算機が基本情報と隣接計算機の識別子を保持している場合(隣接計算機既知モデル). 3.各計算機が基本情報と計算機網の計算機総数を保持している場合(サイズ既知モデル). 分散アルゴリズムの効率の評価は通信複雑度と理想時間複雑度により行われる.通信複雑度は,計算機網全体で分散アルゴリズムの実行中に交換されるメッセージ総数である.理想時間複雑度は,各計算機の処理時間を無視し,メッセージの伝播時間が単位時間であると考えた場合の分散アルゴリズムの実行時間である.CLFを解く分散アルゴリズムの通信複雑度,理想時間複雑度をそれぞれC,Tと表す.本稿では,基本情報モデルにおいては,CLFを解く分散アルゴリズムが存在しないことを示す.また,計算機網の計算機数,正常リンク(故障していないリンク)数,故障リンク数をそれぞれn,e_f,fと表すとき,隣接計算機既知モデルに対しては,C=O(e_f+min(fn,n^2)),T=O(n)である分散アルゴリズムを示し,C=Ω(max(n,min(fn<logf>/<logn>,n^2)))かつT=Ω(n)であることを示す.サイズ既知モデルに対しては,C=O(e_f+nlogf),T=O(n)である分散アルゴリズムを示し,C=Ω(e_f)かつT=Ω(n)であることを示す.更に,故障をより一般化し,計算機の故障も許す場合には,各計算機が如何なる情報を保持していても連結性判定問題を解く分散アルゴリズムは存在しないことを示す.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ