1. Causal Message Sequence Charts
- Author
-
Loïc Hélouët, Thomas Gazagnaire, Shaofa Yang, Blaise Genest, P. S. Thiagarajan, Citrix Systems R&D Ltd, UK, Citrix, Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), School of computing [Singapore] (NUS), National University of Singapore (NUS), EA DST, ANR-06-SETI-0003,DOTS,Systèmes distribués, ouverts et temporisés(2006), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique
- Subjects
partial orders ,General Computer Science ,Computer science ,Programming language ,Modeling ,0102 computer and information sciences ,02 engineering and technology ,Distributed systems ,computer.software_genre ,01 natural sciences ,Theoretical Computer Science ,Undecidable problem ,Decidability ,Formalism (philosophy of mathematics) ,Scenarios ,[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] ,010201 computation theory & mathematics ,Sliding window protocol ,Bounded function ,Scenario languages ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,computer ,Computer Science(all) - Abstract
International audience; 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.
- Published
- 2009
- Full Text
- View/download PDF