Paper Info
Title
Causal Message Sequence Charts
Abstract
Scenario languages based on Message Sequence Charts (MSCs) have been widely studied in the last decade. The high expressive power of MSCs renders many basic problems concerning these languages undecidable. However, several of these problems are decidable for languages that possess a behavioral property called ''existentially bounded''. Unfortunately, collections of scenarios outside this class are frequently exhibited by systems such as sliding window protocols. We propose here an extension of MSCs called causal Message Sequence Charts and a natural mechanism for defining languages of causal MSCs called causal HMSCs (CaHMSCs). These languages preserve decidable properties without requiring existential bounds. Further, they can model collections of scenarios generated by sliding window protocols. We establish here the basic theory of CaHMSCs as well as the expressive power and complexity of decision procedures for various subclasses of CaHMSCs. We also illustrate the modeling power of our formalism with the help of a realistic example based on the TCP sliding window feature.
Year
DOI
Venue
2009
10.1016/j.tcs.2009.06.013
International Conference on Concurrency Theory
Keywords
Field
DocType
modeling power,languages undecidable,window feature,causal message sequence charts,causal mscs,partial orders,window protocol,expressive power,high expressive power,distributed systems,mscs render,scenario languages,causal hmscs,modeling,message sequence chart,sliding window,col
Notation,Sliding window protocol,Programming language,Computer science,Asynchronous distributed systems,Theoretical computer science,Decidability,Expressive power,Bounded function,Undecidable problem
Journal
Volume
Issue
ISSN
410
41
Theoretical Computer Science
ISBN
Citations 
PageRank 
3-540-74406-1
8
0.53
References 
Authors
21
5
Name
Order
Citations
PageRank
Thomas Gazagnaire121513.32
Blaise Genest230425.09
Loïc Hélouët328125.37
P. S. Thiagarajan41497193.71
Shaofa Yang5464.76