Process specification generation from communications service specifications

摘要

This paper proposes an algorithm for generating process specifications from communications service specifications described by a graph grammar. In this work, it is assumed that a communications system consists of homogeneous processes and that there is no global database. Processes that share a relationship form a global state, and a communications service defines global state transitions caused by inputs to the processes. A global state is represented by a labeled directed graph and a global state transition is described by a graph replacement rule. A process specification is regarded as a distributed algorithm whose purpose is to achieve the global state transitions described by the graph replacement rules. The communication time complexity of the generated distributed algorithm does not depend on the number of graph replacement rules.