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

岡野, 浩三; オカノ, コウゾウ; Okano, Kozo; 今城, 広志; イマジョウ, ヒロシ; Imajo, Hiroshi; 東野, 輝夫; ヒガシノ, テルオ; Higashino, Teruo; 谷口, 健一; タニグチ, ケンイチ; Taniguchi, Kenichi

アクセス数:202件（2024-04-18 15:58 集計）

固定URL: https://hdl.handle.net/11094/50245

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
ipij-jnl_36_1_70	pdf	なし	1.41 MB	28	2014.10.01	出版社版/publisher

論文情報

ファイル出力

タイトル	リンクの故障を考慮に入れた分散システムの動作仕様の自動導出
	Synthesis of Protocol Specifications from Service Specifications in Distributed Systems with Communication Link Errors
	リンク　ノ　コショウ　ヲ　コウリョ　二　イレタ　ブンサン　システム　ノ　ドウサ　シヨウ　ノ　ジドウ　ドウシュツ
著者	NRID 1000070252632 1000070252632 著者名岡野, 浩三 ; オカノ, コウゾウ ; Okano, Kozo
	著者名今城, 広志 ; イマジョウ, ヒロシ ; Imajo, Hiroshi
	NRID 1000080173144 1000080173144 researchmap permalink teruo.higashino teruo.higashino Scopus Author ID 7005648670 7005648670 著者名東野, 輝夫 ; ヒガシノ, テルオ ; Higashino, Teruo
	NRID 1000000029513 1000000029513 著者名谷口, 健一 ; タニグチ, ケンイチ ; Taniguchi, Kenichi
抄録	分散システム全体の外部から観測できる動作の内容や実行順を記述した要求仕様から要求仕様どおりに動作する各ノードの動作仕様(どのようなタイミングでどのノードとどのような同期用メッセージやレジスタ値を交換しながら自ノードの動作を実行したり,自ノードのレジスタ値を更新していくべきかを記述したもの)を自動生成できることが望ましい.一方,分散システムでは,ノードやリンク故障を考慮して,これらの故障が生じても,システム全体として要求仕様どおり動くシステムの設計が望まれる.本論文では,レジスタを持つ拡張有限状態機械(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.
出版者	情報処理学会
出版者	ジョウホウ　ショリ　ガッカイ
収録物名	情報処理学会論文誌
収録物名	Transactions of Information Processing Society of Japan
巻(号)	36(1)
ページ	70-83
刊行年月	1995-01-15
言語	日本語
ハンドルURL	https://hdl.handle.net/11094/50245
PISSN	03875806
NCID	AN00116647
アクセス権	open access
権利情報	ここに掲載した著作物の利用に関する注意本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
権利情報	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.
出版タイプ	Version of Record
カテゴリ	学術雑誌論文 Journal Article

資源タイプ	学術雑誌論文
ローカル資源タイプ	学術雑誌論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	情報処理学会論文誌. 1995, 36(1), p. 70-83
DC.title	リンクの故障を考慮に入れた分散システムの動作仕様の自動導出
	Synthesis of Protocol Specifications from Service Specifications in Distributed Systems with Communication Link Errors
	リンク　ノ　コショウ　ヲ　コウリョ　二　イレタ　ブンサン　システム　ノ　ドウサ　シヨウ　ノ　ジドウ　ドウシュツ
DC.creator	岡野, 浩三
	オカノ, コウゾウ
	Okano, Kozo
	今城, 広志
	イマジョウ, ヒロシ
	Imajo, Hiroshi
	東野, 輝夫
	ヒガシノ, テルオ
	Higashino, Teruo
	谷口, 健一
	タニグチ, ケンイチ
	Taniguchi, Kenichi
DC.publisher	情報処理学会
DC.publisher	ジョウホウ　ショリ　ガッカイ
DC.language' scheme='DCTERMS.RFC1766	日本語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	1995-01-15
DCTERMS.abstract	分散システム全体の外部から観測できる動作の内容や実行順を記述した要求仕様から要求仕様どおりに動作する各ノードの動作仕様(どのようなタイミングでどのノードとどのような同期用メッセージやレジスタ値を交換しながら自ノードの動作を実行したり,自ノードのレジスタ値を更新していくべきかを記述したもの)を自動生成できることが望ましい.一方,分散システムでは,ノードやリンク故障を考慮して,これらの故障が生じても,システム全体として要求仕様どおり動くシステムの設計が望まれる.本論文では,レジスタを持つ拡張有限状態機械(EFSM)としてモデル化された分散システム全体の要求仕様から,要求仕様どおりに動作する各ノードの動作仕様(EFSM)を自動生成するための一つのアルゴリズムを提案する.この動作仕様では,高々一つのリンク故障に対して,同一メッセージを異なる2経路で送受信することにより,エラー回避が行われる.その際,単純に二重化せず同一リンクで送信される複数のメッセージを単一のメッセージに統合して,その際のノード間のメッセージ交換の総数をできるだけ少なくしている.メッセージ総数の最小化のために0-1整数線形計画問題の解法を用いている.
DCTERMS.abstract	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.
DC.rights	ここに掲載した著作物の利用に関する注意本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
DC.rights	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.
DC.format	application/pdf
citation_title	リンクの故障を考慮に入れた分散システムの動作仕様の自動導出
	Synthesis of Protocol Specifications from Service Specifications in Distributed Systems with Communication Link Errors
	リンク　ノ　コショウ　ヲ　コウリョ　二　イレタ　ブンサン　システム　ノ　ドウサ　シヨウ　ノ　ジドウ　ドウシュツ
citation_author	岡野, 浩三
	オカノ, コウゾウ
	Okano, Kozo
	今城, 広志
	イマジョウ, ヒロシ
	Imajo, Hiroshi
	東野, 輝夫
	ヒガシノ, テルオ
	Higashino, Teruo
	谷口, 健一
	タニグチ, ケンイチ
	Taniguchi, Kenichi
citation_publisher	情報処理学会
citation_publisher	ジョウホウ　ショリ　ガッカイ
citation_language	日本語
citation_date	1995-01-15
citation_journal_title	情報処理学会論文誌
citation_journal_title	Transactions of Information Processing Society of Japan
citation_volume	36
citation_issue	1
citation_firstpage	70
citation_lastpage	83
citation_public_url	https://hdl.handle.net/11094/50245

閲覧可能ファイル

論文情報

論文詳細を表示