Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2009.06.013
Title: Causal Message Sequence Charts
Authors: Gazagnaire, T.
Genest, B.
Hélouët, L.
Thiagarajan, P.S. 
Yang, S.
Keywords: Distributed systems
Modeling
Partial orders
Scenario languages
Issue Date: 2009
Source: Gazagnaire, T.,Genest, B.,Hélouët, L.,Thiagarajan, P.S.,Yang, S. (2009). Causal Message Sequence Charts. Theoretical Computer Science 410 (41) : 4094-4110. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2009.06.013
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. © 2009 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39777
ISSN: 03043975
DOI: 10.1016/j.tcs.2009.06.013
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

5
checked on Nov 2, 2017

Page view(s)

60
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.