WEKO3
アイテム
任意形状の非同期ネットワークにおける耐故障リーダ選挙について
https://ipsj.ixsq.nii.ac.jp/records/32514
https://ipsj.ixsq.nii.ac.jp/records/325145c0cfa0e-5213-4149-b7d2-c43e0b2a9c91
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL92030016.pdf (1.6 MB)
|
Copyright (c) 1992 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1992-11-20 | |||||||
| タイトル | ||||||||
| タイトル | 任意形状の非同期ネットワークにおける耐故障リーダ選挙について | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | On Leader Election for Faulty Asynchronous Networks with Arbitrary Topology | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 広島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 広島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 広島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 広島大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima University | ||||||||
| 著者名 |
松本, 哲也
× 松本, 哲也
|
|||||||
| 著者名(英) |
Tetsuya, Matsumoto
× Tetsuya, Matsumoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 分散アルゴリズムの基本的問題の1つにリーダ選挙問題がある．本研究では，リンク故障を含むと仮定した任意形状の完全非同期ネットワークにおけるリーダ選挙問題について考察を行う．まず，各プロセスが固有の識別子をもち，ネットワークサイズと故障リンク数の上限値を初期情報としてもっとしたとき，リーダ選挙問題に対するメッセージ数O（+nlog^)，メッセージサイズO()ビットの終了検知を伴うアルゴリズムを提案する．ここでnはネットワーク中のプロセス数，mはリンク数である．次に，各プロセスがネットワークサイズを初期情報としてもつとしても固有の識別子をもたなければリーダ選挙問題は解けず，たとえ各プロセスが独立に確率的選択を行うランダム化アルゴリズムを用いても解けないことを示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Leader election is one of the basic problems on distributed networks. In this paper, leader election for fully asynchronous distributed networks with arbitrary topology with link faults is considered. First, when every process has a unique identifier and knows the size of network and the upper bound of number of link faults as initial information, we propose an algorithm for leader election with termination detection that uses O(m+nlog^2n) messages, each of size O(logn) bits, where n and m are then number of processes and links, respectively, in the network. Next, when every process knows the size of network but doesn't have unique identifiers, we show that even if a randomized algorithm that can execute random selection locally is used, leader election cannot be solved. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1992, 号 94(1992-AL-030), p. 143-152, 発行日 1992-11-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
