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: https://link.springer.com/chapter/10.1007%2F3-540-...

Related URL: http://dx.doi.org/10.1007/3-540-44618-4_37

Abstract

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