プロセス代数によるプロセス生成機能をもつ並行システムの解析

本稿では,(1)子プロセスを生成して,(2)プロセス木を構築し,(3)親プロセスと子プロセス間でマルチウェイ局所通信ができる並行システムを解析する.我々はこのようなシステムをGP-システムと呼ぶ.例えば,アクティブデータベースシステムはこのGP-システム上に実現できる.アクティブデータベースでは,利用者が自由にデータの更新時期,更新条件,更新方法を記述することができるが,並行動作するプロセス間の通信や,子プロセスの反復的生成により,その設計は困難である.並行システムを記述し解析するために,CCSやCSPのようなプロセス代数が知られている.プロセス代数は,(1)並行システムの動作がその仕様に等価であるかどうかをチェックできる,または(2)2つの等価な小さいサブシステムを用いて,2つの等価な大きいシステムを設計できるなどの利点をもつ.しかし,従来のプロセス代数を直接GP-システムに適用することは困難であると思われる.我々は,CCSを拡張したCCSGPを提案する.CCSGPはGP-システムの記述に適したプロセス代数である.本稿では,GP-システムがどのようにCCSGPによって記述されるかをアクティブデータベースの例をもとに説明した後,CCSGPの形式的な定義を与え,最後にGP-システムの設計に有効な定理を示す.
We analyze concurrent and communicating systems which (1) can generate child-processes, (2) construct process trees, and (3) have multi-way local communications between a parent-process and child-processes. In this paper, such systems with generating processes are called GP-systems. For example, active database systems are implemented in GP-systems. In active database systems, though users can freely design occasions, conditions, and actions for updating datas, it is difficult to design them because of the communication, the concurrency, the cascading generation, and so on. In order to describe and analyze concurrent and communicating systems, process algebras such as CCS, CSP, and ACP, are well known. Process algebras are useful for (1) checking whether behavior of a concurrent system is equal to its specification or not, (2) constructing equal large systems from equal small subsystems, and so on. But it seems hard to directly use these process algebras for GP-systems. In this paper, we propose a process algebra named CCSGP (Calculus of Communicating Systems with Generating Processes), which is an extension of CCS. GP-systems can be directly described in CCSGP. We explain how GP-systems are described in CCSGP by an example of an active database system, give a formal definition of CCSGP, and show one important proposition useful for design of GP-systems.