zbMATH — the first resource for mathematics

Bounded MSC communication. (English) Zbl 1077.68695
Nielsen, Mogens (ed.) et al., Foundations of software science and computation structures. 5th international conference, FOSSACS 2002, held as part of the joint European conferences on theory and practice of software, ETAPS 2002, Grenoble, France, April 8–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43366-X). Lect. Notes Comput. Sci. 2303, 295-309 (2002).
Summary: Message sequence charts (MSCs) and high-level message sequence charts (HMSCs) are popular formalisms for the specification of communication protocols between asynchronous processes. An important concept in this context is the size of the communication buffers used between processes. Since real systems impose limitations on the capacity (or speed) of communication links, we ask whether a given HMSC can be implemented with respect to a given buffer size imposed by the environment. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (or HMSC, or hierarchical MSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP.
For the entire collection see [Zbl 0989.00051].

68Q60 Specification and verification (program logics, model checking, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: Link