Safe Implementability of Regular Message Sequence Chart Specifications.
Nicolas Baudru, Rémi Morin · Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing · 2003
Message Sequence Charts (MSCs) are drawn by software designers in order to model the typical behaviors of some communication protocol at an early stage of its design. The important question of whether some given set of scenarios is realizable by some message passing system has already been investigated in different ways. We consider here deadlock-free implementations up to additional message contents. We present an algorithm to check safe implementability of MSC specifications in the framework of non-FIFO channels. Our criterion turns out to have the same complexity bounds as the restrictive approach of Alur et al. [1] where no additional message content is allowed.