Modelling and simulation of dynamic-structure discrete-event systems

Discrete-event modelling and simulation has become an established approach to the description and study of complex dynamic systems. In recent years there has been an increased interest in modelling complex dynamic-structure systems, i.e., systems whose structure changes over time. Such systems are generally more difficult to understand and analyze than systems with a static structure. These challenges can be met by the development of appropriate modelling formalisms based on a solid foundation and with suitable supporting tools. In this thesis we explore an approach to modelling and simulation of dynamic-structure discrete-event systems based on process algebra. The thesis consists of two parts. We begin by exploring, in the first part, a formalism for static-structure discrete-event modelling and simulation called the Discrete-EVent System Specification formalism (DEVS [Zeigler 76, 2000].) We develop an alternative theoretical foundation for DEVS based on Structural Operational Semantics, focusing on determinism and compositionality properties. In the second part we develop a modelling language for dynamic-structure discrete-event systems named kiltera, based on process algebras and incorporating elements from discrete-event modelling. This language, based on the \pi-calculus [Milner 89], allows us to describe and reason about timed, mobile and distributed discrete-event systems in a single framework. We develop a theoretical foundation based on Structural Operational Semantics and establish fundamental properties concerning time-determinism, continuity, compositionality and legitimacy. We build a simulator for the language which supports both sequential and distributed execution of models, based on a variant of the Time Warp algorithm [Jefferson 85]. Finally we apply this language to the modelling and simulation of traffic.La modélisation et la simulation à événements discrets constituent une approche bien établie pour la description et l'étude des systèmes dynamiques complexes. Ces dernières années, il y a eu un regain d'intérêt pour la modélisation des systèmes complexes à structure dynamique. Ces systèmes sont généralement plus difficiles à comprendre et à analyser que les systèmes ayant une structure statique. Cette analyse et cette compréhension peuvent être développées à l'aide de formalismes de modélisation fondés sur une base solide et des outils appropriés. Dans cette thèse, nous explorons une approche de modélisation et de simulation des systèmes à événements discrets fondée sur l'algèbre de processus. Ce document se compose de deux parties. Dans la première partie, nous étudions ce que l'on appelle le formalisme Discrete-EVent System Specifications (DEVS.) Nous développons un autre fondement théorique pour DEVS fondée sur la sémantique opérationnelle structurelle, en mettant l'accent sur les propriétés de déterminisme et de compositionalité. Dans la deuxième partie, nous développons un langage de modélisation pour systèmes à structure dynamique nommé kiltera, en nous fondant sur les algèbres de processus et en incorporant des éléments de modélisation à événements discrets. Ce langage, en se fondant sur le \pi-calcul, nous permet de décrire et de raisonner sur les systèmes mobiles, distribués et au temps-réel, à événements discrets, dans un cadre conceptuel unique. Nous développons une base théorique fondée sur la sémantique opérationnelle structurelle et nous établissons des propriétés fondamentales concernant le déterminisme-temps, la continuité, la compositionalité et la légitimité. Nous construisons un simulateur pour le langage qui supporte à la fois l'exécution séquentielle et distribuée de modèles, en utilisant une variante de l'algorithme Time Warp. Enfin, nous appliquons ce l