by Christian Zöllner, Matthias Barkowsky, Maria Maximova, Holger Giese
Abstract:
To develop future cyber-physical systems, like networks of autonomous vehicles, the modeling and simulation of huge networks of collaborating systems acting together on large-scale topologies is required. Probabilistic Timed Graph Transformation Systems (PTGTSs) have been introduced as a means of modeling a high-level view of these systems of systems. In our previous work, we proposed a simulation scheme based on local search incremental graph matching that can handle large-scale real-world topologies. However, the prohibitive complexity of the graph matching problem underlying the simulation of any GTS variant makes this setup potentially problematic. In this paper, we present an improved simulation algorithm and identify restrictions that hold for PTGTS high-level models of cyber-physical systems and real-world topologies, for which we can establish favorable worst-case complexity bounds. We show that the worst-case amortized complexity per simulation step is only logarithmic in the number of active collaborating systems (like vehicles) and constant concerning the size of the topology. The theoretical results are confirmed by experiments
Reference:
On the Complexity of Simulating Probabilistic Timed Graph Transformation Systems (Christian Zöllner, Matthias Barkowsky, Maria Maximova, Holger Giese), In Graph Transformation - 14th International Conference, ICGT 2021 Held as Part of STAF 2021, Virtual Event, June 24-25, 2021, Proceedings (Fabio Gadducci, Timo Kehrer, eds.), Springer, volume 12741, 2021.
Bibtex Entry:
@InProceedings{ZBMG2021_Complexity,
AUTHOR = {Zöllner, Christian and Barkowsky, Matthias and Maximova, Maria and Giese, Holger},
TITLE = {{On the Complexity of Simulating Probabilistic Timed Graph Transformation Systems}},
YEAR = {2021},
BOOKTITLE = {Graph Transformation - 14th International Conference, ICGT 2021 Held as Part of STAF 2021, Virtual Event, June 24-25, 2021, Proceedings},
VOLUME = {12741},
PAGES = {262--279},
EDITOR = {Gadducci, Fabio and Kehrer, Timo},
SERIES = {Lecture Notes in Computer Science},
PUBLISHER = {Springer},
URL = {https://doi.org/10.1007/978-3-030-78946-6_14},
PDF = {uploads/pdf/ZBMG2021_Complexity.pdf},
OPTacc_pdf = {},
ABSTRACT = {To develop future cyber-physical systems, like networks of autonomous vehicles, the modeling and simulation of huge networks of collaborating systems acting together on large-scale topologies is required. Probabilistic Timed Graph Transformation Systems (PTGTSs) have been introduced as a means of modeling a high-level view of these systems of systems. In our previous work, we proposed a simulation scheme based on local search incremental graph matching that can handle large-scale real-world topologies. However, the prohibitive complexity of the graph matching problem underlying the simulation of any GTS variant makes this setup potentially problematic.
In this paper, we present an improved simulation algorithm and identify restrictions that hold for PTGTS high-level models of cyber-physical systems and real-world topologies, for which we can establish favorable worst-case complexity bounds. We show that the worst-case amortized complexity per simulation step is only logarithmic in the number of active collaborating systems (like vehicles) and constant concerning the size of the topology. The theoretical results are confirmed by experiments}
}