分散合意のための1ビットメッセージ最適早期停止アルゴリズム

• Item type: Journal(1)
• 公開日: 1998-01-15
• タイトル: 分散合意のための1ビットメッセージ最適早期停止アルゴリズム
• タイトル / 言語: en
• タイトル: An Optimal Early Stopping Algorithm with One - bit Messages for Distributed Consensus
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: 京都大学大学院工学研究科／現在，IBM東京基礎研究所
• 著者所属: 京都大学大型計算機センター
• 著者所属: 京都大学大型計算機センター
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Kyoto University/Presently with IBM Tokyo Research Laboratory
• 著者所属(英): en
• 著者所属(英): Kyoto University Data Processing Center
• 著者所属(英): en
• 著者所属(英): Kyoto University Data Processing Center
• 著者名: 依田, 邦和; 岡部, 寿男; 金澤, 正憲
• 著者名(英): Kunikazu, Yoda; Yasuo, Okabe; Masanori, Kanazawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散合意問題は，同期式通信を行う分散システムにおいて，0または1の初期値を持つ正常プロセッサ達が，故障プロセッサ達のいかなる振舞いにもかかわらず，自分達のうちのどれかが持っていた初期値を共通に決定するための通信アルゴリズムを与える問題である．本研究ではラウンド数と最大メッセージビット数が同時に最適の早期停止アルゴリズムを示す．早期停止アルゴリズムとは，アルゴリズム終了までのラウンド数が，最大故障数ではなく実際の故障数に比例するものである．システムがn個のプロセッサからなり，そのうち最大t個が故障している可能性があり，実際の故障数はfであるとする．このアルゴリズムでは，全プロセッサ数n〓（4t＋1）（t＋1）のシステムにおいて，1ビットのメッセージを用いてラウンド数r＝min｛f＋2，t＋1｝で合意に到達する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Distributed Consensus is a problem of protocols by which all correct processors agree on a common binary value that was initially held by any of them,regardless of any behavior of faulty processors,on a synchronous distributed system.We present an early stopping algorithm(i.e.,the number of rounds is proportional to the number of actual faults f,not the number of possibly faulty processors t)with one-bit messages.The algorithm achieves a consensus using one-bit messages within r=min｛f+2,t+1｝rounds on a system where the number of prosessors is n〓(4t+1)(t+1).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 39, 号 1, p. 11-16, 発行日 1998-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764