betaFeedback

WorksComputer Science

Safety Analysis of Parameterized Networks with Shared Counters

Abstract

We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.

Introduction

Verifying concurrent systems with an unbounded number of participants. When dealing with the verification of concurrent systems different aspects can be taken into account as the shape of the protocol executed by the different processes, the means of communication and the number of processes. For what concerns this latter aspect, in some cases, the system is designed for an unbounded (but fixed at each peculiar instance) of participants and in order to verify its correctness, one needs to analyze the behavior for all the possible number of participants or to find whether there exists a specific number for which a bug occurs. Such number is hence a parameter of the problem and this is the reason why we refer to this family of problems as parameterized verification. One of the difficulty lies in the fact that the number of networks to analyze is infinite. This is the setup that German and Sistla presented in [16], where they propose algorithms to verify networks of unbounded size where each participant executes the same finite-state protocol and the communication takes place thanks to pairwise rendez-vous, i.e., two processes agree to move synchronously. Interestingly, they show that some non-trivial temporal properties could be checked in polynomial time.

Varying the means of communication. In the last two decades, with the interest in developing automatic methods to analyze concurrent systems, many results have been found on the verification of parameterized networks considering various means of communication. In [12, 15], the authors have studied networks where the entities can write and read values from a finite set into a shared memory. In [1], the authors assume that the entities of the network can exchange a token and the communication primitives are either: give the token or take the token. As explained in [2] this latter case is a restriction of the rendez-vous communication. In [14], the entities communicate by broadcasting messages that can be received by everyone in the network. This setting has then been refined in [11, 10] to consider networks equipped with communication topologies where only the neighbors of a sender can see an emitted message. Closer to concurrent programming language primitives, the authors of [27] study the parameterized verification problem for processes sharing locks (with an unbounded number of locks) and in [9, 18] a different semantics of rendez-vous has been introduced in order to model the behavior of monitors with their wait and signal primitives. One remark is that in most of these works, except for the one with shared locks where lock creation is allowed, when the number of entities in the system is fixed and each entity runs a finite state protocol, the system to analyze is finite; the difficulty being to deal with an infinite number of instantiations of such systems.

Manipulating counters. In this work, we study parameterized verification problems for networks where each process executes the same finite state program manipulating some shared natural variables (called counters) which are initially set to 0. Such finite state programs are often referred to as counter machines and they have been intensively studied (in the case where they are executed by a single process). It is well-known that when we allow such programs to manipulate at least two counters and to perform increment, decrement and zero-test (such programs are often called Minsky machines), then even simple verification problems as the reachability of a control state become undecidable [28]. However decidability can be regained by imposing some restrictions on the counters. As a matter of fact, the reachability of a control state can be solved in NL (non-deterministic logarithmic space) [6, 23] for machines with a single counter (when the updates on the counters are encoded in unary) and other verification problems have been shown to be decidable and solvable with low complexity for this class of systems in [19, 17]. Forbidding the use of zero-tests leads as well to a class of well studied systems for which many verification problems are decidable, namely the Vector Addition Systems with States (VASS). The control state reachability for VASS is known to be EXPSPACE-complete [26, 29] whereas the reachability of a configuration (where both a control state and a value for the counters is provided) is Ackermann-complete [8, 24, 25]. This latter problem being intractable, some papers have provided some restrictions to circumvent this issue as for instance [5, 7, 13]. There is furthermore a strong connection between parameterized verification and VASS: in some cases the behavior of the network can be encoded into a VASS associating to each state of the protocol a counter whose value represents the number of processes in the associated state. This allows to use the numerous decidable results on VASS to perform parameterized verification see e.g. [16]. However, this translation is not always the best choice in term of complexity.

Our contributions. We study two parameterized verification problems for networks of entities with shared counters: the first one, we call the reachability problem (Reach), asks whether there is a network in which an execution leads to a configuration where (at least) one process ends in a final state and the second one, called the synchronization problem (Synchro), can be stated similarly but requires all the processes of the reached configuration to be in the final state. Note that when dealing with a single process, these two problems are equivalent and correspond to control state reachability. We first show that these two problems are undecidable in the general case. Even if this seems straightforward from the fact that the reachability problem is undecidable for two-counter Minsky machines, this first intuition is contradicted by the fact that in our networks it is not easy to extract a single process which can simulate on its own the Minsky machine and we need to rely on a trick. We then show that, as it is the case for classical counter machines, if we restrict our networks to use a single counter or not to use zero-tests, then the two problems become decidable. For the case with a single counter, we show that the reachability problem is NL-complete and that the synchronization problem can be solved in polynomial time (and is NL-complete too when we forbid the use of zero-tests). When we forbid the use of zero-tests, we obtain much better complexity as for VASS, as the two problems can be solved in polynomial time. Note that our results are not only interesting from a theoretical point of view, as shared counters could be interpreted in the paradigm of concurrent programming languages as semaphores (where a wait decrements the value of the counter and blocks if the value is 0 and a signal increments it). So our techniques for protocols with no zero-test can be used to verify parameterized systems with semaphores with 0 as an initial value. Oppositely to the single-process case, the initial value of the counters plays here a crucial role. Indeed, authorizing for instance a counter to have 1 as an initial value would allow to isolate a process (the first one performing a decrement on this counter) and to simulate afterwards the behavior of a VASS, which would lead to higher complexity bounds for the two considered problems.

ReachSynchro
No restrictionUndecidable [Thm. 4]Undecidable [Thm. 4]
One-counter and no zero-testNL-complete [Thm. 9]NL-complete [Thm. 15]
One-counterNL-complete [Thm. 9]in Ptime [Thm. 21]
No zero-testin Ptime [Thm. 7]in Ptime [Thm. 18]

Table 1. Summary of our results

Link with threshold automata. A model that seems close to the one we consider is the model of threshold automata, see e.g. [21, 3], used to represent the behavior of protocols designed for unbounded number of entities communicating via message passing and resilient to failures. Here as well, the protocol is modeled by a finite state automaton where each transition is labeled by some (global) guard and updates of shared variables. The shared variables are counters that can be only increased, because they are used to simulate the emission of a message whereas the guards can speak about the values of the shared variables but use as well parameters such as the number of failed processes. As a matter of fact, the model is incomparable to the one we study, because the counters behave in a monotonic way, but the guards can express more properties. In [21], the authors have studied an extension where the counters could as well be decremented and they show that reachability is undecidable for this model, but their undecidability proof used the fact that atomically a transition can test for the value of a counter and update it, which is something not allowed in our model.

Networks with shared counters

Preliminaries

We write N\mathbb{N} to denote the set of natural numbers and [i,j][i,j] to represent the set {k∈N∣i≤k and k≤j}\{k \in\mathbb{N} \mid i \leq k \text{ and } k \leq j\} for i,j∈Ni,j \in\mathbb{N}. For a set EE and a strictly positive natural kk, we denote by EkE^k the set of vectors of size kk whose elements are in EE and if v∈Ek\mathbf{v} \in E^k, then v[i]\mathbf{v}[i] represents the ithi^{\text{th}} element of v\mathbf{v} for all i∈[1,k]i \in[1,k]. In some cases, we might represent a vector v∈Ek\mathbf{v} \in E^k by the notation [v[1],v[2],…,v[k]][\mathbf{v}[1],\mathbf{v}[2],\ldots,\mathbf{v}[k]]. We denote by 0\mathbf{0} a vector where all elements are 0. For a vector v∈E1\mathbf{v} \in E^1, such that v[1]=e\mathbf{v}[1] = e, we will sometimes use the notation ee instead of [e][e].

Counter protocols

We present now our model of networks. We assume that all the processes in the network behave similarly following the same finite-state protocol which manipulates counters taking their values in N\mathbb{N}. When following the protocol, each entity has the ability, in an atomic way, to increase, decrease or compare the value of a counter with 0. For a natural $k \in N∖{0}\mathbb{N} \setminus\{0\}, we denote by ActCount⁡(k)\operatorname{ActCount}(k) the set of actions over kk counters represented by {inc⁡(c),dec⁡(c),zero⁡(c)∣0<c≤k}∪{τ}\{\operatorname{inc}(c), \operatorname{dec}(c), \operatorname{zero}(c) \mid0 < c \le k\} \cup\{\tau\} where inc⁡(c)\operatorname{inc}(c) is used to increment the value of the cthc^{\mathrm{th}} counter, dec⁡(c)\operatorname{dec}(c) to decrement it and zero⁡(c)\operatorname{zero}(c) to test if it is equal to 0 and τ\tau corresponds to an internal action having no effect on the counter values. When we will deal with a single counter, we shall simply write inc⁡\operatorname{inc}, dec⁡\operatorname{dec} and zero⁡\operatorname{zero} instead of inc⁡(1)\operatorname{inc}(1), dec⁡(1)\operatorname{dec}(1) and zero⁡(1)\operatorname{zero}(1).

Definition 1 (Counter protocol). A counter protocol Pr⁡\operatorname{Pr} is a tuple (Q,k,qin,qf,E)(Q,k,q_{\mathrm{in}},q_{\mathrm{f}},E) where QQ is a finite set of states, k∈N∖{0}k \in\mathbb{N} \setminus\{0\} is the number of counters, qin∈Qq_{\mathrm{in}} \in Q is the initial state, qf∈Qq_{\mathrm{f}} \in Q is the final state such that qin≠qfq_{\mathrm{in}} \ne q_{\mathrm{f}} and E⊆Q×ActCount⁡(k)×QE \subseteq Q \times\operatorname{ActCount}(k) \times Q is the set of edges labeled by actions over the kk counters.

A one-counter protocol is a counter protocol with a single counter (k=1k = 1) and a counter protocol is said to be zero-test free if there is no edge labeled with zero⁡(c)\operatorname{zero}(c) for 0<c≤k0 < c \le k.

Let Pr⁡=(Q,k,qin,qf,E)\operatorname{Pr} = (Q,k,q_{\mathrm{in}},q_{\mathrm{f}},E) be a counter protocol. A configuration γ\gamma with n>0n > 0 processes of Pr⁡\operatorname{Pr} is a pair γ=(s,v)\gamma= (\mathbf{s},\mathbf{v}) such that s∈Qn\mathbf{s} \in Q^n is a vector where s[p]\mathbf{s}[p] represents the state of the pthp^{\mathrm{th}} process for 0<p≤n0 < p \le n and v∈Nk\mathbf{v} \in\mathbb{N}^k where v[c]\mathbf{v}[c] provides the value of the cthc^{\mathrm{th}} counter for 0<c≤k0 < c \le k. We use ∥γ∥\lVert\gamma\rVert to represent nn, the number of processes in the configuration γ\gamma, and denote by Γn\Gamma_n the set of configurations with nn processes. The set of configurations is given by Γ=⋃n∈N∖{0}Γn\Gamma= \bigcup_{n \in\mathbb{N}\setminus\{0\}} \Gamma_n. The set of initial configurations is equal to Γin={γ=(s,0)∈Γ∣s[p]=qin for all 0<p≤∥γ∥}\Gamma_{\mathrm{in}} = \{\gamma= (\mathbf{s},\mathbf{0}) \in\Gamma\mid\mathbf{s}[p] = q_{\mathrm{in}}\text{ for all }0 < p \le\lVert\gamma\rVert\}. Hence in an initial configuration, all processes are in the initial state qinq_{\mathrm{in}} and all the counter values are set to 0. We consider two sets of final configurations: the first one Γ∃f={γ=(s,v)∈Γ∣∃0<p≤∥γ∥.s[p]=qf}\Gamma_{\exists\mathrm{f}} = \{\gamma= (\mathbf{s},\mathbf{v}) \in\Gamma\mid\exists0 < p \le\lVert\gamma\rVert.\mathbf{s}[p] = q_{\mathrm{f}}\} corresponds to the configurations where at least one process is in state qfq_{\mathrm{f}}; in the second one Γ∀f={γ=(s,v)∈Γ∣s[p]=qf for all 0<p≤∥γ∥}\Gamma_{\forall\mathrm{f}} = \{\gamma= (\mathbf{s},\mathbf{v}) \in\Gamma\mid\mathbf{s}[p] = q_{\mathrm{f}}\text{ for all }0 < p \le\lVert\gamma\rVert\} all processes are in state qfq_{\mathrm{f}}. Note that for the final configurations, the values of the counters are not taken into account.

The network semantics associated to the counter protocol Pr⁡\operatorname{Pr} is given by the labeled transition system (Γ,→)(\Gamma,\to) where →⊆Γ×N×E×Γ\to\subseteq\Gamma\times\mathbb{N} \times E \times\Gamma is the transition relation defined as follows. We have γ→p,eγ′\gamma\xrightarrow{p,e} \gamma' with γ=(s,v)\gamma= (\mathbf{s},\mathbf{v}) and γ′=(s′,v′)\gamma' = (\mathbf{s}',\mathbf{v}') iff ∥γ∥=∥γ′∥\lVert\gamma\rVert= \lVert\gamma'\rVert and 0<p≤∥γ∥0 < p \le\lVert\gamma\rVert and for all p′∈[1,∥γ∥]∖{p}p' \in[1,\lVert\gamma\rVert] \setminus\{p\}, s[p′]=s′[p′]\mathbf{s}[p'] = \mathbf{s}'[p'] and one of the following conditions holds:

  • e=(s[p],τ,s′[p])e = (\mathbf{s}[p],\tau,\mathbf{s}'[p]) and v=v′\mathbf{v} = \mathbf{v}';

  • e=(s[p],inc⁡(c),s′[p])e = (\mathbf{s}[p],\operatorname{inc}(c),\mathbf{s}'[p]) and v′[c]=v[c]+1\mathbf{v}'[c] = \mathbf{v}[c] + 1 and v′[c′]=v[c′]\mathbf{v}'[c'] = \mathbf{v}[c'] for all c′∈[1,k]∖{c}c' \in[1,k] \setminus\{c\};

  • e=(s[p],dec⁡(c),s′[p])e = (\mathbf{s}[p],\operatorname{dec}(c),\mathbf{s}'[p]) and v′[c]=v[c]−1\mathbf{v}'[c] = \mathbf{v}[c] - 1 and v′[c′]=v[c′]\mathbf{v}'[c'] = \mathbf{v}[c'] for all c′∈[1,k]∖{c}c' \in[1,k] \setminus\{c\} (since v′∈Nk\mathbf{v}' \in\mathbb{N}^k this implies v[c]>0\mathbf{v}[c] > 0);

  • e=(s[p],zero⁡(c),s′[p])e = (\mathbf{s}[p],\operatorname{zero}(c),\mathbf{s}'[p]) and v[c]=0\mathbf{v}[c] = 0 and v=v′\mathbf{v} = \mathbf{v}'.

References

  1. [1]B. Aminof, S. Jacobs, A. Khalimov, and S. Rubin. Parameterized model checking of token-passing systems. In VMCAl’14, Lecture Notes in Computer Science, pages 262–281. Springer, 2014.arxiv.org/abs/1311.4425
  2. [2]B. Aminof, T. Kotek, S. Rubin, F. Spegni, and H. Veith. Parameterized model checking of rendezvous systems. Distributed Comput., 31(3):187–222, 2018.
  3. [3]A. R. Balasubramanian, J. Esparza, and M. Lazic. Complexity of verification and synthesis of threshold automata. In ATVA’20, volume 12302 of LNCS, pages 144–160. Springer, 2020.
  4. [4]A. R. Balasubramanian, J. Esparza, and M. Raskin. Finding cut-offs in leaderless rendez-vous protocols is easy. In FOSSACS’21, volume 12650 of LNCS, pages 42–61. Springer, 2021.
  5. [5]M. Blondin, M. Englert, A. Finkel, S. Göller, C. Haase, R. Lazic, P. McKenzie, and P. Totzke. The reachability problem for two-dimensional vector addition systems with states. J. ACM, 68(5):34:1–34:43, 2021.DOI
  6. [6]D. Chistikov, W. Czerwinski, P. Hofman, M. Pilipczuk, and M. Wohar. Shortest paths in one-counter systems. Logical Methods in Computer Science, 15(1), 2019.
  7. [7]D. Chistikov, W. Czerwinski, F. Mazowiecki, L-Orlikowski, H. Sinclair-Banks, and K. Węgrzycki. The tractability border of reachability in simple vector addition systems with states. In FOCS’24, pages 1332–1354. IEEE, 2024.DOI
  8. [8]W. Czerwinski and L. Orlikowski. Reachability in vector addition systems is ackermann-complete. In FOCS’21, pages 1229–1240. IEEE, 2021.arxiv.org/abs/2104.13866
  9. [9]G. Delzanno, J.-F. Raskin, and L. Van Begin. Towards the automated verification of multi-threaded java programs. In TACAS’02, Lecture Notes in Computer Science, pages 173–187. Springer, 2002.
  10. [10]G. Delzanno, A. Sangnier, R. Traverso, and G. Zavattaro. On the complexity of parameterized reachability in reconfigurable broadcast networks. In FSTTCS’12, LIPIcs, pages 289–300. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.DOI
  11. [11]G. Delzanno, A. Sangnier, and G. Zavattaro. Parameterized verification of ad hoc networks. In CONCUR’10, Lecture Notes in Computer Science, pages 313–327. Springer, 2010.DOI
  12. [12]A. Durand-Gasselin, J. Esparza, P. Ganty, and R. Majumdar. Model checking parameterized asynchronous shared-memory systems. Formal Methods Syst. Des., 50(2-3):140–167, 2017.
  13. [13]M. Englert, R. Lazic, and P. Totzke. Reachability in two-dimensional unary vector addition systems with states is nL-complete. In LICS ’16, pages 477–484. ACM, 2016.arxiv.org/abs/1602.00477
  14. [14]J. Esparza, A. Finkel, and R. Mayr. On the verification of broadcast protocols. In LICS’99, pages 352–359. IEEE Computer Society, 1999.
  15. [15]J. Esparza, P. Ganty, and R. Majumdar. Parameterized verification of asynchronous shared-memory systems. J. ACM, 63(1):10:1–10:48, 2016.
  16. [16]S. M. German and A. P. Sistla. Reasoning about systems with many processes. Journal of the ACM, 39(3):675–735, 1992.
  17. [17]S. Göller, C. Haase, J. Ouaknine, and J. Worrell. Model checking succinct and parametric one-counter automata. In ICALP’10, Lecture Notes in Computer Science, pages 575–586. Springer, 2010.DOI
  18. [18]L. Guillou, A. Sangnier, and N. Sznajder. Safety analysis of parameterised networks with non-blocking rendez-vous. In CONCUR’23, LIPIcs, pages 7:1–7:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.arxiv.org/abs/2307.04546
  19. [19]C. Haase, S. Kreutzer, J. Ouaknine, and J. Worrell. Reachability in succinct and parametric one-counter automata. In CONCUR’09, Lecture Notes in Computer Science, pages 369–383. Springer, 2009.DOI
  20. [20]F. Horn and A. Sangnier. Deciding the existence of cut-off in parameterized rendez-vous networks. In CONCUR’20, volume 171 of LIPIcs, pages 46:1–46:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  21. [21]J. Kukovec, I. Konnov, and J. Widder. Reachability in parameterized systems: All flavors of threshold automata. In CONCUR’18, volume 118 of LIPIcs, pages 19:1–19:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.DOI
  22. [22]Richard E. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):18–20, 1975.DOI
  23. [23]P. Lafourcade, D. Lugiez, and R. Treinen. Intruder deduction for AC-like equational theories with homomorphisms. In RTA’05, volume 3467 of Lecture Notes in Computer Science, pages 308–322. Springer, 2005.
  24. [24]J. Leroux. The reachability problem for petri nets is not primitive recursive. In FOCS’21, pages 1241–1252. IEEE, 2021.arxiv.org/abs/2104.12695
  25. [25]J. Leroux and S. Schmitz. Reachability in vector addition systems is primitive-recursive in fixed dimension. In LICS’19, pages 1–13. IEEE, 2019.DOI
  26. [26]R.J. Lipton. The reachability problem requires exponential space. Research report (Yale University. Department of Computer Science). Department of Computer Science, Yale University, 1976.
  27. [27]C. Mascle, A. Muscholl, and I. Walukiewicz. Model-checking parametric lock-sharing systems against regular constraints. In CONCUR’23, LIPIcs, pages 24:1–24:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.arxiv.org/abs/2307.04925
  28. [28]M. Minsky. Computation, Finite and Infinite Machines. Prentice Hall, 1967.
  29. [29]C. Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223–231, 1978.DOI

Paper details

vlnc:W_d43eqm2a
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents