| 講演名 | 2008-12-03 局所発見不可能な故障のゲーム理論的分析 木庭 淳, 菊田 健作, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 局所発見不可能な複数個の故障を発生させる悪意のある敵を想定する。そのような故障の可能性はかつて指摘されていたが、その影響と分析に関する詳細な研究は知られていなかった。ここでは互いに補完しあう2つの自己安定的相互排除プロトコルを組み合わせて悪意のある故障を仮定する。我々はマイナートークンを送るか否かの2つの選択的戦略を用いることによりこの故障に対処する。ここでマイナートークンは特権を与えるためのメジャートークンとペアで用いられ、故障の拡散を防ぐ役割を担う。特権をもつプロセス群対悪意をもつ敵の利得行列を構成し、多段階2人ゼロ和ゲームを考える。ここでは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. |
| キーワード(和) | 自己安定 / 相互排除 / 収束下の安全性 / 悪意のある故障モデル / ゲーム理論 / 多段階2人ゼロ和ゲーム |
| キーワード(英) | self-stabilization / mutual exclusion / safety under convergence / malicious fault model / game theory / multistage two-person zero sum game |
| 資料番号 | COMP2008-47 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2008/11/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 局所発見不可能な故障のゲーム理論的分析 |
| サブタイトル（和） | |
| タイトル（英） | 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)（和/英） | 多段階2人ゼロ和ゲーム / multistage two-person zero sum game |
| 第 1 著者 氏名（和/英） | 木庭 淳 / Jun KINIWA |
| 第 1 著者 所属（和/英） | 兵庫県立大学経済学部応用経済学科 Department of Applied Economics, University of Hyogo |
| 第 2 著者 氏名（和/英） | 菊田 健作 / Kensaku KIKUTA |
| 第 2 著者 所属（和/英） | 兵庫県立大学経営学部組織経営学科 Department of Strategic Management, University of Hyogo |
| 発表年月日 | 2008-12-03 |
| 資料番号 | COMP2008-47 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 330 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |