分散システムにおける実行効率の良い耐故障性動体プログラムの自動導出

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

本研究では,分散システムの抽像度の高い全体仕様から,同期やデータ交換のためにメッセージ交換をしながら全体として全体仕様通りに動作する各ノードの動作仕様(プログラム)を自動生成する方法を扱う.1.まず,論文(岡野 浩三,今城 広志,東野 輝夫,谷口 健一:"拡張有限状態機械モデルを用いた分散システムの要求記述から各ノードの動作仕様の自動導出",情報処理学会論文誌,Vol.34,No.6,pp.1290-1301,(1993-6))のアイデアをもとに,動作仕様群の使用するネットワーク環境のクラスの拡張を行なった.この拡張により,ノード間を結ぶ通信リンクの故障によるメッセージ消失が生じても,誤動作せずに全体仕様通り動作する動作仕様群が自動導出可能になった.各動作仕様においては,耐故障性のために,単純に通信メッセージを増やしたり,単純なタイムアウト機構を導入したりせずに,メッセージ情報を効率よく用いてメッセージ総数を少なくする.メッセージ総数を少なくするために,導出問題を形式的に定義し,実行ステップ数が一般に最小になる全体仕様の模倣方針を決定し,そのもとで,整数線形計画問題の解法を用い,メッセージ総数の最小解を求める方法となった.よって,得られた動作仕様群は,不必要なメッセージ送受信を行わないようになっており,動作効率もよい.2.このアルゴリズムに基づいて動作仕様群自動導出システムを作成した.整数線形計画問題の解法を用いるものと,近似解法を用いるものと2つを用意し,これらの比較も行なった.この結果,数ノードの規模のプログラムであれば整数線形計画問題の解法を用いても十分実用時間内に導出できることを確認した.3.今後の課題として,ノード故障に対して,自津的に故障から修復する自己安定アルゴリズムの導入を検討している.