WEKO3
アイテム
プロセッサとリンクの故障が混在する完全ネットワークにおける分散アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32646
https://ipsj.ixsq.nii.ac.jp/records/326465828aa71-5b47-4a34-a5c6-d592574d2a84
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL90015002.pdf (1.3 MB)
|
Copyright (c) 1990 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1990-05-17 | |||||||
| タイトル | ||||||||
| タイトル | プロセッサとリンクの故障が混在する完全ネットワークにおける分散アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Distributed Algorithms in Complete Networks with Link and Processor Failures | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部 | ||||||||
| 著者所属 | ||||||||
| 大阪大学情報処理教育センター | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculy of Engineering Science Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Education on Center for Information Processing Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculy of Engineering Science Osaka University | ||||||||
| 著者名 |
西川, 直樹
× 西川, 直樹
|
|||||||
| 著者名(英) |
Naoki, Nishikawa
× Naoki, Nishikawa
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | プロセッサとリンクの故障が混在する完全ネットワークにおける放送問題とリーダー選択問題の通信計算量について考察し，リンクとプロセッサがそれぞれ高々f_P，f_L個故障する完全ネットワーク（はプロセッサ数）で以下の結果を得た．（）方向感覚付き完全ネットワーク上の放送問題はΘ（+f_L・f_P+f_L・logf_）（）方向感覚のない完全ネットワーク上の放送問題はΘ（+n・f_）（）方向感覚付き完全ネットワーク上のリーダー選択問題はΘ（+k（_P+f_）+f_L・f_P+f_L・logf_）．ただし，kは起動プロセッサ数を示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper considers fault-tolerant distributed algorithms in asynchronous complete networks with undetectable fail-stop link and processor failures. The problems studied in this paper are the broadcast problem and the leader election problem, and the followings are shown for complete networks with n processors and at most f_L faulty links and at most f_P faulty processors. (1) The message complexity of broadcast is Θ(n+f_L・f_P+f_L・logf_L), if global sence of direction is available, while (2) the message complexity is Θ(n+n・f_L), if no global sence of direction is available. (3) The message complexity of leader election is Θ(n+k(f_P+f_L)+f_L・f_P+f_L・logf_L) where k represents the number of initiator processors start the algorithm, if global sence of direction is available. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1990, 号 37(1990-AL-015), p. 1-8, 発行日 1990-05-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
