Implied message sequence charts

Details Implied message sequence charts Implied message sequence charts

2000-05-26

2004-01-20

Courtenay, III, St. John (Department: 2126)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C703S017000, C706S010000, C345S440000

Reexamination Certificate

active

06681264

ABSTRACT:

FIELD OF THE INVENTION
The invention relates generally to systems analysis and design, and more particularly to modeling using message sequence charts.
BACKGROUND
Message Sequence Charts (MSCs) are commonly used to describe design requirements for concurrent systems, such as telecommunications software. An MSC typically describes messages passed between participating concurrent processes in the system, abstracting away details like program variables and their values. An individual MSC corresponds to a single (partial-order) execution of the described system, and requirements specifications are often given as a set of MSCs depicting different possible executions. Requirements expressed with MSCs have formal semantics, and can be analyzed for, among other things, race conditions, timing conflicts, pattern matching and non-local choice. Since MSCs are typically used early in a design, any errors revealed during analysis of an MSC yields a high pay-off in the design effort.
Each process in a concurrent system has only a local view of the possible scenarios described by the different MSCs. (A local view means the process is only aware of events occurring on its process line.) Consequently, the intended behaviors in the different MSCs that describe a system can combine in unexpected ways to form unspecified but implied MSCs. These unspecified MSCs will exist as execution scenarios in a distributed implementation of the system, and such unspecified MSCs could represent unsafe or undesirable executions. No method exists, however, to detect whether such unspecified behaviors exist.
SUMMARY
The method according to the principles of the invention checks whether the behavior described in a set of message sequence charts (MSCs) is realizable as a set of possible executions of concurrent state machines. The set of MSCs is realizable when it represents all the executions of some system; that is, if the set does not imply any unspecified MSCs. If it is realizable, the MSCs are used to synthesize automata (state machines) that exhibit the desired behaviors. If the behavior is unrealizable, the method provides the implied MSCs.
The method according to the principles of the invention also determines whether the set of MSCs is realizable by a set of dead-lock free automata (safely realizable). If the behaviors are not safely realizable, the method provides implied, partial MSCs. These partial MSCs represent incomplete but implied executions, which can then be extended and completed by system designers. The designer can complete these partial MSCs and add them to the set of MSCs. The new set can then be checked for realizability and implied, partial MSCs. The process can be iterated until no implied MSCs exist or until the designer is satisfied. If the MSCs are safely realizable, they can be used to synthesize deadlock-free automata exhibiting the desired behaviors.
To efficiently determine whether a set of MSCs is safely realizable, the MSCs in the set are analyzed to identify events that are eligible to replace other identified events in the MSC set. For example, for an identified event on a given MSC in the set, it is determined whether some other event on some other MSC in the set can substitute for the identified event. If so, there must be an MSC that realizes the substitution. If that MSC does not exist in the set of MSCs, it is an implied but unspecified MSC. In that case, the set of MSCs is not safely realizable and the implied MSC is reported.
It may also be desirable to determine whether some unspecified MSC is implied by a set of MSCs. For example, when a scenario is known to be dangerous, the scenario can be checked directly to determine if the set of MSCs implies the scenario. To determine whether a given unspecified MSC is implied by a set of MSCs, the projection onto each process in the unspecified MSC is checked for existence in the set. The projection onto each process is the sequence of events for the process. If all the projections for each process in the unspecified MSC exist somewhere in the set of MSCs, the set of MSCs implies the unspecified MSC.


REFERENCES:
patent: 5812145 (1998-09-01), Holzmann et al.
patent: 6052455 (2000-04-01), James
patent: 6122356 (2000-09-01), James
patent: 6147994 (2000-11-01), Duree et al.
patent: 6260186 (2001-07-01), James
patent: 6405361 (2002-06-01), Broy et al.
patent: 6415396 (2002-07-01), Singh et al.
patent: 6516306 (2003-02-01), Alur et al.
Bordeleau et al., “UCM-ROOM Modelling: from Use Case Maps to Communicating State Machines,” IEEE paper #0-8186-7889-5/97, pp. 169-178, May 1997.*
Grabowski, Jens, “The Standardization of Message Sequence Charts,” IEEE paper #0-8186-4240-8/93, pp. 48-63, Aug. 1993.

Affiliated with

Also associated with

Rating

Implied message sequence charts does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implied message sequence charts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implied message sequence charts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3259829