Synthesizing distributed finite-state systems from MSCs

Mukund, Madhavan ; Narayan Kumar, K. ; Sohoni, Milind (2000) Synthesizing distributed finite-state systems from MSCs In: 11th International Conference on Concurrency Theory (CONCUR - 2000), 22 25 Aug 2000, University Park, PA.

Full text not available from this repository.

Official URL:

Related URL:


Message sequence charts (MSCs) are an appealing visual formalism often used to capture system requirements in the early stages of design. An important question concerning MSCs is the following: how does one convert requirements represented by MSCs into state-based specifications? A first step in this direction was the definition in [9] of regular collections of MSCs, together with a characterization of this class in terms of finite-state distributed devices called message-passing automata. These automata are, in general, nondeterministic. In this paper, we strengthen this connection and describe how to directly associate a deterministic message-passing automaton with each regular collection of MSCs. Since real life distributed protocols are deterministic, our result is a more comprehensive solution to the synthesis problem for MSCs. Our result can be viewed as an extension of Zielonka’s theorem for Mazurkiewicz trace languages [6,19] to the setting of finite-state message-passing systems.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Synthesis Problem; Primary Information; Secondary Information; Process Residue; Communication Sequence
ID Code:114218
Deposited On:25 May 2018 04:53
Last Modified:25 May 2018 04:53

Repository Staff Only: item control page