リンクの故障を考慮に入れた分散システムの動作仕様の自動導出

岡野, 浩三; 今城, 広志; 東野, 輝夫 他

情報処理学会論文誌, 1995, 36(1), 70-83

Number of Access:909（2025-08-31 18:49 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/50245

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
ipij-jnl_36_1_70 pdf None 1.41 MB 54 2014.10.01 出版社版/publisher  

Item Information

Output File Export EndNote Basic Export Mendeley

Title
リンクの故障を考慮に入れた分散システムの動作仕様の自動導出
Synthesis of Protocol Specifications from Service Specifications in Distributed Systems with Communication Link Errors
リンク　ノ　コショウ　ヲ　コウリョ　二　イレタ　ブンサン　システム　ノ　ドウサ　シヨウ　ノ　ジドウ　ドウシュツ
Creator
NRID
1000070252632 1000070252632
CreatorName
岡野, 浩三 ; オカノ, コウゾウ ; Okano, Kozo
CreatorName
今城, 広志 ; イマジョウ, ヒロシ ; Imajo, Hiroshi
NRID
1000080173144 1000080173144
researchmap permalink
teruo.higashino teruo.higashino
Scopus Author ID
7005648670 7005648670
CreatorName
東野, 輝夫 ; ヒガシノ, テルオ ; Higashino, Teruo
NRID
1000000029513 1000000029513
CreatorName
谷口, 健一 ; タニグチ, ケンイチ ; Taniguchi, Kenichi
Abstract
分散システム全体の外部から観測できる動作の内容や実行順を記述した要求仕様から要求仕様どおりに動作する各ノードの動作仕様(どのようなタイミングでどのノードとどのような同期用メッセージやレジスタ値を交換しながら自ノードの動作を実行したり,自ノードのレジスタ値を更新していくべきかを記述したもの)を自動生成できることが望ましい.一方,分散システムでは,ノードやリンク故障を考慮して,これらの故障が生じても,システム全体として要求仕様どおり動くシステムの設計が望まれる.本論文では,レジスタを持つ拡張有限状態機械(EFSM)としてモデル化された分散システム全体の要求仕様から,要求仕様どおりに動作する各ノードの動作仕様(EFSM)を自動生成するための一つのアルゴリズムを提案する.この動作仕様では,高々一つのリンク故障に対して,同一メッセージを異なる2経路で送受信することにより,エラー回避が行われる.その際,単純に二重化せず同一リンクで送信される複数のメッセージを単一のメッセージに統合して,その際のノード間のメッセージ交換の総数をできるだけ少なくしている.メッセージ総数の最小化のために0-1整数線形計画問題の解法を用いている.
In a distributed system, the protocol entities must exchange some data values and synchronization messages in order to ensure the temporal ordering of the events described in a service specification for the distributed system. It is desirable that a correct protocol specification can be derived automatically from a given service specification. In this paper, we propose an algorithm which synthesizes automatically a correct protocol specification from a service specification described as an extended FSM(EFSM)model. In our model, message loss is considered as the communication link errors. We assume that at most one communication link may be down. Even if all the messages in the faulty link are lost, the derived protocol specification can simulate the service specification correctly. To avoid the influences of the communicatinon errors, we use duplicated messages with the same information. In our method, however, in order to reduce the number of exchanged messages at each transition, all the messages used in the same link at each phase are merged into one message. To minimize the number of the exchanged messages, we use a procedure to calculate an optimal solution for 0-1 integer linear programming problems.
Publisher
情報処理学会
ジョウホウ　ショリ　ガッカイ
Source Title
情報処理学会論文誌
Transactions of Information Processing Society of Japan
Volume (Issue)
36(1)
Page
70-83
Date of Issued
1995-01-15
Language
Japanese
Handle URL
https://hdl.handle.net/11094/50245
PISSN
03875806
NCID
AN00116647
Access Rights
open access
CopyRight
ここに掲載した著作物の利用に関する注意 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan. Comments are welcome. Mail to address editj＠ipsj.or.jp, please.
oaire:version
Version of Record
Category
学術雑誌論文 Journal Article