故障発生時における計算機網の連結性を判定する分散アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1990-01-31
• タイトル: 故障発生時における計算機網の連結性を判定する分散アルゴリズム
• タイトル / 言語: en
• タイトル: Distributed algorithms for connectivity of networks with faulty elements
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: オムロン（株）
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): OMRON Corporation
• 著者名: 和田, 幸一; 守谷, 幸男; 川口, 喜三男; 森下正浩
• 著者名(英): Koichi, Wada; Yukio, Moritani; Kimio, Kawaguchi-Izawa; Masahiro; Morishita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，非同期式計算機網において計算機やリンクに故障が生じたときの計算機網の連結性を判定する分散アルゴリズムの存在性や通信複雑度と理想時間複雑度の上界及び下界について考察する．故障計算機や故障リンクに隣接あるいは接続する計算機がその故障を検知する機構をもつと仮定する．また，計算機が故障する場合と故障をリンクのみに限定した場合に分けて考察する．特に，後者の場合は，対象とする計算機網を各計算機が保持する計算機網情報によって分類し，基本情報（自分の識別子と接続リンク数）のみの場合，基本情報と隣接計算機の識別子の場合，基本情報と計算機網のサイズの場合について考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider asynchronous distributed algorithms for the connectivity of a network with faulty elements. It is assumed that every node can detect the faults of adjacent nodes and incident links automatically. We discuss such algorithms in the following cases: (1)faults occur at nodes, (2)faults occur only at links. In case (2), networks are classified three classes by the information about the network topology each node knows. (a) Each node knows its identity and the number of incident links (called basic information). (b) Each node knows the basic information and the identities of neighbor nodes. (c) Each node knows the basic information and the size of the network. We show that there do not exit such algorithms in case (1) and (2-a) and discuss the upper and lower bounds on the communication complexity and the ideal time complexity in case (2-b) and (2-c).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 9(1989-AL-013), p. 1-8, 発行日 1990-01-31
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会