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.
