安定後の1故障を考慮したリングでの自己安定相互排除プロトコルに関する研究

上田 英一郎 (9551011)


複数の自律プロセッサとプロセッサ間の通信リンクからなるネットワーク での故障耐性プロトコルの研究が盛んに行われている。 1つの有力な故障耐性プロトコルとして、自己安定プロトコルがある。 自己安定プロトコルとは、任意のネットワーク状況から実行を開始しても解 を求めて安定するプロトコルである。この性質から、自己安定プロトコルは 任意の一時故障に耐性がある。

このような自己安定プロトコルに対して、 1故障状況(正当な状況から、1プロセスの 一時故障により到達する状況)から実行を開始した場合に、 特権を持つ非故障プロセスが高々1つであることを保証するような 相互排除問題を解く自己安定プロトコルについて考察する。 このようなプロトコルを強安定相互排除プロトコル呼ぶ。

強安定相互排除プロトコルの今までの結果としては、Hermanによる 既知の結果が存在する。 この既知の結果では強安定相互排除プロトコルの1つの評価尺度である 巡回ラウンド数ついて、上界と下界の間に差が存在していた。 本研究ではこの差を埋めるような結果を提案している。

本発表ではまず対象とした分散システムのモデルについて定義し、 強安定プロトコルの定義、有効性について考察する。 また、強安定相互排除プロトコルの評価尺度である巡回ラウンド数に ついて簡単に説明する。

次に提案した巡回ラウンド数が最適である強安定相互排除プロトコルの アイデアと計算量について議論し、最後にまとめを行う。