Project topics and materials
Get Complete Project Material File(s) Now! »
Timed Petri Nets and Transportation Systems
Max-plus systems exactly correspond to a subclass of time Petri nets, called timed event graphs, timed marked graphs, or timed decision-free Petri nets. Petri nets are bipartitioned into two types of nodes: places and transitions. Event graphs are those Petri nets whose places have exactly one incoming and one outgoing transition. The qualifies “timed” refers to the fact that every place has a corresponding holding time for tokens that determines how long a token has to reside in the place before it can be consumed by the subsequent transition. One can identify transitions with nodes and places with edges to get an edge-weighted digraph, which corresponds to a max-plus matrix A. If all places initially have one token and there is at most one place between all pairs of transitions, then x(t + 1) = A ⊗ x(t) where xi (t) denotes the time that transition i fires for the tth time. We assume that the initial firing times x(0) are given. Hence we can directly apply our transience bounds to strongly connected timed event graphs that initially have one token at every place. If the number of tokens is different, then one nonetheless identify the Petri net with a max-plus linear system, but the dimension will be higher and it is not necessarily irreducible, even if the original Petri net is strongly connected.
A particular instance of timed event graphs that has attracted a lot of attention are train networks [56, Chapter 8]. The Petri net description includes the travel time between stops, the desired connecting train relations, as well as the time required to change trains. It has one transition for every outgoing track at every station. The places and edges are defined by the line’s trajectory and the connecting train relation. Consider the simple example network in Figure 2.3. It includes four stations, named M, N, O, and P. It has two train lines: Line A going from M to N and back; and Line B going from N to P via O and back. Each of the railway segments MN, NO, and OP possesses a certain travel time that the trains need to cover it; namely 25, 10, and 25 minutes, respectively. If one assumes that lines A and B should wait for each other at station N and that initially there is one train leaving every station in every possible direction, then the Petri net yields an irreducible max-plus matrix describing the necessary travel and changeover times in the train system. That is, the earliest times that the trains can leave is described by a max-plus linear system x(t) = A⊗t ⊗ x(0) with irreducible system matrix A.
However, trains do not always depart at the earliest possible time because they need to satisfy a pre-assigned schedule. Schedules are commonly purely periodic, i.e., of the form yi (t) = yi (0) + t • Δ where Δ is the schedule’s temporal period. The actual departure times in a system respecting the schedule are then given by z(t) = max{x(t), y(t)}.
One interesting performance parameter is the robustness of the system against delays. This can be modeled by the fact that the initial vector x(0) contains the incurred delays and one seeks to know the smallest t at which the system will be on schedule again, i.e., z(t) = y(t) or equivalently y(t) ≥ x(t). This smallest t is called the recovery time. Clearly, the system can only recover if λ = λ(A) < Δ, i.e., if the schedule leaves some headroom. In this case, Walks in Digraphs
Powers of a max-plus matrices also correspond to maximum weight walks in edge-weighted digraphs between two fixed nodes and of fixed length. In the particular case of non-weighted digraphs, they contain the information whether there exists a walk between two given nodes with a given length.
The periodicity of walk lengths in digraphs has been established and studied extensively, in particular for applications such as automata theory [74], but also for their general graph-theoretic interest [18]. The case of primitive matrices has attracted particular interest. Primi-tive digraphs are those that are connected and whose greatest common divisor of their cycle lengths is 1. Figure 2.4 shows an example of a primitive digraph; it would not be primitive without the edge from node 3 to node 2. An alternative definition for primitive digraphs is that some power of their adjacency matrix is strictly positive. In more concrete terms, this characterization reads:
Theorem 2.2 (Schwarz [81, Theorem 4.3]). Let G be a digraph. Then the sequence of digraphs Gt is eventually periodic.
We will call the transient of the sequence of digraphs G0, G1, G2, . . . the index of convergence and denote it by ind(G). It is exactly equal to the transient of the sequence of matrix pow-ers A⊗t where matrix A is defined by setting Ai,j = 0 if (i, j) is an edge of G and Ai,j = −∞ else. Matrices whose entries are in the two-element set {−∞, 0} are called Boolean matri-ces. Every product, and hence in particular every power, of Boolean matrices is Boolean. The study of transients of max-plus matrices, i.e., the study of maximum weight walks in weighted digraphs includes the study of Boolean matrices, i.e., unweighted digraphs, when setting all edge weights to 0.
State of the Art
Definitions and Preliminaries
A digraph is a pair G = (V, E) of a nonempty set V of nodes and a set E ⊆ V × V of edges. A walk W in G is a finite sequence of nodes i0, i1, . . . , iℓ such that (ir−1, ir ) ∈ E for all 1 ≤ r ≤ ℓ. We write ℓ(W) = ℓ for its length. It is empty if ℓ = 0 and closed if iℓ = i0. A walk in the digraph is a path if every node occurs only once. A closed walk is a cycle if it is nonempty and only the start and end node occurs twice.
The length of the shortest cycle in a digraph G is called the girth of G. If a digraph is strongly connected, the greatest common divisor of its cycle lengths is called its cyclicity. The cyclicity of a (possibly not strongly connected) digraph is the least common multiple of the cyclicities of its strongly connected components. The following two lemmas explicit the role and definition of the cyclicity of strongly connected digraphs.
Lemma 2.4. Let G be a strongly connected digraph with cyclicity γ. Then, for all nodes i and j and all walks W1, W2 from i to j, we have the congruence of lengths ℓ (W1) ≡ ℓ (W2) (mod γ).
A particular application of this notion is the existence of closed walks whose length are an arbitrary, sufficiently large, multiple of the cyclicity. Recall that ind(G) denotes the index of convergence of G.
Lemma 2.5. Let G be a strongly connected digraph with cyclicity γ. Then for all nodes i and all multiples t of γ with t ≥ ind(G), there exists a closed walk at i of length t.
The cyclicity has the property that it is an exponent for which a strongly connected di-graph is completely reducible, i.e., there are no edges between distinct strongly connected com-ponents. In a completely reducible digraph, the strongly and weakly connected components coincide.
For a digraph G and a nonnegative integer m, denote by Gm the mth Boolean power of G, i.e., the digraph that contains an edge (i, j) if and only if there exists a walk from i to j of length m in G.
Theorem 2.6 ([18, Theorem 3.4.5]). Let G be a strongly connected digraph with cyclicity γ = γ(G).
Then Gγ is completely reducible and its components have cyclicity 1.
To every n × n max-plus matrix A corresponds a digraph G(A) with node set V = [n] = {1, 2, . . . , n} containing an edge (i, j) if and only if Ai,j = −∞. We refer to Ai,j as the weight of edge (i, j). Matrix A is irreducible if G(A) is strongly connected. If W is a walk in G(A), we define its weight A(W) as the sum of the weights of its edges. The entry Ai⊗,jt is the maximum weight of walks from i to j of length t. We follow the convention that max ∅ = −∞. If v is a max-plus column vector of size n, then the entry A⊗t ⊗ v i is the maximum of the values A(W) + vj where the maximum is formed over all nodes j and all walks W from i to j of length t.
Denote by λ(A) the maximum mean weight A(Z)/ℓ(Z) of cycles in G(A). We call critical every cycle with maximum mean weight. The sub-digraph of G(A) induced by edges on critical cycles is called its critical digraph.
Table of contents :
Acknowledgments
1 Introduction
1.1 Structure of the Thesis and Contribution
I Transience of Distributed Algorithms
2 Max-Plus Linear Algorithms
2.1 Introduction
2.2 Applications
2.2.1 Synchronizers
2.2.2 Cyclic Scheduling
2.2.3 Full Reversal Routing and Scheduling
2.2.4 Timed Petri Nets and Transportation Systems
2.2.5 Walks in Digraphs
2.3 State of the Art
2.3.1 Definitions and Preliminaries
2.3.2 Eventually Periodic Sequences
2.3.3 Boolean Matrices
2.3.4 Nachtigall Decomposition
2.3.5 Bound by Hartmann and Arguelles
2.3.6 A Bound for Primitive Matrices
2.3.7 When All Entries Are Finite
2.4 Comparison of the Existing Boolean Bounds
3 Transients of Critical Nodes
3.1 Proof of Weighted Dulmage-Mendelsohn Transience Bound
3.2 Proof of WeightedWielandt Transience Bound
3.2.1 Walk-Multigraph Correspondence
3.2.2 Critical Hamiltonian Cycles
3.3 Proof of Weighted Schwarz Transience Bound
3.4 Proof of Weighted Kim Transience Bound
3.5 Proof of Weighted Bounds Involving the Factor Rank
4 Global Transience Bounds
4.1 Results
4.1.1 Hartmann-Arguelles Scheme
4.1.2 Cycle Threshold Scheme
4.1.3 Comparison of the Different Schemes
4.2 Applications
4.2.1 Synchronizers
4.2.2 Cyclic Scheduling
4.2.3 Link Reversal
4.3 Proof Strategy for Matrix Transients
4.4 Pumping in the Critical Digraph
4.5 Walk Reductions
4.5.1 Walk Reduction by Repeated Cycle Removal
4.5.2 Walk Reduction by Arithmetic Method
4.5.3 Walk Reduction by Cycle Decomposition
4.6 Critical Bound
4.6.1 Avoiding Super-Digraphs of the Critical Digraph
4.6.2 Hartmann-Arguelles Scheme
4.6.3 Cycle Threshold Scheme
4.7 Putting it Together
4.8 Linear Systems
4.8.1 Modified Proof Strategy
4.8.2 Critical Bounds for Systems
4.9 Matrix vs. System Transients
4.10 A Closer Look at the Nachtigall Decomposition
4.10.1 Transience Bounds via Critical Bound
4.10.2 Nachtigall Decomposition
4.10.3 Transience Bounds via Nachtigall Decomposition
5 Asymptotic Consensus
5.1 Introduction
5.2 State of the Art
5.3 Rate of Convergence in Constant Synchronous Settings
5.3.1 The Reversible Case
5.3.2 Extension to the Non-Reversible Case
5.3.3 Dynamic Settings with Constant Perron Vector
5.3.4 Worst-Case Lower Bound
5.4 Asymptotic Consensus in Dynamic Settings with Aperiodic Core
5.4.1 Coefficient of Ergodicity
5.4.2 Proving Convergence with the Semi-norm
5.4.3 Aperiodic Cores
5.4.4 Coordinated Aperiodic Cores
5.4.5 Clusterings
5.4.6 Dynamic Coordinated Communication Digraphs
5.4.7 Dynamic Communication Digraphs with Fixed Leader
5.4.8 Completely Reducible Communication Digraphs
II Glitch Propagation
6 Glitch Propagation in Digital Circuits
6.1 Introduction
6.2 State of the Art
6.3 Short Pulse Filtration
6.4 Short Pulse Filtration in Physical Systems
6.4.1 Unsolvability of Bounded Short Pulse Filtration
6.4.2 Solvability of Unbounded Short Pulse Filtration
7 Binary CircuitModel
7.1 Basics: Signals, Circuits, Executions, Problem Definition
7.1.1 Signals
7.1.2 Circuits
7.1.3 Executions
7.1.4 Short Pulse Filtration
7.2 Bounded Single-History Channels
7.2.1 Forgetful Single-History Channels
7.2.2 Non-Forgetful Single-History Channels
7.2.3 Examples of Single-History Channels
7.3 Involution Channels
7.4 Constructing Executions with Involution Channels
7.5 Specific Class of Involution Channels: Exp-Channels
8 Unbounded Short Pulse Filtration in Binary Models
8.1 Unsolvability of Unbounded SPF with Constant Channels
8.1.1 Dependence Graphs
8.1.2 Unsolvability Proof
8.2 Solvability of Unbounded SPF with Involution Channels
8.3 Eventual SPF with Constant Delay Channels
9 Bounded Short Pulse Filtration in BinaryModels
9.1 Unsolvability of Bounded SPF with Involution Channels
9.1.1 Continuity of Involution Channels
9.1.2 Unsolvability in Forward Circuits
9.1.3 Simulation with Unrolled Circuits
9.1.4 The Unsolvability Result
9.2 Solvability of Bounded SPF with One Non-Constant Channel
9.2.1 Forgetful Channels
9.2.2 Non-Forgetful Channels
10 Conclusion
Bibliography
