| 講演名 | 2016-10-27 MRSWレジスタモデルに対するオブリビアス敵対スケジューラ下での無待機乱択合意アルゴリズムの高速化 守屋 宣(近畿大), 井上 美智子(奈良先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | MRSWレジスタによる非同期共有メモリシステムに対する，オブリビアス敵対スケジューラ下での無待機乱択合意アルゴリズムについて考察する．乱択合意アルゴリズムとして，合意確率$1-epsilon$のconciliatorアルゴリズムとadopt-commitアルゴリズムを組み合わせる手法が知られている．MRSWレジスタモデルに対しては，計算量が十分小さいadopt-commitアルゴリズムが存在するため，乱択合意アルゴリズムの計算量はconciliatorアルゴリズムに依存する．本稿では，合意確率は悪くなるが計算量が小さくなるconciliatorアルゴリズムを用いることで，プロセスステップ計算量の期待値が従来法の$O(nloglog{n})$から$O(n)$に改善された無待機乱択合意アルゴリズムを示す．また，シミュレーション実験により，アルゴリズムの実用的な有効性を示す． |
| 抄録(英) | We consider wait-free randomized consensus algorithms with an oblivious adversary in asynchronous shared-memory system using MRSW registers. It is known that the randomized consensus algorithm can be constructed from a conciliator algorithm with agreement probability $1-epsilon$ and an adopt-commit algorithm. In the case of MRSW register models, step complexity of a wait-free randomized consensus algorithm depends on that of a conciliator algorithm, since there exists a sufficiently fast adopt-commit algorithm. In this paper, we propose a wait-free randomized consensus algorithm, in which the expected process step complexity is improved to $O(n)$ from that of the previous best algorithm, $O(nloglog{n})$, by a conciliator algorithm with worse agreement probability and reduced complexity. Furthermore, we show the practical effectiveness of the proposed algorithm by simulated experiments. |
| キーワード(和) | 共有メモリシステム / 無待機アルゴリズム / 乱択合意アルゴリズム / オブリビ アス敵対スケジューラ |
| キーワード(英) | shared-memory system / wait-free algorithm / randomized consensus / oblivious adversary |
| 資料番号 | SS2016-20,DC2016-22 |
| 発行日 | 2016-10-20 (SS, DC) |
| 研究会情報 | |
| 研究会 | DC / SS |
|---|---|
| 開催期間 | 2016/10/27(から2日開催) |
| 開催地（和） | 彦根勤労福祉会館(彦根市) |
| 開催地（英） | Hikone Kinro-Fukushi Kaikan Bldg. |
| テーマ（和） | ソフトウェアシステム, ネットワーク環境でのディペンダビリティ |
| テーマ（英） | Software System and Dependability on Network, etc |
| 委員長氏名（和） | 井上 美智子(奈良先端大) / 緒方 和博(北陸先端大) |
| 委員長氏名（英） | Michiko Inoue(NAIST) / Kazuhiro Ogata(JAIST) |
| 副委員長氏名（和） | 福本 聡(首都大東京) / 中田 明夫(広島市大) |
| 副委員長氏名（英） | Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Akio Nakata(Hiroshima City Univ.) |
| 幹事氏名（和） | 吉村 正義(京都産大) / 金子 晴彦(東工大) / 小林 隆志(東工大) / 肥後 芳樹(阪大) |
| 幹事氏名（英） | Masayoshi Yoshimura(Kyoto Sangyo Univ.) / Haruhiko Kaneko(Tokyo Inst. of Tech.) / Takashi Kobayashi(Tokyo Inst. of Tech.) / Yoshiki Higo(Osaka Univ.) |
| 幹事補佐氏名（和） | / 島 和之(広島市大) |
| 幹事補佐氏名（英） | / Kazuyuki Shima(Hiroshima City Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Dependable Computing / Technical Committee on Software Science |
|---|---|
| 本文の言語 | ENG-JTITLE |
| タイトル（和） | MRSWレジスタモデルに対するオブリビアス敵対スケジューラ下での無待機乱択合意アルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Faster Wait-free Randomized Consensus with an Oblivious Adversary for MRSW Register Model |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 共有メモリシステム / shared-memory system |
| キーワード(2)（和/英） | 無待機アルゴリズム / wait-free algorithm |
| キーワード(3)（和/英） | 乱択合意アルゴリズム / randomized consensus |
| キーワード(4)（和/英） | オブリビ アス敵対スケジューラ / oblivious adversary |
| 第 1 著者 氏名（和/英） | 守屋 宣 / Sen Moriya |
| 第 1 著者 所属（和/英） | 近畿大学(略称：近畿大) Kindai University(略称：Kindai Univ.) |
| 第 2 著者 氏名（和/英） | 井上 美智子 / Michiko Inoue |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara institute of science and technology(略称：NAIST) |
| 発表年月日 | 2016-10-27 |
| 資料番号 | SS2016-20,DC2016-22 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | SS-277,DC-278 |
| ページ範囲 | pp.13-18(SS), pp.13-18(DC), |
| ページ数 | 6 |
| 発行日 | 2016-10-20 (SS, DC) |