The research described here bears on stochastic discrete event systems and more precisely on stochastic networks (see the more general web page on queueing theory) and Petri nets (see the following Petri net bibliography).
We concentrated on the development of an algebraic framework allowing for a mathematical represention of networks regardless of their dimension and the underlying stochastic assumptions. This formalism also allows one to define classes of networks (e.g. event graphs, free choice nets etc.) for which similar methods of analysis work. Based on this mathematical representation, one can then design controls or evaluate analytically performaces in new ways, quite different from the more classical Markovian approach. For more on this approach, see the Wiley book entitled Synchronization and Linearity, which we coauthored with G. Cohen, G. J. Olsder and J. P. Quadrat in 1992.
Concerning my own research, here are the main domains of current interest, which are also summarized in the slides of a lecture that I gave at the 10-th Applied Probability Conference in Ulm (Germany) in July 1999:
- STOCHASTIC ANALYSIS: an important issue in this setting is that of the computation and analytical characterization of the stationary distributions in networks. Here are the main directions:
- ANALYTIC EXPANSIONS for (max,plus) Lyapunov exponents with D. Hong: see the reports RR-3427. RR-3558. The aim here is to work out expansions for the throughput of closed networks with random services.
- COMPUTATION OF DISTRIBUTIONS in (max,plus) linear systems: mean values in RR-2494, with V. Schmidt , Laplace transforms and transient behavior in RR-2785 and RR-3022, with V. Schmidt and S. Hasenfuss from Ulm University. This concerns open networks with Poisson input point processes, for which we wish to derive expressions for the law of stationary or transient waiting times.
- HEAVY TAIL ASYMPTOTICS for the stationary distributions in various classes of networks:
- for irreducible (max,plus) networks, see the Questa 99 paper in collaboration with V. Schmidt and S. Schlegel;
- for monotone separable networks, see RR-4197 in collaboration with S. Foss; in this paper (now published in the Annals of Applied Probability), we started developing the theory of rare events for networks and we worked out some examples, in particular we derived the exact asymptotics for tandem queues with subexponential service times.
- The tail asymptotics of subexponential (max,plus) networks was then derived in RR-4952 and that of generalized Jackson networks in RR-5081, jointly with S. Foss and M. Lelarge.
- There are several quite interesting developments which lead to a more and more complete theory of rare events for networks. A comprehensive exposition of the advances on the matter can be found in the thesis (defended in 2005) and the web page of Marc Lelarge.
- ALGEBRA: we worked on the algebraic framework for non homogenous linear systems in RR-3435 jointly with R. Agrawal of University of Wisconsin and R. Rajan of AT&T labs. One of the motivations for this is to model integrated service networks.
- NON-LINEAR NETWORKS: beyong the linear classes, there are several other classes of networks which can be analyzed via certain extensions of this algebraic framework. The main results bear on
- The MONOTONE-SEPARABLE framework that we introduced in the 95 JAP paper jointly with S. Foss; this class contains as special cases generalized Jackson networks, (max,plus) linear networks, multiserver queues and many classes of Free Choice stochasttic Petri Nets.
- (MAX,PLUS) LINEAR SYSTEMS WITH FIFO PERTURBATIONS. The report RR-3434 with T. Bonald . bears on the analysis of the stability region for the TCP protocol.
- GENERALIZED JACKSON NETWORKS, a topic that we started investigating jointly with S. Foss (when he was still at Novosibirsk University) using ergodic theory RR 2015 ; see in particular the following paper which was published in the proceedings of the Edinburgh Stochastic Network conference.
- FREE CHOICE NETS, see RR-2411 with S. Foss and B. Gaujal;
- NON EXPANSIVE OPERATORS, see RR-2641, with J. Mairesse from Liafa.
- INFINITE DIMENSIONAL SYSTEMS: The Probability Theory and Related Fields (PTRF) paper, with J. Mairesse of Liafa and A.A. Borovkov of the Sobolev Mathematical Institute, studies the links between infinite tandems of single server queues with general statistics, products of infinite-dimensional random (max,plus) matrices and first passage percolation. This line of thoughts is continued in several directions:
- J. Martin of the university of Oxford studied various cases of queues with blocking (see in the following list of papers).
- Jointly with Augustin Chaintreau of ENS and Zhen Liu of IBM Research, we extended this approach to study the rate of infinite tandems and infinite trees of stochastic dynamical systems found in Internet multicasting. See RR-4895 (Infocom 2004) and RR-5241 (Infocom 2005).
- Jointly with Serguei Foss we studied infinite dimensional max plus systems based on random closed sets of the Euclidean plane in the paper Poisson Hail on a Hot Ground, to appear in Advances in Applied Probability in 2011.
- SIMULATION: our main contribution bears on the parallel simulation of event-graphs (see RR-1520 with M. Canales). For the extension to free-choice nets and other more general classes, see the web pages of N. Furmento, B. Gaujal and A. Jean-Marie.
Our research group was partner of the European project Alapedes which was part of the TMR program; there was also a Spring school on this topic in Noirmoutier: Algèbres Max-Plus et applications en informatique et automatique which stressed the recent developments of the theory and several domains of application in manufacturing, in transportation systems, and in computer science.
Several types of appications have been and are being investigated:
- Flow control and regulators in communication networks.
- Synchronization mechanisms in parallel processing (see the Qmips book, which we co-edited with A. Jean-Marie and I. Mitrani, which summarizes the results that we obtained in a BRA European project on the matter).
- Kanban or assembly lines in manufacturing (see for instance RR-2494).
- Real time systems (see RR-3778 with B. Gaujal and D. Simon).
A. Jean-Marie has a software prototype called ERS which allows one to manipulated some of these objects and many more.Last revised: July, 2011.