Bounded MSC Communication

Markus Lohrey and Anca Muscholl

To appear at Foundations of Software Science and Computation Structures (FOSSACS02), Grenoble, France, 6-14 April, 2002


Message sequence charts (MSCs) and different kinds of extensions like high-level message sequence charts (HMSCs) and nested message sequence charts (nMSCs) are popular formalisms for the specification of asynchronously communicating processes. An important concept in this context are the channel-buffers between communicating processes. Since real systems impose limitations on the capacity (or speed) of communication links, we consider the size of these buffers as a computational resource, similar to memory in classical computing devices. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (HMSC, nMSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP.

Server START Conference Manager
Update Time 14 Dec 2001 at 14:02:38
Start Conference Manager
Conference Systems