高度な故障耐性を有する分散システム実現のための基礎研究

点击翻译按钮获取中文摘要

分散システムの長所の一つは、一部の計算機や通信リンクが故障しても、分散システム全体の機能は停止せず、正常な部分でサービスを継続できることである。そのようなサービスを実現するためには、故障耐性のある分散アルゴリズムの設計/開発が必要である。本研究では、故障耐性のある分散アルゴリズムの中でも、一時故障に対する高い故障耐性からその実用化が期待されている自己安定アルゴリズムについて研究を行い、以下の結果を得た。1.永久故障に対する故障耐性を有する自己安定アルゴリズムに関する研究:自己安定アルゴリズムは一時故障に対する高い故障耐性を有するが、一方、永久故障に対する故障耐性を考慮していない。自己安定アルゴリズムを実用化するには、永久故障に対しても故障耐性を有する自己安定アルゴリズムの設計/開発が必要である。永久故障に対する高い故障耐性を実現する方法として、無待機アルゴリズムが有望視されている。本研究では、無待機アルゴリズムに関する研究を行い、時計合わせ問題に対して、同期時間最適な無待機アルゴリズムの設計を行った。2.小規模で局所的な一時故障からの復旧を効率よく行なう自己安定アルゴリズムに関する研究:自己安定アルゴリズムが解を求めて安定している状況で、計算機の新たな一時故障によりネットワーク状況が変動すると、自己安定アルゴリズムは、新たに解を求める。実際のネットワークでは、このような一時故障によるネットワーク状況の変動は、小規模で局所的なものがほとんどである。本研究では、小規模で局所的な変動に対して、効率よく解を求めて安定する強安定アルゴリズムに関する研究を行い、リングネットワークでの相互排除問題に対して、巡回ラウンド数最適な強安定アルゴリズムの設計を行った。