# Causal Message Sequence Charts

2 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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.
keyword :
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2009, 38 p

Littérature citée [24 références]

https://hal.inria.fr/inria-00429538
Contributeur : Loic Helouet <>
Soumis le : mardi 3 novembre 2009 - 12:29:18
Dernière modification le : vendredi 16 novembre 2018 - 01:24:59
Document(s) archivé(s) le : jeudi 17 juin 2010 - 17:41:33

### Fichier

GGHTY-CMSC-Long.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00429538, version 1

### Citation

Thomas Gazagnaire, Blaise Genest, Loïc Hélouët, P.S. Thiagarajan, Shaofa Yang. Causal Message Sequence Charts. Theoretical Computer Science, Elsevier, 2009, 38 p. 〈inria-00429538〉

### Métriques

Consultations de la notice

## 567

Téléchargements de fichiers