Abstract
Max-Plus Linear (MPL) systems are essential for modeling synchronization in discrete-event systems like transportation and manufacturing networks. However, formal verification of these systems is historically challenging due to infinite state spaces and the computational complexity of existing abstraction-based methods. This paper presents a robust framework for the formal verification of MPL systems using a new logic called Time-Difference LTL (TDLTL) and specialized Satisfiability Modulo Theory (SMT) algorithms. By exploiting the deterministic and eventually periodic nature of MPL systems, the proposed approach achieves significant speedups over traditional model checkers and enables the verification of large-scale networks, such as the London Underground.
Introduction
Max-Plus Linear (MPL) systems are a specific class of discrete-event systems where state transitions are governed by maximization and addition. These operations make them ideal for modeling "synchronization without concurrency," such as a train station where a connecting train must wait for the slowest incoming arrival.
Despite their utility, two major hurdles remain for practical engineering:
- Structural Analysis: Determining the "transient" (the time to reach steady state) and "cyclicity" (the period of that state) is computationally expensive.
- Temporal Verification: Specifying and checking complex requirements, such as maximum allowable delays between events, has lacked a general framework. Previous attempts relied on state-space abstractions that suffer from exponential "state-explosion" as system variables increase.
Methods
The authors address these challenges by shifting from traditional model checking to a symbolic, SMT-based approach.
Time-Difference LTL (TDLTL)
A new temporal logic, TDLTL, is introduced to specify requirements based on the difference between event times. This is critical because absolute time values in MPL systems often diverge to infinity, while the relative differences between events remain stable and predictable.
SMT-Based Verification and Completeness Thresholds
Instead of using off-the-shelf model checkers like nuXmv, which struggle with infinite time-stamps, the authors developed specialized algorithms using Quantifier-Free Real Difference Logic (QF_RDL). This approach leverages the fact that MPL systems are deterministic; a single initial state produces exactly one trajectory or "orbit."
As shown in the figure above, MPL systems eventually settle into a periodic regime. The authors proved that the system's transient and cyclicity provide a "completeness threshold." If a property holds through the transient phase and one full cycle, it is guaranteed to hold indefinitely. This allows the algorithm to check only a finite number of steps to prove properties over an infinite horizon.
Results and Case Studies
The framework was evaluated using synthetic benchmarks and a real-world case study of the London Underground.
- Synthetic Benchmarks: Testing on 1,000 randomly generated matrices (up to dimension $n=40$) showed that the SMT-based
SMT-DLalgorithm consistently outperformed traditional tools. WhilenuXmvoften timed out after 1,000 seconds, the SMT approach frequently finished in under 100 seconds. - London Underground: The researchers successfully verified properties on the District line, which involves 113 variables. Previous abstraction-based methods were practically unable to handle more than a few variables. The analysis confirmed that the absolute difference between departures at terminus stations remains under 300 seconds, while also identifying cases where trains do not depart simultaneously.
Conclusion and Future Work
This research demonstrates that SMT-based verification, particularly the "initialised" approach that projects requirements back onto the starting state, is significantly more efficient for MPL systems than traditional abstraction. Future work will focus on extending these methods to reducible matrices (which may have multiple eigenvalues) and parametric MPL systems where delays are represented as symbolic expressions rather than fixed values.
Summary updated