Timed Multiset Rewriting and the Verification of Time-Sensitive Distributed Systems

DOI10.1007/978-3-319-44878-7_14zbMATH Open1433.68058arXiv1606.07886OpenAlexW2471389158MaRDI QIDQ4603575FDOQ4603575

Authors: Tajana Ban Kirigin, Vivek Nigam, Max Kanovich, Andre Scedrov, Carolyn Talcott 

Publication date: 16 February 2018

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Time-Sensitive Distributed Systems (TSDS), such as applications using autonomous drones, achieve goals under possible environment interference (eg, winds). Moreover, goals are often specified using explicit time constraints which must be satisfied by the system emph{perpetually}. For example, drones carrying out the surveillance of some area must always have emph{recent pictures}, ie, at most $M$ time units old, of some strategic locations. This paper proposes a Multiset Rewriting language with explicit time for specifying and analysing TSDSes. We introduce two properties, emph{realizability} (some trace is good) and emph{survivability} (where, in addition, all admissible traces are good). A good trace is an infinite trace in which goals are perpetually satisfied. We propose a class of systems called emph{progressive timed systems} (PTS), where intuitively only a finite number of actions can be carried out in a bounded time period. We prove that for this class of systems both the realizability and the survivability problems are PSPACE-complete. Furthermore, if we impose a bound on time (as in bounded model-checking), we show that for PTS, realizability becomes NP-complete, while survivability is in the $Delt{a}_2^p$ class of the polynomial hierarchy. Finally, we demonstrate that the rewriting logic system Maude can be used to automate time bounded verification of PTS.

Full work available at URL: https://arxiv.org/abs/1606.07886

Recommendations

• On the complexity of verification of time-sensitive distributed systems
• Decidability of safety properties of timed multiset rewriting
• scientific article; zbMATH DE number 1070625
• scientific article; zbMATH DE number 1670505
• A multiset rewriting model for specifying and verifying timing aspects of security protocols
• Dealing with practical limitations of distributed timed model checking for timed automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Distributed systems (68M14)

Cited In (3)

• A Timed Mobility Semantics Based on Rewriting Strategies
• A semantic model for interacting cyber-physical systems
• On the complexity of verification of time-sensitive distributed systems

This page was built for publication: Timed Multiset Rewriting and the Verification of Time-Sensitive Distributed Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603575)