A hierarchy of communication models for Message Sequence Charts

In a Message Sequence Chart (MSC) the dynamical behaviour of a number of cooperating entities is depicted. An MSC defines a partial order on the communication events between these entities. This order determines the physical architecture needed for implementing the specified behaviour, such as a FIFO buffer between each of the entities. In a systematic way, we define 50 communication models for MSC and we define what it means for an MSC to be implementable by such a model. Some of these models turn out to be equivalent, in the sense that they implement the same class of MSCs. After analysing the notion of implementability, only ten classes remain, for which we develop a hierarchy. We also develop algorithms to check whether a given MSC belongs to such a class. (C) 2002 Elsevier Science B.V. All rights reserved.