License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.24
URN: urn:nbn:de:0030-drops-170874
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17087/
Go to the corresponding LIPIcs Volume Portal

Bozga, Marius ; Bueri, Lucas ; Iosif, Radu

On an Invariance Problem for Parameterized Concurrent Systems

pdf-format:
LIPIcs-CONCUR-2022-24.pdf (0.8 MB)

Abstract

We consider concurrent systems consisting of replicated finite-state processes that synchronize via joint interactions in a network with user-defined topology. The system is specified using a resource logic with a multiplicative connective and inductively defined predicates, reminiscent of Separation Logic [John C. Reynolds, 2002]. The problem we consider is if a given formula in this logic defines an invariant, namely whether any model of the formula, following an arbitrary firing sequence of interactions, is transformed into another model of the same formula. This property, called havoc invariance, is quintessential in proving the correctness of reconfiguration programs that change the structure of the network at runtime. We show that the havoc invariance problem is many-one reducible to the entailment problem ϕ ⊧ ψ, asking if any model of ϕ is also a model of ψ. Although, in general, havoc invariance is found to be undecidable, this reduction allows to prove that havoc invariance is in 2EXP, for a general fragment of the logic, with a 2EXP entailment problem.

BibTeX - Entry

@InProceedings{bozga_et_al:LIPIcs.CONCUR.2022.24,
  author =	{Bozga, Marius and Bueri, Lucas and Iosif, Radu},
  title =	{{On an Invariance Problem for Parameterized Concurrent Systems}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17087},
  URN =		{urn:nbn:de:0030-drops-170874},
  doi =		{10.4230/LIPIcs.CONCUR.2022.24},
  annote =	{Keywords: parameterized verification, invariant checking, resource logics, reconfigurable systems, tree automata}
}

Keywords: parameterized verification, invariant checking, resource logics, reconfigurable systems, tree automata
Collection: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue Date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI