Les séminaires du projet MISTRAL

Seminars of Project MISTRAL

Vivacité des réseaux de Petri
Bruno GAUJAL (INRIA Sophia Antipolis)

Dans de grands réseaux qui contiennent des synchronisations, il peut arriver que l'évolution temporelle du réseau mène à des interblocages. Un réseau sans interblocage dans lequel tous les noeuds sont actifs est dit vivant.
La modélisation de tels réseaux par des réseaux de Petri et l'utilisation des équations d'évolution permet la mise au point de tests de vivacité essentiellement algébriques (triangularisation, rang et rayon de matrices). Plusieurs autres propriétés logiques similaires sont aussi vérifiables par l'intermédiaire de ces équations. Ces tests ont été implémentés dans ers+.

Modelisation et ordonnancement de reseaux de Petri temporises a l'aide d'automates (max,+)
Jean MAIRESSE (Universite de Cambridge, GB)

On definit le modele tache ressource contraint. Celui ci peut etre decrit de facon equivalente comme: -- un systeme (max,+) lineaire dont la dynamique est contrainte par un langage. -- le produit tensoriel d'un automate booleen et d'un automate (max,+). La modelisation en terme d'automates permet une analyse exacte pour le fonctionnement dans le pire des cas (pour les systemes deterministes).
On montre que ce modele permet de representer la classe des `safe free choice nets' ainsi que de nombreux autres exemples de `safe Petri nets'.
Ce modele fournit un bon cadre pour aborder le probleme de l'ordonnancement dans les ateliers flexibles cycliques (l'ordonnancement des taches sur les machines est fixe mais pas celui des taches sur les machines). En particulier, on ameliore la complexite des algorithmes permettant de calculer temps de cycle et circuits critiques a ordonnancement fixe.

Multi-class production systems with setup times
Rhonda Righter (Santa Clara University, USA)

We consider polling systems with random setup times, and show that if setup times or service times are reduced in the convex ordering sense, then work loads and queue sizes will be reduced in the usual stochastic sense. We also show that the joint distributions of various performance measures across time are invariant under shifts in setup times as long as the net shift is zero.

A preliminary version of a denotational framework for comparing models of computation
Edward A. Lee (UC Berkeley, USA)

We give the beginnings of a denotational framework that describes concurrent processes in general terms as sets of possible behaviors. The major objective is to provide a framework within which certain key properties of concurrent models of computation can be compared and contrasted. Compositions of processes are given as intersections of their behaviors. The interaction between processes is through signals, which are collections of events. A system is determinate if given the constraints imposed by the inputs there are exactly one or exactly zero behaviors. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. Synchronous systems contain synchronous signals. Strict causality (in timed systems) and continuity (in untimed systems) ensure determinacy under certain technical conditions. The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, and discrete-event systems.

Etude d'un modèle de contrôle de flux: Stabilité et Performances.
Thomas BONALD (INRIA, Sophia Antipolis)

Le but de ce travail est l'étude d'un mécanisme de contrôle de flux à fenêtre (type TCP/IP par exemple). La première partie décrit le modèle, constitué d'une file d'attente, qui reçoit le flux d'une source contrôlée par une fenêtre de taille fixe, et un flux exogène. Dans une deuxième partie, on étudie la stabilité du modèle. En particulier, si la charge du trafic exogène est inférieure à 1, on montre que le modèle est stable en utilisant trois techniques : l'analyse d'une chaîne de Markov quand le processus d'arrivée du flux exogène est Poisson, les modèles fluides quand ce processus est de renouvellement, et la règle de saturation quand ce processus est stationnaire ergodique. Enfin, dans le cas poissonnien, on donne une méthode pour calculer les moments des temps de séjour des clients des deux flux, ainsi que les moments du nombre de clients dans la file. L'optimisation de la taille de fenêtre ainsi que quelques extensions du modèle sont présentées.

Greedy algorithm: Z1 case.
Irina KOURKOVA (Universite de Moscou)

A polling network with a collection of stations Z is considered. Customers appear at each point in Z according to a Poisson process. The server goes at unit speed along the real line stopping to perform service of the accumulated customers. It stays at a station until the moment when this station becomes empty and then goes to the neighbour one with the maximum number of customers. The trajectories of the server are studied.

Séminaires récents

Dernière modification: 25 avril 1996

Contact: Zhen Liu