故障が存在する計算機網に対する連結性判定分散アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
非同期式計算機網において計算機やリンクに故障が存在する計算機網の連結性を判定する分散アルゴリズムについて考察する．ここでは，故障計算機や故障リンクに隣接あるいは接続する計算機はその故障を検知する機構をもつと仮定する．分散アルゴリズムでは，各計算機がアルゴリズム実行前に計算機網に関していかなる情報を保持しているかによって，分散アルゴリズムが存在するか否か，またその効率が左右される．本論文では，計算機が故障する場合と故障をリンクのみに限定した場合に分けて議論し，前者の場合には，計算機綱に関するいかなる情報を保持していても，連結性を判定する分散アルゴリズムは存在しないことを示す．後者に対しては，基本情報（自分の識別子と接続リンク数）のみを保持する場合，基本情報と隣接計算機の識別子のみを保持する場合，基本情報と計算機網のサイズのみを保持する場合について，分散アルゴリズムの存在いかん，存在するならばその通信複雑度と理想時間複雑度の上下界を考察する．
- Institute of Electronics, Information and Communication Engineersの論文
- 1991-02-20
著者
関連論文
- ソート集合のある分割に対する並列アルゴリズムについて
- マルチメディアを用いた導入教育
- 命令再構成型VLIWプロセッサV++における2つの再構成機能の評価
- バリア同期のためのタスクスケジューリングアルゴリズムとその性能評価
- 命令再構成型VLIWプロセッサV++における適応型再構成戦略
- 重複可能なバリア型同期のための最適バリアスケジューリング
- 概念制約式を用いたプログラミングを可能にするコンパイル手法
- バリアを唯一の同期手段とした場合のタスクスケジューリング
- 自己組織系集団による通信の進化の試み
- ランギーII:仮想的生物による通信の進化
- 複数種の生物集団の共存する人工生命環境の設計
- 概念制約式を用いたプログラミングとプログラム合成
- 星状多角形内の同期式自律分散ロボットの一点集合問題
- 2連結グラフに対するATM網に適した最適な耐故障性ルーティング
- 点集合の強凸-包含を求めるアルゴリズム
- スーパーキューブの耐故障性について
- 2辺連結グラフの4分割について
- グラフのあるk-分割問題に対する効率的なアルゴリズムについて
- 重みつきグラフのk分割問題について
- 3個の空位をもつN×M-平面自動倉庫(N,M≧3)の最小歩数関数
- 異なる半径の数を限定した円集合の凸包を求める最適並列アルゴリズム
- 誤差耐性のある強凸包構成問題に対する並列解法
- 拡張超立方体グラフに対する耐故障性路線割当と直径罹障度
- 円集合の凸包を求める効率の良い並列アルゴリズム
- コンパイラ教育支援システムにおける属性文法に基づく意味解析系提示ツールの作成
- アルゴリズムの可視化に基づくコンパイラ教育支援システム
- k-辺連結有向(無向)グラフに対する高信頼性路線割当の存在条件と計算量
- 通信網に対する高信頼性最適路線割当ての存在条件と計算量の改善
- 3個の空位を持つN×M-平面自動倉庫の最小歩数関数
- 連結グラフの(L,κ)-辺分割線形時間アルゴリズムとκ-辺連結グラフに対する高信頼性路線割当
- 3連結グラフにおける3-独立木構成アルゴリズムと2点間の内点独立路を求めるアルゴリズム
- 非阻塞グラフに関する一考察
- 故障発生時の連結性判定問題を解く分散アルゴリズムについて
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当
- 多重サイクルグラフ上の高信頼性路線割当の構成
- 故障耐性の高い路線割当をもつ通信網の構成問題
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 有向,無効グラフに対する最適なt-spannerの構成について
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 一般のグラフの埋込み面積のMax-Min下界
- 多重サイクルグラフ上の高信頼性路線割当ての構成
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 故障が存在する計算機網に対する連結性判定分散アルゴリズム
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 一般のグラフの埋込み面積のMax-Min下界
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当