分散システムにおける相互排除機構の高信頼化に関する研究

分布式系统中互斥机制增强可靠性研究

• 批准号: 10780190
• 负责人: 土屋 達弘
• 金额: $ 0.64万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10780190/
• 关键词: 分散システム; 相互排除問題; クォーラム; コテリー; 信頼性; 相互排除; ネットワーク

分散システムにおいて相互排除問題は最も基本的かつ重要な問題として知られている。分散相互排除機構にはトークン方式とコテリー方式があるが、信頼性の面で後者の方式が優れている。コテリーは交叉条件とよばれる条件をみたすプロセスの集合族であり、相互排除機構の信頼性は、機構が採用するコテリーに依存して決まる。本研究では、コテリー方式の分散相互排除機構について、その信頼性が最大になるようなコテリーを求める方法を開発した。具体的には、まずプロセスの集合族がコテリーとなる条件を制約式で表現することによって、この問題を0-1整数計画法の問題として定式化した。そして、定式された問題を計算機を用いて解くためのプログラムを、良く知られた解析ソフトウェアLINDOを組み入れることで実装した。これにより、分散システムの形状、各構成要素(プロセス及び通信リンク)の信頼を入力として、信頼性最適なコテリーを求めることが可能になった。次に、この提案手法が現実的にどの程度の規模のシステムに対して適用可能か、必要な計算時間やメモリ量に関する評価実験によって分析を行った。その結果、プロセス数が10程度の場合であれば、現実的な時間かつメモリ量で最適なコテリーが求められることが分かった。更に、新たな高速な相互排除機構の信頼性評価法を開発し、この評価法を利用して、提案法と既存のヒューリスティックによって得られたコテリーを用いた場合との比較評価を信頼性に関して行った。その結果、提案法によって得られるコテリーを採用することで、相互排除機構の故障確率を半減できることが分かった。

Decentralization is the most fundamental problem of mutual exclusion. Decentralized mutual exclusion mechanism is the best way to improve the reliability of the system. The condition of intersection is set to exclude the reliability of the organization. This study develops a method to maximize the reliability of decentralized mutual exclusion mechanisms. The problem of the integer method of 0-1 is formulated according to the constraint expression of the set of concrete problems. The problem is solved by computer, and the problem is solved by computer. The shape of the distribution system, the information penetration of each component element (including the distribution system and the communication system), and the information optimization are possible. For example, the proposed method is applicable to the evaluation of the possible and necessary calculation time. When the number of results is 10, the number of results is 10. When the number of results is 10, the number of results is 10. The new method of evaluating the reliability of a high-speed communication system is developed and used. As a result, the proposed law has been adopted, and the accuracy of mutual troubleshooting institutions has been reduced by half.

项目成果

K.Hashimoto,T.Tsuchiya,T.Kikuno: "A multiprocessor scheduling algorithm for law overhead fault-tolerance" Proc.of 17th IEEE Symp.on Reliability Distributed Systems. 186-194 (1998)

K.Hashimoto、T.Tsuchiya、T.Kikuno：“用于法律开销容错的多处理器调度算法”Proc.of 17th IEEE Symp.on Reliability Distributed Systems。

T.Tsuchiya,T.Kikuno: "Maximizing availability of quorum-based exclusion mechanisms" Digest of Fast Abstracts:FTCS-28. 92-93 (1998)

T.Tsuchiya、T.Kikuno：“最大化基于群体的排除机制的可用性”快速摘要文摘：FTCS-28。

T.Tsuchiya,T.Kikuno: "Dependability evaluation of the weighted voting scheme in the presence of node and link failures"International Journal of Computer Systems: Science & Engineering. (掲載予定).

T.Tsuchiya，T.Kikuno：“存在节点和链路故障时加权投票方案的可靠性评估”国际计算机系统杂志：科学与工程（待出版）。

T.Tsuchiya,T.Kikuno: "Availability evaluation of quorum-based mutual exclusion schemes in general topology networks"The Computer Journal. 42・7. 613-622 (1999)

T.Tsuchiya，T.Kikuno：“一般拓扑网络中基于群体的互斥方案的可用性评估”计算机杂志 42・7（1999）。

T.Tsuchiya,N.Ido,T.Kikuno: "Constructing Byzantine quorum systems from combinatorial designs"The Information Processing Letters. 71・1. 35-42 (1999)

T.Tsuchiya、N.Ido、T.Kikuno：“从组合设计构建拜占庭仲裁系统”信息处理快报 71・1 (1999)。