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

自动推导分布式系统中执行效率高的容错运动程序

基本信息

批准号：
06780258
负责人：
岡野浩三
金额：
$ 0.58万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780258/
关键词：
プロトコル仕様動作仕様耐故障プロトコル合成

项目摘要

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

在本研究中，我们开发了一种方法，可以根据分布式系统高度抽象的整体规范自动生成每个节点的操作规范（程序），同时交换消息以进行同步和数据交换。论文（冈野幸三、今城宏、东野辉夫、谷口Kenichi：“使用扩展的有限状态机模型从分布式系统的需求描述中自动推导每个节点的操作规范”，《日本信息处理学会汇刊》，第 34 卷，第 6 期，第 1290-1301 页。，（1993-基于6）中的想法），我们扩展了操作规范所使用的网络环境的类别。这种扩展使我们能够防止节点之间的通信链路发生故障。现在可以自动导出一组操作规范，即使消息丢失，这些操作规范也可以按照整体规范进行操作，而不会发生故障。对于每个操作规范，为了容错，可以简单地增加通信消息的数量或设置一个简单的超时。在不引入任何机制的情况下，通过有效地利用消息信息来减少消息总数。为了减少消息总数，我们正式定义了推导问题。然后，我们决定了总体规范的模仿策略，通常会最小化执行步骤的数量，并基于此，我们使用整数线性规划问题求解方法来找到消息总数的最小解决方案。规范组的设计避免了不必要的消息发送和接收，具有良好的运行效率。 2．我们准备了两种方法，一种使用线性规划问题求解方法，另一种使用近似求解方法，并进行了比较。结果，我们发现对于节点较少的程序，可以使用整数我们确认可以在足够的时间内导出该算法以供实际使用。3.作为未来的工作，我们正在考虑引入一种从节点故障中自动恢复的自稳定算法。