License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2015.72
URN: urn:nbn:de:0030-drops-53813
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5381/
Go to the corresponding LIPIcs Volume Portal

La Torre, Salvatore ; Muscholl, Anca ; Walukiewicz, Igor

Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable

pdf-format:
21.pdf (0.7 MB)

Abstract

Verification of concurrent systems is a difficult problem in general, and this is the case even more in a parametrized setting where unboundedly many concurrent components are considered. Recently, Hague proposed an architecture with a leader process and unboundedly many copies of a contributor process interacting over a shared memory for which safety properties can be effectively verified. All processes in Hague's setting are pushdown automata. Here, we extend it by considering other formal models and, as a main contribution, find very liberal conditions on the individual processes under which the safety problem is decidable: the only substantial condition we require is the effective computability of the downward closure for the class of the leader processes. Furthermore, our result allows for a hierarchical approach to constructing models of concurrent systems with decidable safety problem: networks with tree-like architecture, where each process shares a register with its children processes (and another register with its parent). Nodes in such networks can be for instance pushdown automata, Petri nets, or multi-pushdown systems with decidable reachability problem.

BibTeX - Entry

@InProceedings{latorre_et_al:LIPIcs:2015:5381,
  author =	{Salvatore La Torre and Anca Muscholl and Igor Walukiewicz},
  title =	{{Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{72--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5381},
  URN =		{urn:nbn:de:0030-drops-53813},
  doi =		{10.4230/LIPIcs.CONCUR.2015.72},
  annote =	{Keywords: Verification, parametrized systems, shared memory}
}

Keywords: Verification, parametrized systems, shared memory
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

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