| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-12-03 10:05 局所発見不可能な故障のゲーム理論的分析 ○木庭 淳・菊田健作（兵庫県立大）  COMP2008-47 |
|
| 抄録 | （和） | 局所発見不可能な複数個の故障を発生させる悪意のある敵を想定する。 そのような故障の可能性はかつて指摘されていたが、その影響と分析に関する詳細な研究 は知られていなかった。ここでは互いに補完しあう２つの自己安定的相互排除プロトコル を組み合わせて悪意のある故障を仮定する。我々はマイナートークン を送るか否かの２つの選択的戦略を用いることによりこの故障に対処する。ここで マイナートークンは特権を与えるためのメジャートークンとペアで用いられ、 故障の拡散を防ぐ役割を担う。特権をもつプロセス群対悪意をもつ敵の 利得行列を構成し、多段階２人ゼロ和ゲームを考える。ここでは2種類のゲームの解釈 ---Dijkstra的故障回復動作が起こったときゲームを終了するか否か---を行い、各場合 において悪意のある敵の能力分析を混合戦略を用いて行う。我々の方法は悪意のある敵 に対してアルゴリズムを強化する一般的な枠組みとして考えることができる。 |
| （英） | We consider a malicious adversary which generates multiple undetectable faults by local checks. Though the possibility of such faults has ever been suggested, details of its influence and handling are unknown. We assume the malicious faults in a self-stabilizing mutual exclusion protocol, a hybrid of previously proposed ones that complement each other. In the hybrid protocol, we can cope with the faults by using optional strategies, sending a minor token or not, where the minor token plays a role of preventing the contamination from spreading. We construct a payoff matrix between a group of privileged processes and an adversary, and consider a multistage two-person zero sum game. We interpret the game in two ways: whether or not it terminates when Dijkstra-like repair, i.e., moves against malicious faults, occurs. For each case, we evaluate the ability of malicious adversary by using a mixed strategy. Our idea is also considered as a general framework for strengthening an algorithm against malicious faults. |
|
| キーワード | （和） | 自己安定 / 相互排除 / 収束下の安全性 / 悪意のある故障モデル / ゲーム理論 / 多段階２人ゼロ和ゲーム / / |
| （英） | self-stabilization / mutual exclusion / safety under convergence / malicious fault model / game theory / multistage two-person zero sum game / / | |
| 文献情報 | 信学技報, vol. 108, no. 330, COMP2008-47, pp. 7-14, 2008年12月. | |
| 資料番号 | COMP2008-47 | |
| 発行日 | 2008-11-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-47 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-12-03 - 2008-12-03 |
| 開催地（和） | 群馬大学 |
| 開催地（英） | Gunma Univ. |
| テーマ（和） | 情報処理学会アルゴリズム研究会との共催 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-12-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 局所発見不可能な故障のゲーム理論的分析 |
| サブタイトル（和） | |
| タイトル（英） | Game Theoretic Analysis of Malicious Faults Which are Undetectable by Local Checks |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 自己安定 / self-stabilization |
| キーワード(2)（和/英） | 相互排除 / mutual exclusion |
| キーワード(3)（和/英） | 収束下の安全性 / safety under convergence |
| キーワード(4)（和/英） | 悪意のある故障モデル / malicious fault model |
| キーワード(5)（和/英） | ゲーム理論 / game theory |
| キーワード(6)（和/英） | 多段階２人ゼロ和ゲーム / multistage two-person zero sum game |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 木庭 淳 / Jun Kiniwa / キニワ ジュン |
| 第1著者 所属（和/英） | 兵庫県立大学 (略称： 兵庫県立大) University of Hyogo (略称： Univ. Hyogo) |
| 第2著者 氏名（和/英/ヨミ） | 菊田 健作 / Kensaku Kikuta / キクタ ケンサク |
| 第2著者 所属（和/英） | 兵庫県立大学 (略称： 兵庫県立大) University of Hyogo (略称： Univ. Hyogo) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-12-03 10:05:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-47 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.330 |
| ページ範囲 | pp.7-14 |
| ページ数 | 8 |
| 発行日 | 2008-11-26 (COMP) |
[研究会発表申込システムのトップページに戻る]