固有の識別番号を仮定しないネットワークにおけるリーダー選挙問題
スポンサーリンク
概要
- 論文の詳細を見る
ネットワークはプロセッサの集合とプロセッサ間を結ぶ通信リンクの集合から構成される.従来,プロセッサが固有の識別番号をもつという仮定の下で,ネットワーク上の様々な問題,例えば,リーダー選挙問題,生成木構成問題,トポロジー認識問題などを効率良く解く(分散)アルゴリズム(あるいはプロトコル)に関する研究が数多くなされてきた(たとえば,萩原[2]はその概説).事実,プロセッサが固有の識別番号をもつとすると,ネットワーク・トポロジーやプロセッサ数などのネットワークの属性に関する情報が全く利用できないと仮定しても,任意のネットワークに対して,上に挙げたそれぞれの問題を解くアルゴリズムが容易に構成でき,問題はいかに効率の良いアルゴリズムを構成するかという一点に集約される.プロセッサが識別番号をもたない(あるいは全てのプロセッサが同じ識別番号をもつ)ようなネットワークをアノニマス・ネットワークと呼ぶ.アノニマス・ネットワークに対してはAngluin[1]やJohnsonとSchneider[3]が(異なるモデルを用いて)リーダー選挙問題を解くアルゴリズムが存在しないネットワークが存在することを示し,アルゴリズムが存在するための必要条件や十分条件について考察した.また,YamashitaとKameda[4]は以下の3つの場合,(1)ネットワークのプロセッサ数の上限が既知,(2)ネットワークのプロセッサ数が既知,(3)ネットワークのトポロジーが既知,について上に挙げたそれぞれの問題が解けるネットワークのクラスを明らかにした.本稿ではプロセッサが固有の識別番号をもつと仮定できないようなネットワークにおいてリーダー選挙問題が解けるための条件を考察する.従って,本稿の結果はアノニマス・ネットワークに対する同様の結果を特別な場合として含む.直感的に言えば,リーダーが選挙できるための必要十分条件は何らかの意味で特別なプロセッサが存在することである.そこで,プロセッサ間の『類似(similarity)』関係を[4]で用いたプロセッサのビューと呼ばれる概念によって定式化し,任意のプロセッサに対して類似なプロセッサが存在するようなネットワークを特徴付ける.類似関係にある二つのプロセッサは同じ結果を出力する可能性があることが示せ,上記の特徴付けはネットワークの上でリーダーが選挙できるための必要十分条件となっている.
- 一般社団法人情報処理学会の論文
- 1988-09-12
著者
関連論文
- 有限視野を持つ群ロボットのための一点収束アルゴリズムとその誤差に対する強度の評価
- 視野に制約のあるロボットによる一点集合と合意の問題
- アドホックネットワーク向けトークン巡回自己安定分散アルゴリズム
- A Universal Self-Stabilizing Mutual Exclusion Algorithm (New Developments of Theory of Computation and Algorithms)
- 単方向リングネットワークでの一様なランダム化自己安定相互排除
- 分散システムにおける資源割り当てアルゴリズム(計算量理論)
- 双方向リングネットワーク上での自己安定2:相互排除(計算機構とアルゴリズム)
- 拡張された分散$k$-相互排除(計算量理論)
- 拡張された分散κ-相互排除
- 統一的中間表現を用いた自動並列化コンパイラの実装 : ソースコードから統一的中間表現への変換
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- Visual Debugger における履歴情報の保存と利用
- 多角形を捜索するために必要な捜索者数について
- Cooperative Control Algorithms for Anonymous Mobile Robots
- ニューロコンピュータAN1における組合せ最適化問題の解法と問題点
- 世界規模分散ファイルシステムSKINNY
- リングネットワークにおける一様な自己安定 k-相互排除システム
- リングネットワークにおける一様な自己安定k-相互排除システム
- 自己安定相互排除アルゴリズムの実験的評価とその改良
- リングの方向付け問題を有限状態数で解く自己安定アルゴリズム(アルゴリズムと計算量理論)
- システム統合化をめざしたLAN(UNINET) : その3.ソフトウェア分割作成システムとしての評価
- リアルタイム・ネットワークのためのニューラル・スケジューラ
- 分散システムの一つのスケジューリング問題(アルゴリズムの数学的基礎理論とその応用)
- 広域ネットワーク向きファイルキャッシュプロトコルの実験的評価
- $k$-コータリのgraph-nondominatednessについて (アルゴリズムと計算の理論)
- 分散相互排除システムの可用度を改善するコーラム再割当アルゴリズム(計算理論とその応用)
- 分散相互排除システムの可用度を改善するコーラム再割当アルゴリズム
- グラフ上の相互排除のためのNDコータリ
- WAN向きファイルキャッシュプロトコルSCAUPの提案とその正当性の検証
- ニューラルネットワークによる組合せ最適化問題の一般的解法
- ストリーム中の頻出アイテム発見に対するO(loglogN) 領域乱択アルゴリズム
- ATMスイッチにおける三段階スケジューリング法の提案とその評価
- ATMスイッチにおける三段階スケジューリング法の提案とその評価
- ATMスイッチにおける三段階スケジューリング法の提案とその評価(並列・分散)
- リングネットワ-クにおけるリ-ダ選挙アルゴリズムの実験的評価
- アルゴリズム駆動ニューロコンピュータAN1 : (2)直交アーキテクチャ
- システム統合化をめざしたLAN(UNINET) : その2.トランスポート層までサポートするT-LAN
- 多重バス結合並列プロセッサのための最適時間ソーティングアルゴリズム (並列処理)
- サイモン・フレーザー大学計算科学科の紹介(海外情報)
- LANにおける自律管理システムに関する研究 : ユーザー管理と共有ファイルシステム管理
- 侵入者は見つかるか : 美術館捜索問題
- 分散競合解消問題
- 3. 分散相互排除問題とコータリ (<特集> フォールトトレラント分散システム向けアルゴリズム)
- 分散アルゴリズムについて(パラレル・アルゴリズム)
- ビザンティン合意問題 : 信頼性の低い分散ネットワーク上での合意問題
- ホップフィ-ルドニュ-ラルネットワ-クによる実数集合の分割 (ニュ-ロコンピュ-ティング論文)
- プロダクションシステムのための並列マッチング方式とマルチプロセッサによる一評価
- システム統合化をめざしたLAN(UNINET) : その4.分散システム構築の一実験
- 3SAT問題のニューラルネットワーク解法(理論計算機科学とその周辺)
- 分散環境で動作する分散アルゴリズムシミュレータ
- 1-D-3 グラフ上のランダムウォークとその高速化(特別セッション 若手によるOR横断研究)
- DS-1-16 完全非同期ロボットによるパターン形成(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 ストリーム中の頻出アイテム発見に対するO(loglogN)領域乱択アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 無理数遷移確率ランダムウォークの脱乱択化
- 書き換え型プロダクションシステムのための高速マッチングアルゴリズム
- ニューロコンピュータAN1における並列処理
- 固有の識別番号を仮定しないネットワークにおけるリーダー選挙問題
- 2-B-1 パリティ最長路問題(離散最適化(4))
- 1-F-9 無理数の遷移確率をもつランダムウォークの脱乱択化(確率モデル(3))
- 1-B-7 ラーマングラフの局所遷移可能性(離散最適化(2))
- 計算機ネットワークに自律的に適応する分散システムの検討
- ストリームに対するO(loglogn)領域を用いたReservoir sampling(一般)
- DS-1-14 関数ルーターモデルの提案(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 森および連結全域部分グラフの乱択近似数え上げ(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-17 動的グラフ上のランダムウォークの到達時間と全訪問時間(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 安定結婚問題における最大最適選好マッチングの頂点集合の一意性(一般)
- 関数ルーターモデルによるハイパーキューブ上ランダムウォークの脱乱択化(一般)