| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-03-10 14:15 オブリビアス敵対スケジューラ下でのMRSWレジスタを用いた乱択合意アルゴリズム ○中島 悟・井上美智子（奈良先端大）  COMP2013-68 |
|
| 抄録 | （和） | 本研究では, 共有メモリ分散システム上において, オブリビアス敵対スケジューラ下で乱択合意アルゴリズムを提案する. 乱択合意アルゴリズムを$1-epsilon (0< epsilon < 1)$の確率で合意をとるConciliatorアルゴリズムとAdopt-Commitオブジェクトから構成する手法が知られている. 本研究では, Multi-Reader Single-Writer(MRSW)レジスタを用いた, Conciliatorアルゴリズムを提案する. 提案したConciliatorアルゴリズムの時間計算量に関しては, 上界が既存手法と漸近的に等しいことを証明する. また, 計算機実験を用いて, 提案したConciliatorアルゴリズムが, 既存手法と比べて, 同じ合意確率に対して時間計算量が優れていることを示す. そして, その結果から, 提案した乱択合意アルゴリズムが既存手法よりも優れていることを示す. |
| （英） | In this paper, we propose an efficient randomized consensus algorithm in distributed shared register model under an oblivious adversary. The randomized consensus algorithm is known to be constructed by a Conciliator algorithm and an Adopt-Commit object. In this paper, we propose a Conciliator algorithm using Multi-Reader Single-Writer(MRSW) registers. We first show that the upper bound of time complexity of the proposed Conciliator algorithm is asymptotically equal to existing algorithms. We also evaluate the time complexity of the proposed Conciliator algorithm by experiments. Experimental results show that the time complexity of the proposed Conciliator algorithm is more effective than the conventional method for the same agreement probability, and therefore, obtain an efficient randomized consensus algorithm. |
|
| キーワード | （和） | 分散アルゴリズム / MRSWレジスタモデル / 乱択合意問題 / オブリビアス敵対スケジューラ / / / / |
| （英） | distributed algorithm / MRSW register model / randomized consensus problem / oblivious adversary scheduler / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 488, COMP2013-68, pp. 53-60, 2014年3月. | |
| 資料番号 | COMP2013-68 | |
| 発行日 | 2014-03-03 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-68 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-03-10 - 2014-03-10 |
| 開催地（和） | 明治大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | オブリビアス敵対スケジューラ下でのMRSWレジスタを用いた乱択合意アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Randomized consensus algorithm using MRSW registers under oblivious adversary |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(2)（和/英） | MRSWレジスタモデル / MRSW register model |
| キーワード(3)（和/英） | 乱択合意問題 / randomized consensus problem |
| キーワード(4)（和/英） | オブリビアス敵対スケジューラ / oblivious adversary scheduler |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中島 悟 / Satoru Nakajima / ナカジマ サトル |
| 第1著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第2著者 氏名（和/英/ヨミ） | 井上 美智子 / Michiko Inoue / イノウエ ミチコ |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-03-10 14:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-68 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.488 |
| ページ範囲 | pp.53-60 |
| ページ数 | 8 |
| 発行日 | 2014-03-03 (COMP) |
[研究会発表申込システムのトップページに戻る]