Synchronization and linearity. An algebra for discrete event systems.

*(English)*Zbl 0824.93003
Wiley Series on Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: Wiley. xx, 489 p. (1992).

A class of dynamic systems known as “discrete event dynamic systems” (DEDS) and its mathematical theory are discussed in this book. These systems can be described by the following two versions of linear equations: \(x(k + 1) = Ax(k)\) and \(x(k + 1) = A(k) x(k) \oplus B(k) u(k)\). In terms of applications three different interpretations of + and \(\oplus\) operations can be given: maximization and addition, minimization and addition, and lastly maximization and multiplication. From a technical point of view, DEDS are systems composed of a finite number of resources (processors, memories, communication channels, manufacturing machines) shared by several users (computing jobs, communication packets, manufactured objects) which all contribute to the achievement of some common goal (parallel computation in various architectures, transmission of a set of packets in a communication system, the assembly of a product in an automated manufacturing line). The dynamics of such systems can be described by two fundamental paradigms of “synchronization” and “concurrency” which are conceptually similar to such concepts in Petri net theory. The concept of synchronization and its mathematical theory is a main topic of this book. The fundamental thesis is that there exists an algebra in which DEDS that do not involve concurrency can naturally be modeled as linear systems. The idea is to treat the max operation as the “addition” of the algebra and the + operation as “multiplication”. The mathematical feature of “addition” is that it is an idempotent, and “multiplication” has the left and right distributive property with respect to “addition”. An algebraic structure consisting of a set of multisets (bags) called “dioids” is introduced (“dioid” stands for double monoid). The book is mathematically rigorous (all theorems are accompanied by proofs) in the presentation of dioid-based deterministic and stochastic systems. Some parts of the book have never been published previously. However, a substantial number of examples facilitate an understanding of the subject. The main purpose and achievement of the book is the development of a theory of linear systems on dioids. Deterministic and stochastic systems are separately analyzed. This is a research monograph, summarizing the authors’ contributions, which can be partially used as a graduate-level textbook for computer science, control engineering or operations research students. Each chapter ends with detailed reference notes.

In the first two chapters classical concepts of system theory such as state space recursive equations, input-output transfer functions, and feedback loops are introduced. In addition, fundamental concepts from graph theory, matrix theory, Petri nets and their subclasses, and timed event graphs are formulated together with the most important theorems and several practical examples (from the areas of planning, communication, production, queuing systems, parallel computation and traffic control). In particular, Viterbi’s maximization algorithm for communication, shortest path dynamic programming algorithm for networks, critical path dynamic programming algorithm for task scheduling, and Karp’s cycle computation algorithm for the evaluation of eigenvalues and eigenvectors are presented. Description of flexible manufacturing systems, railway traffic systems, and systolic and wavefront array processors by means of linear algebra are also discussed by suitable examples. Finally it is shown that a class of continuous systems with flow limitation and mixing phenomena can be described by the same linear equations as the above- mentioned discrete problems. The Cayley-Hamilton theorem, which for conventional algebra states that a square matrix satisfies its own characteristic equation, is reformulated for an algebraic structure defined on a set \(S\) of elements supplied with two operations denoted \(\oplus\) and \(\otimes\) which obey the axioms of associativity of addition, commutativity of addition, associativity of multiplication, both right and left distributivity of multiplication over addition, existence of an identity element, and commutativity of multiplication. Fundamental concepts for Petri nets such as reachability tree, reachability graph, event graph, state machine, bounded, safe, live, consistent, synchronous, conservative nets, timed event graphs (autonomous and nonautonomous), stochastic event graphs, and multigraphs are introduced formally and by examples. The synchronization concept is modeled by means of Petri nets.

Chapters Three and Four deal thoroughly with max-plus algebra and with an algebraic system of dioids. The max-plus algebra is a special case of a dioid structure. It is argued that the dioid algebra appears to be the right tool to handle synchronization in a linear manner, even when the synchronization phenomenon seems to be very nonlinear. The theory of dioids can also be a good starting point to encompass such basic features of DEDS as concurrency but at the price of considering systems which are nonlinear even in this new framework.

Chapters Five and Six deal with the deterministic system theory of DEDS as described by the class of Petri nets called event graphs which are exclusively driven, from the system dynamics point of view, by synchronization phenomena. Each event graph can be described by linear equations built on some descriptive variables and an associated dioid algebra. Two dioid algebras are applied: one, in the event domain, called “dater” description and another, in the time domain, called “counter” description. The first indicates the moments of time when an event of a certain type happened, the second counts the number of events which happened before a certain moment of time. In addition, a third description involving power series in a two-dimensional domain of the event and time domains is also studied. The problems of “inverting” the system, and equivalence of rationality, periodicity, and realizability are also discussed.

In Chapter Seven and Eight, the theory of stochastic DEDS systems is elaborated. First, an ergodic theory of event graphs is presented. A set of equations which describe the evolution of daters is a basis of such systems having stationary properties. First the existence problem is stated in terms of a “random eigenpair problem” which is a generalization of the deterministic case. The Petri net analogue of the \(G/G/1\) queue is carefully analyzed using probabilistic formalism. First- order theorems, which indicate how the daters grow in such a stochastic framework, are proven. It happens that the growth rates are analogues of Lyapunov exponents in conventional algebra, and generalizations of cycle times in the deterministic case. Second-order theorems are concerned with the construction of the eigenpairs. This construction is based on the analysis of ratios of daters. Both nonautonomous and autonomous cases are considered. Conditions on the uniqueness and reachability of the stationary state are formulated for both cases. Explanations are presented using both stochastic Petri nets and corresponding dioids, and stochastic linear algebra. The main results of this chapter state that the cycle time of a stochastic event graph is the maximal Lyapunov exponent associated with the matrices of its standard equation and that stationary states correspond to stochastic eigenpairs of these matrices. Several illustrative examples (including acyclic fork-join networks of queues and systems of machines with blocking after service) are used simultaneously with theoretical arguments.

Chapter Nine is a loosely connected and coherent set of different ideas which did not fit into the previous chapters. A realization theory with a version of the Cayley-Hamilton theorem in the max-plus algebra environment and a special class of nonlinear systems characterized by the equation \(x(k+1) = A(u(k), u(k -1))x(k)\) are studied. The analogy between probability calculus and dynamic programming is presented: iterated convolutions of probability laws play the same role as the inf- convolution of cost functions. The Fourier transform is used as an analysis tool for probability laws and the Fenchel transform in the dynamic programming case. Asymptotic theorems for the value function of dynamic programming correspond to the law of large numbers and the central limit theorem, and quadratic forms, being a stable set of inf- convolution, correspond to Gaussian laws which are stable by convolution. Also basic equations that govern the evolution of general Petri nets and their periodicity conditions, when structural consumption conflicts are resolved by a predefined “switching” mechanism, are developed. These equations can be viewed as a nonlinear extension of the evolution equations for event graphs. Min-max systems, i.e. systems described by equations with three operations: addition, maximization, and minimization, are also considered.

In the first two chapters classical concepts of system theory such as state space recursive equations, input-output transfer functions, and feedback loops are introduced. In addition, fundamental concepts from graph theory, matrix theory, Petri nets and their subclasses, and timed event graphs are formulated together with the most important theorems and several practical examples (from the areas of planning, communication, production, queuing systems, parallel computation and traffic control). In particular, Viterbi’s maximization algorithm for communication, shortest path dynamic programming algorithm for networks, critical path dynamic programming algorithm for task scheduling, and Karp’s cycle computation algorithm for the evaluation of eigenvalues and eigenvectors are presented. Description of flexible manufacturing systems, railway traffic systems, and systolic and wavefront array processors by means of linear algebra are also discussed by suitable examples. Finally it is shown that a class of continuous systems with flow limitation and mixing phenomena can be described by the same linear equations as the above- mentioned discrete problems. The Cayley-Hamilton theorem, which for conventional algebra states that a square matrix satisfies its own characteristic equation, is reformulated for an algebraic structure defined on a set \(S\) of elements supplied with two operations denoted \(\oplus\) and \(\otimes\) which obey the axioms of associativity of addition, commutativity of addition, associativity of multiplication, both right and left distributivity of multiplication over addition, existence of an identity element, and commutativity of multiplication. Fundamental concepts for Petri nets such as reachability tree, reachability graph, event graph, state machine, bounded, safe, live, consistent, synchronous, conservative nets, timed event graphs (autonomous and nonautonomous), stochastic event graphs, and multigraphs are introduced formally and by examples. The synchronization concept is modeled by means of Petri nets.

Chapters Three and Four deal thoroughly with max-plus algebra and with an algebraic system of dioids. The max-plus algebra is a special case of a dioid structure. It is argued that the dioid algebra appears to be the right tool to handle synchronization in a linear manner, even when the synchronization phenomenon seems to be very nonlinear. The theory of dioids can also be a good starting point to encompass such basic features of DEDS as concurrency but at the price of considering systems which are nonlinear even in this new framework.

Chapters Five and Six deal with the deterministic system theory of DEDS as described by the class of Petri nets called event graphs which are exclusively driven, from the system dynamics point of view, by synchronization phenomena. Each event graph can be described by linear equations built on some descriptive variables and an associated dioid algebra. Two dioid algebras are applied: one, in the event domain, called “dater” description and another, in the time domain, called “counter” description. The first indicates the moments of time when an event of a certain type happened, the second counts the number of events which happened before a certain moment of time. In addition, a third description involving power series in a two-dimensional domain of the event and time domains is also studied. The problems of “inverting” the system, and equivalence of rationality, periodicity, and realizability are also discussed.

In Chapter Seven and Eight, the theory of stochastic DEDS systems is elaborated. First, an ergodic theory of event graphs is presented. A set of equations which describe the evolution of daters is a basis of such systems having stationary properties. First the existence problem is stated in terms of a “random eigenpair problem” which is a generalization of the deterministic case. The Petri net analogue of the \(G/G/1\) queue is carefully analyzed using probabilistic formalism. First- order theorems, which indicate how the daters grow in such a stochastic framework, are proven. It happens that the growth rates are analogues of Lyapunov exponents in conventional algebra, and generalizations of cycle times in the deterministic case. Second-order theorems are concerned with the construction of the eigenpairs. This construction is based on the analysis of ratios of daters. Both nonautonomous and autonomous cases are considered. Conditions on the uniqueness and reachability of the stationary state are formulated for both cases. Explanations are presented using both stochastic Petri nets and corresponding dioids, and stochastic linear algebra. The main results of this chapter state that the cycle time of a stochastic event graph is the maximal Lyapunov exponent associated with the matrices of its standard equation and that stationary states correspond to stochastic eigenpairs of these matrices. Several illustrative examples (including acyclic fork-join networks of queues and systems of machines with blocking after service) are used simultaneously with theoretical arguments.

Chapter Nine is a loosely connected and coherent set of different ideas which did not fit into the previous chapters. A realization theory with a version of the Cayley-Hamilton theorem in the max-plus algebra environment and a special class of nonlinear systems characterized by the equation \(x(k+1) = A(u(k), u(k -1))x(k)\) are studied. The analogy between probability calculus and dynamic programming is presented: iterated convolutions of probability laws play the same role as the inf- convolution of cost functions. The Fourier transform is used as an analysis tool for probability laws and the Fenchel transform in the dynamic programming case. Asymptotic theorems for the value function of dynamic programming correspond to the law of large numbers and the central limit theorem, and quadratic forms, being a stable set of inf- convolution, correspond to Gaussian laws which are stable by convolution. Also basic equations that govern the evolution of general Petri nets and their periodicity conditions, when structural consumption conflicts are resolved by a predefined “switching” mechanism, are developed. These equations can be viewed as a nonlinear extension of the evolution equations for event graphs. Min-max systems, i.e. systems described by equations with three operations: addition, maximization, and minimization, are also considered.

##### MSC:

93-02 | Research exposition (monographs, survey articles) pertaining to systems and control theory |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

90B10 | Deterministic network models in operations research |

90C39 | Dynamic programming |

93A30 | Mathematical modelling of systems (MSC2010) |

93C05 | Linear systems in control theory |