Synchronization and Linearity An Algebra for Discrete Event Systems

Synchronization and Linearity An Algebra for Discrete Event Systems Franc¸ois Baccelli INRIA and Ecole Normale Supe´rieure, De´partement d’Informatique Paris, France Guy Cohen Ecole Nationale des Ponts et Chausse´es-CERMICS Marne la Valle´e, France and INRIA Geert Jan Olsder Delft University of Technology Faculty of Technical Mathematics Delft, the Netherlands Jean-Pierre Quadrat Institut National de la Recherche en Informatiqueet en Automatique INRIA-Rocquencourt Le Chesnay, France Preface to the Web Edition The first edition of this book was published in 1992 by Wiley (ISBN 0 471 93609 X). Since this book is now out of print, and to answer the request of several colleagues, the authors have decided to make it available freely on the Web, while retaining the copyright, for the benefit of the scientific community. Copyright Statement This electronic document is in PDF format. One needs Acrobat Reader (available freely for most platforms from the Adobe web site) to benefit from the full interactive machinery: using the package hyperrefby Sebastian Rahtz, the table of contents and all LT X cross-references are automatically converted into clickable hyperlinks, bookmarks are generated automatically, etc.. So, do not hesitate to click on references to equation or section numbers, on items of the table of contents and of the index, etc.. One may freely use and print this document for one’s own purpose or even dis-tribute it freely, but not commercially, provided it is distributed in its entirety and without modifications, including this preface and copyright statement. Any use of the contents should be acknowledged according to the standard scientific practice. The authorswill appreciate receivingany comments bye-mail orothermeans; all modifica-tionsresultingfromthese comments infuturereleases willbeadequately andgratefully acknowledged. About This and Future Releases We have taken the opportunity of this electronic edition to make corrections of mis-prints and slight mistakes we have become aware of since the book was published for the first time. Inthe present release, alterationsof the originaltext are mildand need no special mention: they concern typographic style (which may result in a different pagi-nation with respect to the original paper version of the book), the way some equations are displayed, and obvious mistakes. Some sentences may even have been rephrased for better claritywithoutalteringthe originalmeaning. There are, however, no changes in the numbering of equations, theorems, remarks, etc.. From time to time in the near future, we plan to offer new releases in which more substantial alterations of the original text will be provided. Indeed, we consider some material as somewhat outdated (and sometimes even wrong). These more important modificationswillinitiallybelistedexplicitlyandprovidedseparatelyfromtheoriginal i ii Synchronization and Linearity text. In a more remote future, we may consider providing a true “second edition” in which these changes will be incorporated in the main text itself, sometimes removing the obsolete or wrong corresponding portions. Franc¸ois Baccelli Guy Cohen Geert Jan Olsder Jean-Pierre Quadrat francois.baccelli@ens.fr guy.cohen@mail.enpc.fr g.j.olsder@math.tudelft.nl jean-pierre.quadrat@inria.fr October 2001 Contents Preface ix I Discrete Event Systems and Petri Nets 1 1 Introduction and Motivation 3 1.1 Preliminary Remarks and Some Notation . . . . . . . . . . . . . . . 3 1.2 Miscellaneous Examples . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Communication . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.3 Production . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.4 Queuing System with Finite Capacity . . . . . . . . . . . . . 18 1.2.5 Parallel Computation . . . . . . . . . . . . . . . . . . . . . . 20 1.2.6 Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.7 ContinuousSystem Subject to Flow Bounds and Mixing . . . 25 1.3 Issues and Problems in Performance Evaluation . . . . . . . . . . . . 28 1.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2 Graph Theory and Petri Nets 35 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Graphs and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.1 Compositionof Matrices and Graphs . . . . . . . . . . . . . 41 2.3.2 Maximum Cycle Mean . . . . . . . . . . . . . . . . . . . . . 46 2.3.3 The Cayley-Hamilton Theorem . . . . . . . . . . . . . . . . 48 2.4 Petri Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4.2 Subclasses and Properties of Petri Nets . . . . . . . . . . . . 59 2.5 Timed Event Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.5.1 Simple Examples . . . . . . . . . . . . . . . . . . . . . . . . 63 2.5.2 The Basic Autonomous Equation . . . . . . . . . . . . . . . 68 2.5.3 Constructiveness of the Evolution Equations . . . . . . . . . 77 2.5.4 Standard Autonomous Equations . . . . . . . . . . . . . . . . 81 2.5.5 The Nonautonomous Case . . . . . . . . . . . . . . . . . . . 83 2.5.6 Constructionof the Marking . . . . . . . . . . . . . . . . . . 87 2.5.7 Stochastic Event Graphs . . . . . . . . . . . . . . . . . . . . 87 2.6 Modeling Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 iii ... - tailieumienphi.vn