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.
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} N to denote the set of natural numbers and [ i , j ] [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\} { k ∈ N ∣ i ≤ k and k ≤ j } for i , j ∈ N i,j \in\mathbb{N} i , j ∈ N . For a set E E E and a strictly positive natural k k k , we denote by E k E^k E k the set of vectors of size k k k whose elements are in E E E and if v ∈ E k \mathbf{v} \in E^k v ∈ E k , then v [ i ] \mathbf{v}[i] v [ i ] represents the i th i^{\text{th}} i th element of v \mathbf{v} v for all i ∈ [ 1 , k ] i \in[1,k] i ∈ [ 1 , k ] . In some cases, we might represent a vector v ∈ E k \mathbf{v} \in E^k v ∈ E k by the notation [ v [ 1 ] , v [ 2 ] , … , v [ k ] ] [\mathbf{v}[1],\mathbf{v}[2],\ldots,\mathbf{v}[k]] [ v [ 1 ] , v [ 2 ] , … , v [ k ]] . We denote by 0 \mathbf{0} 0 a vector where all elements are 0. For a vector v ∈ E 1 \mathbf{v} \in E^1 v ∈ E 1 , such that v [ 1 ] = e \mathbf{v}[1] = e v [ 1 ] = e , we will sometimes use the notation e e e instead of [ e ] [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} 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\} N ∖ { 0 } , we denote by ActCount ( k ) \operatorname{ActCount}(k) ActCount ( k ) the set of actions over k k k 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\} { inc ( c ) , dec ( c ) , zero ( c ) ∣ 0 < c ≤ k } ∪ { τ } where inc ( c ) \operatorname{inc}(c) inc ( c ) is used to increment the value of the c t h c^{\mathrm{th}} c th counter, dec ( c ) \operatorname{dec}(c) dec ( c ) to decrement it and zero ( c ) \operatorname{zero}(c) 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} inc , dec \operatorname{dec} dec and zero \operatorname{zero} zero instead of inc ( 1 ) \operatorname{inc}(1) inc ( 1 ) , dec ( 1 ) \operatorname{dec}(1) dec ( 1 ) and zero ( 1 ) \operatorname{zero}(1) zero ( 1 ) .
Definition 1 (Counter protocol). A counter protocol Pr \operatorname{Pr} Pr is a tuple ( Q , k , q i n , q f , E ) (Q,k,q_{\mathrm{in}},q_{\mathrm{f}},E) ( Q , k , q in , q f , E ) where Q Q Q is a finite set of states, k ∈ N ∖ { 0 } k \in\mathbb{N} \setminus\{0\} k ∈ N ∖ { 0 } is the number of counters, q i n ∈ Q q_{\mathrm{in}} \in Q q in ∈ Q is the initial state, q f ∈ Q q_{\mathrm{f}} \in Q q f ∈ Q is the final state such that q i n ≠ q f q_{\mathrm{in}} \ne q_{\mathrm{f}} q in = q f and E ⊆ Q × ActCount ( k ) × Q E \subseteq Q \times\operatorname{ActCount}(k) \times Q E ⊆ Q × ActCount ( k ) × Q is the set of edges labeled by actions over the k k k counters.
A one-counter protocol is a counter protocol with a single counter (k = 1 k = 1 k = 1 ) and a counter protocol is said to be zero-test free if there is no edge labeled with zero ( c ) \operatorname{zero}(c) zero ( c ) for 0 < c ≤ k 0 < c \le k 0 < c ≤ k .
Let Pr = ( Q , k , q i n , q f , E ) \operatorname{Pr} = (Q,k,q_{\mathrm{in}},q_{\mathrm{f}},E) Pr = ( Q , k , q in , q f , E ) be a counter protocol. A configuration γ \gamma γ with n > 0 n > 0 n > 0 processes of Pr \operatorname{Pr} Pr is a pair γ = ( s , v ) \gamma= (\mathbf{s},\mathbf{v}) γ = ( s , v ) such that s ∈ Q n \mathbf{s} \in Q^n s ∈ Q n is a vector where s [ p ] \mathbf{s}[p] s [ p ] represents the state of the p t h p^{\mathrm{th}} p th process for 0 < p ≤ n 0 < p \le n 0 < p ≤ n and v ∈ N k \mathbf{v} \in\mathbb{N}^k v ∈ N k where v [ c ] \mathbf{v}[c] v [ c ] provides the value of the c t h c^{\mathrm{th}} c th counter for 0 < c ≤ k 0 < c \le k 0 < c ≤ k . We use ∥ γ ∥ \lVert\gamma\rVert ∥ γ ∥ to represent n n n , the number of processes in the configuration γ \gamma γ , and denote by Γ n \Gamma_n Γ n the set of configurations with n n n processes. The set of configurations is given by Γ = ⋃ n ∈ N ∖ { 0 } Γ n \Gamma= \bigcup_{n \in\mathbb{N}\setminus\{0\}} \Gamma_n Γ = ⋃ n ∈ N ∖ { 0 } Γ n . The set of initial configurations is equal to Γ i n = { γ = ( s , 0 ) ∈ Γ ∣ s [ p ] = q i n 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\} Γ in = { γ = ( s , 0 ) ∈ Γ ∣ s [ p ] = q in for all 0 < p ≤ ∥ γ ∥} . Hence in an initial configuration, all processes are in the initial state q i n q_{\mathrm{in}} q 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 ] = q f } \Gamma_{\exists\mathrm{f}} = \{\gamma= (\mathbf{s},\mathbf{v}) \in\Gamma\mid\exists0 < p \le\lVert\gamma\rVert.\mathbf{s}[p] = q_{\mathrm{f}}\} Γ ∃ f = { γ = ( s , v ) ∈ Γ ∣ ∃0 < p ≤ ∥ γ ∥ . s [ p ] = q f } corresponds to the configurations where at least one process is in state q f q_{\mathrm{f}} q f ; in the second one Γ ∀ f = { γ = ( s , v ) ∈ Γ ∣ s [ p ] = q f 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\} Γ ∀ f = { γ = ( s , v ) ∈ Γ ∣ s [ p ] = q f for all 0 < p ≤ ∥ γ ∥} all processes are in state q f q_{\mathrm{f}} q 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} Pr is given by the labeled transition system ( Γ , → ) (\Gamma,\to) ( Γ , → ) where → ⊆ Γ × N × E × Γ \to\subseteq\Gamma\times\mathbb{N} \times E \times\Gamma →⊆ Γ × N × E × Γ is the transition relation defined as follows. We have γ → p , e γ ′ \gamma\xrightarrow{p,e} \gamma' γ p , e γ ′ with γ = ( s , v ) \gamma= (\mathbf{s},\mathbf{v}) γ = ( s , v ) and γ ′ = ( s ′ , v ′ ) \gamma' = (\mathbf{s}',\mathbf{v}') γ ′ = ( s ′ , v ′ ) iff ∥ γ ∥ = ∥ γ ′ ∥ \lVert\gamma\rVert= \lVert\gamma'\rVert ∥ γ ∥ = ∥ γ ′ ∥ and 0 < p ≤ ∥ γ ∥ 0 < p \le\lVert\gamma\rVert 0 < p ≤ ∥ γ ∥ and for all p ′ ∈ [ 1 , ∥ γ ∥ ] ∖ { p } p' \in[1,\lVert\gamma\rVert] \setminus\{p\} p ′ ∈ [ 1 , ∥ γ ∥] ∖ { p } , s [ p ′ ] = s ′ [ p ′ ] \mathbf{s}[p'] = \mathbf{s}'[p'] s [ p ′ ] = s ′ [ p ′ ] and one of the following conditions holds:
e = ( s [ p ] , τ , s ′ [ p ] ) e = (\mathbf{s}[p],\tau,\mathbf{s}'[p]) e = ( s [ p ] , τ , s ′ [ p ]) and v = v ′ \mathbf{v} = \mathbf{v}' v = v ′ ;
e = ( s [ p ] , inc ( c ) , s ′ [ p ] ) e = (\mathbf{s}[p],\operatorname{inc}(c),\mathbf{s}'[p]) e = ( s [ p ] , inc ( c ) , s ′ [ p ]) and v ′ [ c ] = v [ c ] + 1 \mathbf{v}'[c] = \mathbf{v}[c] + 1 v ′ [ c ] = v [ c ] + 1 and v ′ [ c ′ ] = v [ c ′ ] \mathbf{v}'[c'] = \mathbf{v}[c'] v ′ [ c ′ ] = v [ c ′ ] for all c ′ ∈ [ 1 , k ] ∖ { c } c' \in[1,k] \setminus\{c\} c ′ ∈ [ 1 , k ] ∖ { c } ;
e = ( s [ p ] , dec ( c ) , s ′ [ p ] ) e = (\mathbf{s}[p],\operatorname{dec}(c),\mathbf{s}'[p]) e = ( s [ p ] , dec ( c ) , s ′ [ p ]) and v ′ [ c ] = v [ c ] − 1 \mathbf{v}'[c] = \mathbf{v}[c] - 1 v ′ [ c ] = v [ c ] − 1 and v ′ [ c ′ ] = v [ c ′ ] \mathbf{v}'[c'] = \mathbf{v}[c'] v ′ [ c ′ ] = v [ c ′ ] for all c ′ ∈ [ 1 , k ] ∖ { c } c' \in[1,k] \setminus\{c\} c ′ ∈ [ 1 , k ] ∖ { c } (since v ′ ∈ N k \mathbf{v}' \in\mathbb{N}^k v ′ ∈ N k this implies v [ c ] > 0 \mathbf{v}[c] > 0 v [ c ] > 0 );
e = ( s [ p ] , zero ( c ) , s ′ [ p ] ) e = (\mathbf{s}[p],\operatorname{zero}(c),\mathbf{s}'[p]) e = ( s [ p ] , zero ( c ) , s ′ [ p ]) and v [ c ] = 0 \mathbf{v}[c] = 0 v [ c ] = 0 and v = v ′ \mathbf{v} = \mathbf{v}' v = v ′ .
Note that when going from the configuration γ \gamma γ to γ ′ \gamma' γ ′ the number of processes does not change and at most one process, the one executing the action given by the edge e e e , changes its state and performs the associated update/test on the counters. Notice that each action is performed atomically as when a process p p p performs an action, it is not interrupted by another process. We will write γ → γ ′ \gamma\to\gamma' γ → γ ′ if there exists p ∈ N p \in\mathbb{N} p ∈ N and e ∈ E e \in E e ∈ E such that γ → p , e γ ′ \gamma\xrightarrow{p,e} \gamma' γ p , e γ ′ and use → ∗ \to^* → ∗ to describe the reflexive and transitive closure of → \to → . A n n n -process run ρ \rho ρ of the counter protocol Pr \operatorname{Pr} Pr is given by a finite sequence of the form: ρ : = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho\mathrel{:=} \gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell ρ := γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ where γ 0 \gamma_0 γ 0 is a configuration with n n n processes. For such a run, we denote by first ( ρ ) \operatorname{first}(\rho) first ( ρ ) [resp. last ( ρ ) \operatorname{last}(\rho) last ( ρ ) ] its first [resp. last] configuration γ 0 \gamma_0 γ 0 [resp. γ ℓ \gamma_\ell γ ℓ ]. We use as well len ( ρ ) \operatorname{len}(\rho) len ( ρ ) to represent the length ℓ \ell ℓ of ρ \rho ρ and denote by actions ( ρ ) \operatorname{actions}(\rho) actions ( ρ ) the sequence ( p 1 , e 1 ) ( p 2 , e 2 ) ⋯ ( p ℓ , e ℓ ) (p_1,e_1)(p_2,e_2)\cdots(p_\ell,e_\ell) ( p 1 , e 1 ) ( p 2 , e 2 ) ⋯ ( p ℓ , e ℓ ) . A run ρ \rho ρ is initial whenever first ( ρ ) \operatorname{first}(\rho) first ( ρ ) belongs to Γ i n \Gamma_{\mathrm{in}} Γ in . For i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] , we denote by ρ ≤ i \rho_{\le i} ρ ≤ i the prefix γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p i , e i γ i \gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_i,e_i} \gamma_i γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p i , e i γ i of the run ρ \rho ρ . Given two n n n -process runs ρ \rho ρ and ρ ′ \rho' ρ ′ with last ( ρ ) = first ( ρ ′ ) \operatorname{last}(\rho) = \operatorname{first}(\rho') last ( ρ ) = first ( ρ ′ ) , we can build a third run obtained by executing ρ ′ \rho' ρ ′ after ρ \rho ρ and, which we shall denote as ρ . ρ ′ \rho.\rho' ρ . ρ ′ .
Example 2. Figure 1 presents an example of a counter protocol Pr with three counters. A possible initial 3-process run of Pr is ( [ q i n , q i n , q i n ] , [ 0 , 0 , 0 ] ) → ( [ q 1 , q i n , q i n ] , [ 1 , 0 , 0 ] ) → ( [ q 1 , q 1 , q i n ] , [ 2 , 0 , 0 ] ) → ( [ q 2 , q 1 , q i n ] , [ 1 , 0 , 0 ] ) → ( [ q 1 , q 1 , q i n ] , [ 1 , 1 , 0 ] ) → ( [ q 2 , q 1 , q i n ] , [ 0 , 1 , 0 ] ) → ( [ q 1 , q 1 , q i n ] , [ 0 , 2 , 0 ] ) → ( [ q 1 , q 3 , q i n ] , [ 0 , 1 , 0 ] ) → ( [ q 1 , q 4 , q i n ] , [ 0 , 0 , 0 ] ) → ( [ q 1 , q 5 , q i n ] , [ 0 , 0 , 0 ] ) → ( [ q 1 , q f , q i n ] , [ 0 , 0 , 1 ] ) → ( [ q 1 , q f , q 6 ] , [ 0 , 0 , 0 ] ) → ( [ q 1 , q f , q f ] , [ 0 , 0 , 0 ] ) ([q_{in},q_{in},q_{in}],[0,0,0]) \to([q_1,q_{in},q_{in}],[1,0,0]) \to([q_1,q_1,q_{in}],[2,0,0]) \to([q_2,q_1,q_{in}],[1,0,0]) \to([q_1,q_1,q_{in}],[1,1,0]) \to([q_2,q_1,q_{in}],[0,1,0]) \to([q_1,q_1,q_{in}],[0,2,0]) \to([q_1,q_3,q_{in}],[0,1,0]) \to([q_1,q_4,q_{in}],[0,0,0]) \to([q_1,q_5,q_{in}],[0,0,0]) \to([q_1,q_f,q_{in}],[0,0,1]) \to([q_1,q_f,q_6],[0,0,0]) \to([q_1,q_f,q_f],[0,0,0]) ([ q in , q in , q in ] , [ 0 , 0 , 0 ]) → ([ q 1 , q in , q in ] , [ 1 , 0 , 0 ]) → ([ q 1 , q 1 , q in ] , [ 2 , 0 , 0 ]) → ([ q 2 , q 1 , q in ] , [ 1 , 0 , 0 ]) → ([ q 1 , q 1 , q in ] , [ 1 , 1 , 0 ]) → ([ q 2 , q 1 , q in ] , [ 0 , 1 , 0 ]) → ([ q 1 , q 1 , q in ] , [ 0 , 2 , 0 ]) → ([ q 1 , q 3 , q in ] , [ 0 , 1 , 0 ]) → ([ q 1 , q 4 , q in ] , [ 0 , 0 , 0 ]) → ([ q 1 , q 5 , q in ] , [ 0 , 0 , 0 ]) → ([ q 1 , q f , q in ] , [ 0 , 0 , 1 ]) → ([ q 1 , q f , q 6 ] , [ 0 , 0 , 0 ]) → ([ q 1 , q f , q f ] , [ 0 , 0 , 0 ]) .
Figure 1. Example of a counter protocol
Verification problems and known results
In this work, we focus on two parameterized questions which ask whether there exists a number of processes allowing to reach a configuration where one process is in the final state or where all processes are in the final state. The first one called the reachability problem is:
Reach
Input: A counter protocol P r = ( Q , k , q i n , q f , E ) \mathrm{Pr}=(Q,k,q_{in},q_f,E) Pr = ( Q , k , q in , q f , E ) ;
Question: Does there exist γ i n ∈ Γ i n \gamma_{in}\in\Gamma_{in} γ in ∈ Γ in and γ f ∈ Γ ∃ f \gamma_f\in\Gamma_{\exists f} γ f ∈ Γ ∃ f such that γ i n → ∗ γ f \gamma_{in}\to^*\gamma_f γ in → ∗ γ f ?
If the answer is positive, we say that q f q_f q f is existentially reachable by Pr. The second problem is the synchronization problem :
Synchro
Input: A counter protocol P r = ( Q , k , q i n , q f , E ) \mathrm{Pr}=(Q,k,q_{in},q_f,E) Pr = ( Q , k , q in , q f , E ) ;
Question: Does there exist γ i n ∈ Γ i n \gamma_{in}\in\Gamma_{in} γ in ∈ Γ in and γ f ∈ Γ ∀ f \gamma_f\in\Gamma_{\forall f} γ f ∈ Γ ∀ f such that γ i n → ∗ γ f \gamma_{in}\to^*\gamma_f γ in → ∗ γ f ?
If the answer is positive, we say that q f q_f q f is universally reachable by Pr. We will as well consider the unparameterized version of these problems and denote by F i x R e a c h [ n ] \mathrm{FixReach}[n] FixReach [ n ] [resp. F i x S y n c h r o [ n ] \mathrm{FixSynchro}[n] FixSynchro [ n ] ] (for n > 0 n>0 n > 0 ) the variation of R e a c h \mathrm{Reach} Reach [resp. $\mathrm{Synchro}] where we impose the initial configuration to have n n n processes (i.e., we add the condition ∥ γ i n ∥ = n \lVert\gamma_{in}\rVert=n ∥ γ in ∥ = n ) where n n n is a strictly positive natural encoded in unary. Note that in this context, F i x R e a c h [ 1 ] \mathrm{FixReach}[1] FixReach [ 1 ] and F i x S y n c h r o [ 1 ] \mathrm{FixSynchro}[1] FixSynchro [ 1 ] are the same since we have a single process.
The cases where we have a single process are well studied problems and it corresponds to the study of so-called counter machines. When such machines manipulate at least two counters, then the reachability problem is undecidable [28 ] . One way to regain decidability consists in either considering one counter automata or to forbid the use of equality tests with 0 (and we obtain then VASS). The known results can be reformulated in our context:
Theorem 3.
F i x R e a c h [ 1 ] \mathrm{FixReach}[1] FixReach [ 1 ] is undecidable [28 ] .
F i x R e a c h [ 1 ] \mathrm{FixReach}[1] FixReach [ 1 ] restricted to one-counter protocols is NL-complete [6 , 23 ] .
Given two states q , q ′ q,q' q , q ′ of a one-counter protocol, deciding whether ( [ q ] , 0 ) → ∗ ( [ q ′ ] , 0 ) ([q],0)\to^*([q'],0) ([ q ] , 0 ) → ∗ ([ q ′ ] , 0 ) is NL-complete [6 , 23 ] .
F i x R e a c h [ 1 ] \mathrm{FixReach}[1] FixReach [ 1 ] restricted to zero-test free protocols is EXPSPACE-complete [26 , 29 ] .
Undecidability in the general case
We shall see in this section that without any restrictions, Reach and Synchro are undecidable. To obtain this result we provide a reduction from FixReach[1 ] with a single process.
The main issue to simulate the execution of a single process is that, in the parameterized case, we have to ensure that the executions of different processes ’match’ the execution of the single one. This is due to the fact that we cannot isolate a specific process.
We present now the key ideas behind our reduction. Let P r = ( Q , 2 , q i n , q f , E ) \mathrm{Pr} = (Q, 2, q_{\mathrm{in}}, q_f, E) Pr = ( Q , 2 , q in , q f , E ) be a counter protocol equipped with two counters. We assume that E = { e 1 , … , e m } E = \{e_1,\ldots,e_m\} E = { e 1 , … , e m } . From P r \mathrm{Pr} Pr we build another protocol P r ′ = ( Q ′ , 4 + m , q i n ′ , q f , E ′ ) \mathrm{Pr}' = (Q', 4+m, q'_{\mathrm{in}}, q_f, E') Pr ′ = ( Q ′ , 4 + m , q in ′ , q f , E ′ ) . It is equipped with as many counters as edges in P r \mathrm{Pr} Pr and with four more counters. The set of states Q Q Q of P r \mathrm{Pr} Pr is included in Q ′ Q' Q ′ which contains other auxiliary states depicted on the next figures. The set E ′ E' E ′ is the smallest set containing the following edges: for each transition e i ∈ E e_i \in E e i ∈ E , we have the transitions described by Figure 2 in E ′ E' E ′ and furthermore we have the edges provided by Figure 3 .
Figure 2. Encoding an edge of Pr
Figure 3. Edges of Pr′ for the initialization
To simulate the execution of P r \mathrm{Pr} Pr with a single processes by many processes following P r ′ \mathrm{Pr}' Pr ′ , we have two phases, an initialization phase and a simulation phase. We recall that in an initial configuration, all counters values are equal to 0. During the initialization phase, the processes are in the part of P r ′ \mathrm{Pr}' Pr ′ described by Figure 3 where they consecutively increment for each edge e i e_i e i the ( 4 + i ) t h (4+i)^{\mathrm{th}} ( 4 + i ) th counter associated to it. In this initialization phase, the value of the ( 4 + i ) t h (4+i)^{\mathrm{th}} ( 4 + i ) th counter is equal to the number of processes that have been through the control state q i q_i q i . At the end of this sequence, the transitions ( q m , zero ( 3 ) , q ′ ) (q_m,\operatorname{zero}(3),q') ( q m , zero ( 3 ) , q ′ ) and ( q ′ , inc ( 3 ) , q i n ) (q',\operatorname{inc}(3),q_{\mathrm{in}}) ( q ′ , inc ( 3 ) , q in ) are here to ensure some sort of synchronization. Indeed as soon as a process goes in q i n q_{\mathrm{in}} q in all the other processes that are not in q ′ q' q ′ will not be able to go into the part of the protocol simulating the behavior of P r \mathrm{Pr} Pr .
During the simulation phase, each process in q ′ q' q ′ or q i n q_{\mathrm{in}} q in has to simulate the same transitions of P r \mathrm{Pr} Pr at the same time; this is ensured by the gadget present at the beginning of the sequences presented in Figure 2 . To take these sequences of edges, the ( 4 + i ) t h (4+i)^{\mathrm{th}} ( 4 + i ) th counter associated to edge e i e_i e i should be decremented to 0 but since every process involved in the simulation has incremented it once in the initialization phase, they hence all have to decrement it, test it with 0 and reincrement it again (this is ensured by the use of the fourth counter) and finally agree on the same transition (of course some processes could have incremented these counters and be blocked in the initialization phase, but in that case, the associated transitions cannot be simulated). Then the operation of the simulated edge is performed as many times as there are processes involved in the simulation. As a matter of fact, if there are n n n processes involved in the simulation, if in the actual execution a counter has value v v v , then in the simulation it has value n ∗ v n \ast v n ∗ v but this does not affect the correctness of the simulation as each increment and decrement will be performed n n n times. When the value of the counter is 0 in the simulated execution, it will be 0 as well in the simulation. We see then that a single process can reach q f q_f q f in Pr iff there exists an initial configuration γ i n \gamma_{in} γ in and a final configuration γ f ∈ Γ ∀ f \gamma_f \in\Gamma_{\forall f} γ f ∈ Γ ∀ f such that γ i n → ∗ γ f \gamma_{in} \to^{\ast} \gamma_f γ in → ∗ γ f in P r ′ \mathrm{Pr}' Pr ′ . Since Γ ∀ f ⊆ Γ ∃ f \Gamma_{\forall f} \subseteq\Gamma_{\exists f} Γ ∀ f ⊆ Γ ∃ f and since if a process can reach q f q_f q f in P r ′ \mathrm{Pr}' Pr ′ then there is an execution where they can all reach q f q_f q f this leads to our first result.
Theorem 4. Reach and Synchro are undecidable.
Useful notations
We introduce here notations useful to analyze the behavior of counter protocols and their associated network. Let P r = ( Q , k , q i n , q f , E ) \mathrm{Pr} = (Q, k, q_{in}, q_f, E) Pr = ( Q , k , q in , q f , E ) be a counter protocol. A path P P P in P r \mathrm{Pr} Pr is either the empty sequence ε \varepsilon ε or a finite sequence of edges of the form P = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) … ( q m − 1 , a m , q m ) P = (q_0, a_1, q_1)(q_1, a_2, q_2) \ldots(q_{m-1}, a_m, q_m) P = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) … ( q m − 1 , a m , q m ) such that ( q i , a i , q i + 1 ) ∈ E (q_i, a_i, q_{i+1}) \in E ( q i , a i , q i + 1 ) ∈ E for all i ∈ [ 0 , m − 1 ] i \in[0,m-1] i ∈ [ 0 , m − 1 ] . For such a non-empty path, we denote by l e n ( P ) len(P) l e n ( P ) its length equal to m m m (the length of an empty path will then be 0), by f i r s t ( P ) first(P) f i r s t ( P ) [resp. l a s t ( P ) last(P) l a s t ( P ) ] the first [resp. last] control state q 0 q_0 q 0 [resp. q m q_m q m ] seen on the path and by l a b ( P ) lab(P) l ab ( P ) the finite word of actions a 1 a 2 … a m a_1a_2 \ldots a_m a 1 a 2 … a m belonging to A c t C o u n t ( k ) ∗ \mathit{ActCount}(k)^{\ast} ActCount ( k ) ∗ . As for runs, we can concatenate two non-empty paths P P P and P ′ P' P ′ to obtain a path P . P ′ P.P' P . P ′ whenever l a s t ( P ) = f i r s t ( P ′ ) last(P) = first(P') l a s t ( P ) = f i r s t ( P ′ ) (we assume as well P = ε . P = P . ε P = \varepsilon.P = P.\varepsilon P = ε . P = P . ε ). The value v a l c ( P ) val_c(P) v a l c ( P ) for a counter c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] of such a non-empty path P P P is an integer equal to ∣ { i ∈ [ 1 , m ] ∣ a i = i n c ( c ) } ∣ − ∣ { i ∈ [ 1 , m ] ∣ a i = d e c ( c ) } ∣ |\{i \in[1,m] \mid a_i = inc(c)\}| - |\{i \in[1,m] \mid a_i = dec(c)\}| ∣ { i ∈ [ 1 , m ] ∣ a i = in c ( c )} ∣ − ∣ { i ∈ [ 1 , m ] ∣ a i = d ec ( c )} ∣ (note that this value can be negative). A non-empty path is initial [resp. final] whenever f i r s t ( P ) = q i n first(P) = q_{in} f i r s t ( P ) = q in [resp. l a s t ( P ) = q f last(P) = q_f l a s t ( P ) = q f ].
Given a n n n -process run ρ : = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho:= \gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell ρ := γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ , for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] , we use p a t h ( p ) ( ρ ) path^{(p)}(\rho) p a t h ( p ) ( ρ ) to denote the path followed by process p p p in ρ \rho ρ . It can be formally defined as follows: it corresponds to the sequence e i 1 ⋯ e i k ∈ E ∗ e_{i_1} \cdots e_{i_k} \in E^{\ast} e i 1 ⋯ e i k ∈ E ∗ such that i 1 , … , i k ∈ [ 1 , ℓ ] i_1,\ldots,i_k \in[1,\ell] i 1 , … , i k ∈ [ 1 , ℓ ] and p i j = p p_{i_j} = p p i j = p for all j ∈ [ 1 , k ] j \in[1,k] j ∈ [ 1 , k ] and i j < i j ′ i_j < i_{j'} i j < i j ′ iff j < j ′ j < j' j < j ′ for all j , j ′ ∈ [ 1 , ℓ ] j,j' \in[1,\ell] j , j ′ ∈ [ 1 , ℓ ] and for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] , if p i = p p_i = p p i = p then there exists j ∈ [ 1 , k ] j \in[1,k] j ∈ [ 1 , k ] such that i j = i i_j = i i j = i . Note that if p i ≠ p p_i \ne p p i = p for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] , then p a t h ( p ) ( ρ ) = ε path^{(p)}(\rho) = \varepsilon p a t h ( p ) ( ρ ) = ε . A non-empty path P P P is said to be feasible with 1 process iff there exists a 1-process run ρ \rho ρ such that f i r s t ( ρ ) = ( [ f i r s t ( P ) ] , 0 ) first(\rho) = ([first(P)],0) f i r s t ( ρ ) = ([ f i r s t ( P )] , 0 ) and p a t h ( 1 ) ( ρ ) = P path^{(1)}(\rho) = P p a t h ( 1 ) ( ρ ) = P .
Solving Reach in some restricted cases
In this section, we shall see that when the considered counter protocols are zero-test free, then Reach can be solved in polynomial time and when these tests are allowed but the protocol manipulates a single counter then Reach is an NL-complete problem.
When zero-tests are not allowed
We begin with the easiest case where we consider a zero-test free counter protocol P r = ( Q , k , q i n , q f , E ) \mathrm{Pr} = (Q,k,q_{in},q_f,E) Pr = ( Q , k , q in , q f , E ) . Our method to solve Reach in this case is based on the following observations: first if a counter can reach a strictly positive value at some point then by repeating this run, we can make the value grow as high as we want and second, higher counter values allow to reach more states, since there are no zero-tests.
To formalize these intuitions, for a subset of counters C ⊆ [ 1 , k ] C \subseteq[1,k] C ⊆ [ 1 , k ] , we denote by Pr ∖ C \operatorname{Pr}_{\setminus C} Pr ∖ C the counter protocol ( Q , k , q i n , q f , E ′ ) (Q,k,q_{\mathrm{in}},q_f,E') ( Q , k , q in , q f , E ′ ) such that E ′ E' E ′ is the smallest set verifying:
if ( q , a , q ′ ) ∈ E (q,a,q') \in E ( q , a , q ′ ) ∈ E and a ∉ { inc ( c ) , dec ( c ) ∣ c ∈ C } a \notin\{\operatorname{inc}(c),\operatorname{dec}(c) \mid c \in C\} a ∈ / { inc ( c ) , dec ( c ) ∣ c ∈ C } then ( q , a , q ′ ) ∈ E ′ (q,a,q') \in E' ( q , a , q ′ ) ∈ E ′ , and,
if ( q , a , q ′ ) ∈ E (q,a,q') \in E ( q , a , q ′ ) ∈ E and a ∈ { inc ( c ) , dec ( c ) ∣ c ∈ C } a \in\{\operatorname{inc}(c),\operatorname{dec}(c) \mid c \in C\} a ∈ { inc ( c ) , dec ( c ) ∣ c ∈ C } then ( q , τ , q ′ ) ∈ E ′ (q,\tau,q') \in E' ( q , τ , q ′ ) ∈ E ′ .
In other words, to obtain Pr ∖ C \operatorname{Pr}_{\setminus C} Pr ∖ C from Pr \operatorname{Pr} Pr , we replace all updates on counters belonging to C C C by some silent actions. We have then the following lemma which is at the heart of our decision procedure for Reach in this specific case.
Lemma 6. q f q_f q f is existentially reachable by Pr \operatorname{Pr} Pr if and only if:
Either there exists a non-empty initial and final path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) is in τ ∗ \tau^* τ ∗ ,
Or, there exists an initial path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) belongs to τ ∗ inc ( c ) \tau^*\operatorname{inc}(c) τ ∗ inc ( c ) for some c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] and q f q_f q f is existentially reachable in Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } .
Proof. Fist assume q f q_f q f is existentially reachable in Pr \operatorname{Pr} Pr . We proceed by a case analysis.
If there does not exist a path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) belongs to τ ∗ inc ( c ) \tau^*\operatorname{inc}(c) τ ∗ inc ( c ) for some c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] , it means that in any run for any counters the first action on counter performed by any process is a decrement, but this is not possible (since in the initial configurations, the initial values of the counters are 0). So since q f q_f q f is existentially reachable in Pr \operatorname{Pr} Pr it means that there is a process following a path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) belongs to τ ∗ \tau^* τ ∗ and last ( P ) = q f \operatorname{last}(P)=q_f last ( P ) = q f .
Assume there exists a path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) belongs to τ ∗ inc ( c ) \tau^*\operatorname{inc}(c) τ ∗ inc ( c ) for some c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] . Then q f q_f q f is existentially reachable in Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } because all runs that are possible in Pr \operatorname{Pr} Pr are as well feasible in Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } by ignoring counters c c c (in this latter protocol we have indeed substituted some actions on counter c c c by τ \tau τ ).
Now assume there exists a non-empty path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) is in τ ∗ \tau^* τ ∗ and last ( P ) = q f \operatorname{last}(P)=q_f last ( P ) = q f , then it is clear that P P P is feasible with 1 process. Hence q f q_f q f is existentially reachable in Pr \operatorname{Pr} Pr .
Finally assume that there exists a path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) belongs to τ ∗ inc ( c ) \tau^*\operatorname{inc}(c) τ ∗ inc ( c ) for some c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] and q f q_f q f is existentially reachable in Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } . It means that there exists a run in Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } of the form: ρ : = ( s 0 , v 0 ) → p 1 , e 1 ( s 1 , v 1 ) → p 2 , e 2 ( s 2 , v 2 ) ⋯ → p n , e n ( s n , v n ) \rho:= (s_0,v_0) \xrightarrow{p_1,e_1} (s_1,v_1) \xrightarrow{p_2,e_2} (s_2,v_2) \cdots\xrightarrow{p_n,e_n} (s_n,v_n) ρ := ( s 0 , v 0 ) p 1 , e 1 ( s 1 , v 1 ) p 2 , e 2 ( s 2 , v 2 ) ⋯ p n , e n ( s n , v n ) where v 0 = 0 v_0=0 v 0 = 0 with s 0 [ p ] = q i n s_0[p]=q_{\mathrm{in}} s 0 [ p ] = q in for all 0 < p ≤ ∥ ( s 0 , v 0 ) ∥ 0 < p \leq\lVert(s_0,v_0)\rVert 0 < p ≤ ∥( s 0 , v 0 )∥ and such that there exists 0 < p ≤ ∥ ( s n , v n ) ∥ 0 < p \leq\lVert(s_n,v_n)\rVert 0 < p ≤ ∥( s n , v n )∥ verifying s n [ p ] = q f s_n[p]=q_f s n [ p ] = q f . When building Pr ∖ { c } \operatorname{Pr}_{\setminus\{c\}} Pr ∖ { c } from Pr \operatorname{Pr} Pr , each action on the counter c c c has been replaced by the action τ \tau τ , we hence deduce that from ρ \rho ρ we can build a run of Pr \operatorname{Pr} Pr which behaves similarly on all the counters except c c c and where at most n n n decrements on the counter c c c has been performed. As a matter of fact, we know that there exists a run in Pr \operatorname{Pr} Pr of the form: ρ ′ : = ( s 0 , v 0 ′ ) → p 1 , e 1 ′ ( s 1 , v 1 ′ ) → p 2 , e 2 ′ ( s 2 , v 2 ′ ) ⋯ → p n , e n ′ ( s n , v n ′ ) \rho' := (s_0,v'_0) \xrightarrow{p_1,e'_1} (s_1,v'_1) \xrightarrow{p_2,e'_2} (s_2,v'_2) \cdots\xrightarrow{p_n,e'_n} (s_n,v'_n) ρ ′ := ( s 0 , v 0 ′ ) p 1 , e 1 ′ ( s 1 , v 1 ′ ) p 2 , e 2 ′ ( s 2 , v 2 ′ ) ⋯ p n , e n ′ ( s n , v n ′ ) where v 0 ′ [ c ] = n v'_0[c]=n v 0 ′ [ c ] = n and for all i ∈ [ 1 , n ] i \in[1,n] i ∈ [ 1 , n ] we have:
v i ′ [ c ′ ] = v i [ c ′ ] v'_i[c']=v_i[c'] v i ′ [ c ′ ] = v i [ c ′ ] for all c ′ ∈ [ 1 , k ] ∖ { c } c' \in[1,k]\setminus\{c\} c ′ ∈ [ 1 , k ] ∖ { c } ;
e i ′ = e i e'_i=e_i e i ′ = e i if e i e_i e i is an edge of Pr \operatorname{Pr} Pr and e i ′ ∈ { ( q , a , q ′ ) ∈ E ∣ a ∈ { inc ( c ) , dec ( c ) ∣ c ∈ C } } e'_i \in\{(q,a,q') \in E \mid a \in\{\operatorname{inc}(c),\operatorname{dec}(c) \mid c \in C\}\} e i ′ ∈ {( q , a , q ′ ) ∈ E ∣ a ∈ { inc ( c ) , dec ( c ) ∣ c ∈ C }} otherwise.
Since there exists a path P P P in Pr \operatorname{Pr} Pr of the form ( q 0 , τ , q 1 ) ( q 1 , τ , q 2 ) ⋯ ( q m − 1 , inc ( c ) , q m ) (q_0,\tau,q_1)(q_1,\tau,q_2)\cdots(q_{m-1},\operatorname{inc}(c),q_m) ( q 0 , τ , q 1 ) ( q 1 , τ , q 2 ) ⋯ ( q m − 1 , inc ( c ) , q m ) , we will complete ρ ′ \rho' ρ ′ at the beginning by introducing n n n new processes all following the path P P P . This introductory step allows us to reach the configuration ( s 0 ′ , v 0 ′ ) (s'_0,v'_0) ( s 0 ′ , v 0 ′ ) such that ∥ ( s 0 ′ , v 0 ′ ) ∥ = N + n \lVert(s'_0,v'_0)\rVert=N+n ∥( s 0 ′ , v 0 ′ )∥ = N + n where N = ∥ ( s 0 , v 0 ′ ) ∥ N=\lVert(s_0,v'_0)\rVert N = ∥( s 0 , v 0 ′ )∥ and for all p ∈ [ 1 , N ] p\in[1,N] p ∈ [ 1 , N ] we have s 0 ′ [ p ] = q i n s'_0[p]=q_{\mathrm{in}} s 0 ′ [ p ] = q in (the N N N first processes did not move) and for all p ∈ [ N + 1 , N + n ] p\in[N+1,N+n] p ∈ [ N + 1 , N + n ] , we have s 0 ′ [ p ] = q m s'_0[p]=q_m s 0 ′ [ p ] = q m . From this configuration, following the same actions as of ρ ′ \rho' ρ ′ (where the n n n last processes will not play any role) we can reach the configuration ( s , v n ′ ) (s,v'_n) ( s , v n ′ ) where for all p ∈ [ 1 , N ] p\in[1,N] p ∈ [ 1 , N ] we have s [ p ] = s n [ p ] s[p]=s_n[p] s [ p ] = s n [ p ] and for all p ∈ [ N + 1 , N + n ] p\in[N+1,N+n] p ∈ [ N + 1 , N + n ] , we have s ′ [ p ] = q m s'[p]=q_m s ′ [ p ] = q m (the n n n last processes did not move in these other runs). Since q f q_f q f appears in s n s_n s n we conclude that q f q_f q f is existentially reachable in Pr \operatorname{Pr} Pr .
This last lemma allows us to design a decision procedure to solve R e a c h \mathsf{Reach} Reach . We begin with the zero-test free counter protocol P r = ( Q , k , q i n , q f , E ) \mathsf{Pr} = (Q,k,q_{\mathit{in}},q_f,E) Pr = ( Q , k , q in , q f , E ) . If there is a path P P P in P r \mathsf{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) is in τ ∗ \tau^* τ ∗ and l a s t ( ρ ) = q f last(\rho) = q_f l a s t ( ρ ) = q f , we stop and return a positive answer to the problem. Otherwise we seek for a counter c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] for which there exists a path P P P in P r \mathsf{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) belongs to τ ∗ i n c ( c ) \tau^*\mathit{inc}(c) τ ∗ inc ( c ) , if this is the case, we reinitiate the procedure with the counter-protocol P r ∖ { c } \mathsf{Pr}_{\setminus\{c\}} Pr ∖ { c } otherwise we return a negative answer to the problem.
Lemma 6 guarantees the correctness of this procedure and since at each step if we do not return a positive answer we delete some actions of a counter c c c , we conclude that we will loop in this procedure at most k k k times. Hence this algorithm will terminate. Finally, each path search can be done in non-logarithmic space in the size of the protocol (it corresponds to some reachability query on a graph). Consequently we obtain a polynomial time upper bound for R e a c h \mathsf{Reach} Reach restricted to zero-test free counter protocols.
We furthermore provide a reduction from the Circuit Value Problem, which is Ptime-complete [22 ] , to obtain a matching lower bound. This latter problem consists in determining the value of an output signal in an acyclic boolean circuit when the input values are given. The idea behind the reduction is to use two counters for each value name (or signal) in the circuit, such that if the first [resp. second] counter, called ⊤ \top ⊤ -counter [resp. ⊥ \perp ⊥ -counter], is strictly positive, then the signal is evaluated to true [resp. false]. It is then easy to encode the behavior of boolean gates. For instance, to simulate an or signal, if we can decrement one of the two ⊤ \top ⊤ -counters associated to the input signals, then we increment the ⊤ \top ⊤ -counter associated to the output and if we can decrement the two ⊥ \perp ⊥ -counter associated to the inputs, then we increment the ⊥ \perp ⊥ -counter of the output. Our reduction guarantees that the two counters associated to a signal are never both strictly positive. Note that in this reduction, it does not harm that we have many processes simulating the circuit, as their actions on the different counters will not change the set of counters having a strictly positive value.
As a consequence, we get the following result.
Theorem 7. R e a c h \mathsf{Reach} Reach restricted to zero-test free counter protocols is Ptime-complete.
Proof. We show that R e a c h \mathsf{Reach} Reach restricted to zero-test free counter protocols is Ptime-hard providing a reduction from CVP, the Circuit Value Problem, which is known to be Ptime-complete [22 ] . This latter problem consists in determining the value of an output signal in an acyclic boolean circuit when the input values are given. An instance of CVP can be defined as a tuple ( V N , G ) (VN,G) ( V N , G ) where V N VN V N is the finite ordered set of value names of form { V 1 , V 2 , V 3 , … , V n } \{V_1,V_2,V_3,\ldots,V_n\} { V 1 , V 2 , V 3 , … , V n } and G G G is a total function which assigns to each value name a value or a boolean combination of previous values; formally for all i ∈ [ 1 , n ] i \in[1,n] i ∈ [ 1 , n ] , we have either G ( V i ) ∈ { ⊤ , ⊥ } G(V_i) \in\{\top,\perp\} G ( V i ) ∈ { ⊤ , ⊥ } , or G ( V i ) = ¬ V j G(V_i) = \neg V_j G ( V i ) = ¬ V j with j < i j < i j < i or G ( V i ) = V j ∨ V k G(V_i) = V_j \lor V_k G ( V i ) = V j ∨ V k with j < i j < i j < i and k < i k < i k < i or G ( V i ) = V j ∧ V k G(V_i) = V_j \land V_k G ( V i ) = V j ∧ V k with j < i j < i j < i and k < i k < i k < i . And the CVP asks then to determine whether V n V_n V n has a value true (⊤ \top ⊤ ) following the respective boolean combinations in the circuit.
Let ( V N , G ) (VN,G) ( V N , G ) be an instance of CVP with V N = { V 1 , V 2 , V 3 , … , V n } VN = \{V_1,V_2,V_3,\ldots,V_n\} V N = { V 1 , V 2 , V 3 , … , V n } . From this we build a zero-test free counter protocol P r = ( Q , 2 n , q i n , q f , E ) \mathsf{Pr} = (Q,2n,q_{\mathit{in}},q_f,E) Pr = ( Q , 2 n , q in , q f , E ) with 2 n 2n 2 n counters and where the set Q Q Q and E E E will be described later. Intuitively, for each value name V i V_i V i the i t h i^{\mathrm{th}} i th [resp. the ( n + i ) t h (n+i)^{\mathrm{th}} ( n + i ) th ] counter will be assigned a strictly positive value iff V i V_i V i will be assigned to true [resp. false]. For each V i V_i V i , we have the following set of edges in E E E :
If G ( V i ) = ⊤ G(V_i) = \top G ( V i ) = ⊤ then we have the edge ( q i n , i n c ( i ) , q i ) (q_{\mathit{in}},\mathit{inc}(i),q_i) ( q in , inc ( i ) , q i ) in E E E .
If G ( V i ) = ⊥ G(V_i) = \perp G ( V i ) =⊥ then we have the edge ( q i n , i n c ( n + i ) , q i ) (q_{\mathit{in}},\mathit{inc}(n+i),q_i) ( q in , inc ( n + i ) , q i ) in E E E .
If G ( V i ) = ¬ V j G(V_i) = \neg V_j G ( V i ) = ¬ V j then we have the following edges in E E E : ( q i n , d e c ( j ) , q i ′ ) (q_{\mathit{in}},\mathit{dec}(j),q'_i) ( q in , dec ( j ) , q i ′ ) , ( q i ′ , i n c ( n + j ) , q i ) (q'_i,\mathit{inc}(n+j),q_i) ( q i ′ , inc ( n + j ) , q i ) (these two edges correspond to V j V_j V j having true as a value and hence V i V_i V i should be set to false), ( q i n , d e c ( n + j ) , q i ′ ′ ) (q_{\mathit{in}},\mathit{dec}(n+j),q''_i) ( q in , dec ( n + j ) , q i ′′ ) , ( q i ′ ′ , i n c ( i ) , q i ) (q''_i,\mathit{inc}(i),q_i) ( q i ′′ , inc ( i ) , q i ) (these two edges correspond to V j V_j V j having false as a value and hence V i V_i V i should be set to true).
If G ( V i ) = V j ∧ V k G(V_i)=V_j\land V_k G ( V i ) = V j ∧ V k then we have the following edges in E E E : ( q i n , dec ( n + j ) , q i ′ ) , ( q i n , dec ( n + k ) , q i ′ ) , ( q i ′ , inc ( n + i ) , q i ) (q_{\mathrm{in}},\operatorname{dec}(n+j),q'_i),(q_{\mathrm{in}},\operatorname{dec}(n+k),q'_i),(q'_i,\operatorname{inc}(n+i),q_i) ( q in , dec ( n + j ) , q i ′ ) , ( q in , dec ( n + k ) , q i ′ ) , ( q i ′ , inc ( n + i ) , q i ) (these last three edges match the case where V j V_j V j or V k V_k V k are assigned to false, then so V i V_i V i is assigned to false too), ( q i n , dec ( j ) , q i ′ ′ ) , ( q i ′ ′ , dec ( k ) , q i ′ ′ ′ ) , ( q i ′ ′ ′ , inc ( i ) , q i ) (q_{\mathrm{in}},\operatorname{dec}(j),q''_i),(q''_i,\operatorname{dec}(k),q'''_i),(q'''_i,\operatorname{inc}(i),q_i) ( q in , dec ( j ) , q i ′′ ) , ( q i ′′ , dec ( k ) , q i ′′′ ) , ( q i ′′′ , inc ( i ) , q i ) (these last three edges deal with the case where V j V_j V j and V k V_k V k are assigned to true).
If G ( V i ) = V j ∨ V k G(V_i)=V_j\lor V_k G ( V i ) = V j ∨ V k then we have the following edges in E E E : ( q i n , dec ( j ) , q i ′ ) , ( q i n , dec ( k ) , q i ′ ) , ( q i ′ , inc ( i ) , q i ) (q_{\mathrm{in}},\operatorname{dec}(j),q'_i),(q_{\mathrm{in}},\operatorname{dec}(k),q'_i),(q'_i,\operatorname{inc}(i),q_i) ( q in , dec ( j ) , q i ′ ) , ( q in , dec ( k ) , q i ′ ) , ( q i ′ , inc ( i ) , q i ) (these last three edges match the case where V j V_j V j or V k V_k V k are assigned to true, then V i V_i V i is assigned to true too), ( q i n , dec ( n + j ) , q i ′ ′ ) , ( q i ′ ′ , dec ( n + k ) , q i ′ ′ ′ ) , ( q i ′ ′ ′ , inc ( n + i ) , q i ) (q_{\mathrm{in}},\operatorname{dec}(n+j),q''_i),(q''_i,\operatorname{dec}(n+k),q'''_i),(q'''_i,\operatorname{inc}(n+i),q_i) ( q in , dec ( n + j ) , q i ′′ ) , ( q i ′′ , dec ( n + k ) , q i ′′′ ) , ( q i ′′′ , inc ( n + i ) , q i ) (these last three edges deal with the case where V j V_j V j and V k V_k V k are assigned to true).
And we have as well in E E E a last edge of the form ( q i n , dec ( n ) , q f ) (q_{\mathrm{in}},\operatorname{dec}(n),q_f) ( q in , dec ( n ) , q f ) which can be taken only when the n t h n^{\mathrm{th}} n th counter has a strictly positive value. The key behind this reduction lies in the fact that since the circuit indeed is acyclic, each time some process takes a sequence of edges to evaluate a value name V i V_i V i , it will always take the same sequence and finally increase the same associated counter (the i i i -th or the n + i n+i n + i -th one). We will finally have that the value name V n V_n V n is assigned to true in the circuit iff there exists an initial configuration γ i n \gamma_{\mathrm{in}} γ in (where all the counters are initially set to 0 0 0 ) and a configuration γ f ∈ Γ ∃ f \gamma_f\in\Gamma_{\exists f} γ f ∈ Γ ∃ f (where at least one process is in q f q_f q f ) such that γ i n → ∗ γ f \gamma_{\mathrm{in}}\to^*\gamma_f γ in → ∗ γ f (meaning that since the only edge leading to q f q_f q f is ( q i n , dec ( n ) , q f ) (q_{\mathrm{in}},\operatorname{dec}(n),q_f) ( q in , dec ( n ) , q f ) , then at some point the n t h n^{\mathrm{th}} n th counter has been increased).
Note that we could have obtained the upper bound thanks to Theorem 18 , which shows that Synchro restricted to zero-test free counter protocols is in Ptime. We can indeed reduce, in that case, Reach to Synchro (adding a counter that is increased when the final state is reached and transitions from all the other states to the final state decreasing this counter). However, our proof technique provided an NL upper bound when the number of counters is fixed and is a good warm-up for the rest of the paper.
Authorizing tests over a single counter
We consider here a one-counter protocol P r = ( Q , 1 , q i n , q f , E ) \mathsf{Pr}=(Q,1,q_{\mathrm{in}},q_f,E) Pr = ( Q , 1 , q in , q f , E ) . As for the proof of Theorem 7 , we provide a necessary and sufficient condition for q f q_f q f to be existentially reachable in P r \mathsf{Pr} Pr . We show indeed that if the solution is not trivial, we need an initial and final path P f P_f P f (which will witness the fact that q f q_f q f is reachable) and we need two reachable transitions that can increment and decrement the counter on demand (in order to make the path P f P_f P f feasible).
Lemma 8. q f q_f q f is existentially reachable by P r \mathsf{Pr} Pr if and only if:
Either the answer to FixReach[1 ] is true for P r \mathsf{Pr} Pr ,
Or, the three following conditions are satisfied:
There exists an initial and final path P f P_f P f in P r \mathsf{Pr} Pr ;
There exists an initial path P + P_+ P + in P r \mathsf{Pr} Pr such that lab ( P + ) \operatorname{lab}(P_+) lab ( P + ) belongs to ( τ + zero ) ∗ inc (\tau+\operatorname{zero})^*\operatorname{inc} ( τ + zero ) ∗ inc ;
There exists a transition ( q − , dec , q ′ ) (q_-,\operatorname{dec},q') ( q − , dec , q ′ ) in E E E and an initial 1 1 1 -process run of the form, ( q i n , 0 ) → ∗ ( q − , 0 ) (q_{\mathrm{in}},0)\to^*(q_-,0) ( q in , 0 ) → ∗ ( q − , 0 ) .
Proof. First assume that q f q_f q f is existentially reachable in P r \mathsf{Pr} Pr and the run to reach a configuration exhibiting q f q_f q f needs strictly more than one process (i.e., the answer to FixReach[1 ] is false for P r \mathsf{Pr} Pr ). We have hence a run ρ \rho ρ of the form γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \gamma_0\xrightarrow{p_1,e_1}\gamma_1\xrightarrow{p_2,e_2}\gamma_2\cdots\xrightarrow{p_\ell,e_\ell}\gamma_\ell γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ with γ i = ( s i , v i ) \gamma_i=(s_i,v_i) γ i = ( s i , v i ) for all i ∈ [ 0 , ℓ ] i\in[0,\ell] i ∈ [ 0 , ℓ ] where γ 0 \gamma_0 γ 0 is an initial configuration with n > 1 n>1 n > 1 processes and s ℓ [ 1 ] = q f s_\ell[1]=q_f s ℓ [ 1 ] = q f (we can assume that it is the first process that reaches q f q_f q f ). We prove that the three conditions are satisfied:
By definition of a run and of the transition relation → \to → , we have that path ( 1 ) ( ρ ) \operatorname{path}^{(1)}(\rho) path ( 1 ) ( ρ ) is an initial and final path in P r \mathsf{Pr} Pr .
Since, the answer to FixReach[1 ] is false for Pr, there must be i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] such that l a b ( e i ) = inc lab(e_i)=\operatorname{inc} l ab ( e i ) = inc (otherwise all for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] , we would have l a b ( e i ) ∈ { zero , τ } lab(e_i) \in\{\operatorname{zero},\tau\} l ab ( e i ) ∈ { zero , τ } and the answer to FixReach[1 ] would be true). Let i + i_+ i + be the first index in [ 1 , ℓ ] [1,\ell] [ 1 , ℓ ] such that l a b ( e i + ) = inc lab(e_{i_+})=\operatorname{inc} l ab ( e i + ) = inc . It means that for all 1 ≤ i < i + 1 \leq i < i_+ 1 ≤ i < i + we have necessarily l a b ( e i ) ∈ { zero , τ } lab(e_i) \in\{\operatorname{zero},\tau\} l ab ( e i ) ∈ { zero , τ } as a decrement of the counter cannot happen if no increment have been seen before. As matter of fact, we deduce that if we take the path p a t h ( p i + ) ( ρ ≤ i + ) path^{(p_{i_+})}(\rho_{\leq i_+}) p a t h ( p i + ) ( ρ ≤ i + ) , it corresponds to a path P + P_+ P + such that l a b ( P + ) lab(P_+) l ab ( P + ) belongs to ( τ + zero ) ∗ inc (\tau+\operatorname{zero})^*\operatorname{inc} ( τ + zero ) ∗ inc .
We let k k k be the smallest in [ 1 , ℓ ] [1,\ell] [ 1 , ℓ ] index such that p a t h ( p k ) ( ρ ≤ k ) path^{(p_k)}(\rho_{\leq k}) p a t h ( p k ) ( ρ ≤ k ) is not feasible with 1 process. In that case we have necessarily l a b ( e k ) ∈ { dec , zero } lab(e_k) \in\{\operatorname{dec},\operatorname{zero}\} l ab ( e k ) ∈ { dec , zero } (the other actions over the counter not blocking a run). We have as well that p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) path^{(p_k)}(\rho_{\leq(k-1)}) p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) is feasible with 1 process and that if e k = ( q , a , q ′ ) e_k=(q,a,q') e k = ( q , a , q ′ ) , and if it is not empty we have l a s t ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) = q last(path^{(p_k)}(\rho_{\leq(k-1)}))=q l a s t ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) = q otherwise q = q i n q=q_{\mathrm{in}} q = q in (the path followed by process p k p_k p k before index k k k is feasible and it ends in the state q q q , since the next transition taken by p k p_k p k is ρ \rho ρ will be e k e_k e k ). We treat the two cases:
Case l a b ( e k ) = dec lab(e_k)=\operatorname{dec} l ab ( e k ) = dec : in that case we have that v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) = 0 val_1(path^{(p_k)}(\rho_{\leq(k-1)}))=0 v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) = 0 . Indeed if v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) > 0 val_1(path^{(p_k)}(\rho_{\leq(k-1)}))>0 v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) > 0 then p a t h ( p k ) ( ρ ≤ k ) path^{(p_k)}(\rho_{\leq k}) p a t h ( p k ) ( ρ ≤ k ) would be feasible (since k k k is the smallest index for which the path followed by process p k p_k p k is not feasible and because of the semantics of the action dec) and if v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) < 0 val_1(path^{(p_k)}(\rho_{\leq(k-1)}))<0 v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) < 0 then k k k would not be the smallest index for which the path followed by process p k p_k p k is not feasible. Hence by putting e k = ( q − , dec , q ′ ) e_k=(q_-,\operatorname{dec},q') e k = ( q − , dec , q ′ ) and by taking the run with 1 process ρ ′ \rho' ρ ′ such that p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) = p a t h ( 1 ) ( ρ ′ ) path^{(p_k)}(\rho_{\leq(k-1)})=path^{(1)}(\rho') p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) = p a t h ( 1 ) ( ρ ′ ) and since v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) = 0 val_1(path^{(p_k)}(\rho_{\leq(k-1)}))=0 v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) = 0 , we know that the last configuration of ρ ′ \rho' ρ ′ will be of the form ( q − , 0 ) (q_-,0) ( q − , 0 ) .
Case l a b ( e k ) = zero lab(e_k)=\operatorname{zero} l ab ( e k ) = zero : as we have done for the previous case, we first deduce that v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) ) ) > 0 val_1(path^{(p_k)}(\rho_{\leq(k-1)}))>0 v a l 1 ( p a t h ( p k ) ( ρ ≤ ( k − 1 ) )) > 0 . Note that by definition of the index k k k we have as well that v a l 1 ( p a t h ( p ) ( ρ ≤ ( k − 1 ) ) ) ≥ 0 val_1(path^{(p)}(\rho_{\leq(k-1)}))\geq0 v a l 1 ( p a t h ( p ) ( ρ ≤ ( k − 1 ) )) ≥ 0 for all p ∈ [ 1 , n ] ∖ { k } p \in[1,n]\setminus\{k\} p ∈ [ 1 , n ] ∖ { k } (when a path is feasible, the value of the path is the value obtained by the run following the path and is hence a natural). Furthermore by definition of the semantics, we know as well that if γ k − 1 = ( s k − 1 , v k − 1 ) \gamma_{k-1}=(s_{k-1},v_{k-1}) γ k − 1 = ( s k − 1 , v k − 1 ) then v k − 1 [ 1 ] = ∑ p ∈ [ 1 , n ] v a l 1 ( p a t h ( p ) ( ρ ≤ ( k − 1 ) ) ) v_{k-1}[1]=\sum_{p\in[1,n]}val_1(path^{(p)}(\rho_{\leq(k-1)})) v k − 1 [ 1 ] = ∑ p ∈ [ 1 , n ] v a l 1 ( p a t h ( p ) ( ρ ≤ ( k − 1 ) )) . Consequently, we have v k − 1 [ 1 ] > 0 v_{k-1}[1]>0 v k − 1 [ 1 ] > 0 which is in contradiction with the fact that γ k − 1 → p k , e k γ k \gamma_{k-1}\xrightarrow{p_k,e_k}\gamma_k γ k − 1 p k , e k γ k with l a b ( e k ) = zero lab(e_k)=\operatorname{zero} l ab ( e k ) = zero . Hence we cannot have l a b ( e k ) = zero lab(e_k)=\operatorname{zero} l ab ( e k ) = zero and the only valid case is the previous one.
Assume now that the answer to FixReach[1 ] is true for Pr, then it is clear that q f q_f q f is existentially reachable in Pr. So it remains to check that this last fact is satisfied when the three following conditions are satisfied. We first introduce some notations:
Let P f = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) ⋯ ( q m − 1 , a m , q m ) P_f=(q_0,a_1,q_1)(q_1,a_2,q_2)\cdots(q_{m-1},a_m,q_m) P f = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) ⋯ ( q m − 1 , a m , q m ) be an initial and final path in Pr (hence q m = q f q_m=q_f q m = q f );
Let P + = e + , 1 ⋯ e + , m + P_+=e_{+,1}\cdots e_{+,m_+} P + = e + , 1 ⋯ e + , m + be an initial path such that l a b ( e + , i ) ∈ { τ , zero } lab(e_{+,i})\in\{\tau,\operatorname{zero}\} l ab ( e + , i ) ∈ { τ , zero } for all i ∈ [ 1 , m + ] i\in[1,m_+] i ∈ [ 1 , m + ] and l a b ( e + , m + ) = inc lab(e_{+,m_+})=\operatorname{inc} l ab ( e + , m + ) = inc ;
Let e − = ( q − , dec , q ′ ) e_-=(q_-,\operatorname{dec},q') e − = ( q − , dec , q ′ ) and let ρ − \rho_- ρ − be the initial 1 process run of the form γ 0 ′ → 1 , e − , 1 γ 1 ′ → 1 , e − , 2 γ 2 ′ ⋯ → 1 , e − , m − γ m − ′ \gamma'_0\xrightarrow{1,e_{-,1}}\gamma'_1\xrightarrow{1,e_{-,2}}\gamma'_2\cdots\xrightarrow{1,e_{-,m_-}}\gamma'_{m_-} γ 0 ′ 1 , e − , 1 γ 1 ′ 1 , e − , 2 γ 2 ′ ⋯ 1 , e − , m − γ m − ′ where γ m − = ( q − , 0 ) \gamma_{m_-}=(q_-,0) γ m − = ( q − , 0 )
We shall now see how to build m m m runs ρ 1 , … , ρ m \rho_1,\ldots,\rho_m ρ 1 , … , ρ m involving m + 1 m+1 m + 1 processes such that ρ i \rho_i ρ i will have the form γ i , 0 → p i , 1 , e i , 1 γ i , 1 → p i , 2 , e i , 2 γ i , 2 ⋯ → p i , ℓ i , e i , ℓ i γ i , ℓ i \gamma_{i,0}\xrightarrow{p_{i,1},e_{i,1}}\gamma_{i,1}\xrightarrow{p_{i,2},e_{i,2}}\gamma_{i,2}\cdots\xrightarrow{p_{i,\ell_i},e_{i,\ell_i}}\gamma_{i,\ell_i} γ i , 0 p i , 1 , e i , 1 γ i , 1 p i , 2 , e i , 2 γ i , 2 ⋯ p i , ℓ i , e i , ℓ i γ i , ℓ i for all i ∈ [ 1.. m ] i\in[1..m] i ∈ [ 1.. m ] and such that γ i , ℓ i = γ i + 1 , 0 \gamma_{i,\ell_i}=\gamma_{i+1,0} γ i , ℓ i = γ i + 1 , 0 for all i ∈ [ 1.. m − 1 ] i\in[1..m-1] i ∈ [ 1.. m − 1 ] and γ 1 , 0 \gamma_{1,0} γ 1 , 0 is the initial configuration with m + 1 m+1 m + 1 processes. In other words, we will be able to ‘concatenate’ the m m m runs to obtain an initial run of the form γ 1 , 0 → ∗ γ 1 , ℓ 1 = γ 2 , 0 → ∗ ⋯ → ∗ γ m − 1 , ℓ m − 1 = γ m , 0 → ∗ γ m , ℓ m \gamma_{1,0}\to^*\gamma_{1,\ell_1}=\gamma_{2,0}\to^*\cdots\to^*\gamma_{m-1,\ell_{m-1}}=\gamma_{m,0}\to^*\gamma_{m,\ell_m} γ 1 , 0 → ∗ γ 1 , ℓ 1 = γ 2 , 0 → ∗ ⋯ → ∗ γ m − 1 , ℓ m − 1 = γ m , 0 → ∗ γ m , ℓ m . The shape of each run γ i \gamma_i γ i will be determined by the transition ( q i − 1 , a i , q i ) (q_{i-1},a_i,q_i) ( q i − 1 , a i , q i ) of P f P_f P f . Intuitively the first process will only take this latter transition and the other processes will be here to always set the counter to 0. We will guarantee in our construction that if γ i , 0 = ( s i , 0 , v i , 0 ) \gamma_{i,0}=(s_{i,0},v_{i,0}) γ i , 0 = ( s i , 0 , v i , 0 ) then s i , 0 [ 1 ] = q i − 1 s_{i,0}[1]=q_{i-1} s i , 0 [ 1 ] = q i − 1 and s i , 0 [ p ] = q i n s_{i,0}[p]=q_{\mathrm{in}} s i , 0 [ p ] = q in for all p ∈ [ i + 1 , m + 1 ] p\in[i+1,m+1] p ∈ [ i + 1 , m + 1 ] and v i , 0 = 0 v_{i,0}=0 v i , 0 = 0 and if γ m , ℓ m = ( s m , ℓ m , v m , ℓ m ) \gamma_{m,\ell_m}=(s_{m,\ell_m},v_{m,\ell_m}) γ m , ℓ m = ( s m , ℓ m , v m , ℓ m ) we will have s m , ℓ m [ 1 ] = q m = q f s_{m,\ell_m}[1] = q_m = q_f s m , ℓ m [ 1 ] = q m = q f . Let i ∈ [ 1 , m ] i \in[1,m] i ∈ [ 1 , m ] , the run ρ i \rho_i ρ i has the following form according to a i a_i a i , the action of transition e i = ( q i − 1 , a i , q i ) e_i = (q_{i-1}, a_i, q_i) e i = ( q i − 1 , a i , q i ) :
Case a i = τ a_i = \tau a i = τ : we have then ρ i : = γ i , 0 → 1 , e i γ i , 1 \rho_i := \gamma_{i,0} \xrightarrow{1,e_i} \gamma_{i,1} ρ i := γ i , 0 1 , e i γ i , 1 (since our construction guarantees that γ i , 0 = ( s i , 0 , 0 ) \gamma_{i,0} = (s_{i,0},0) γ i , 0 = ( s i , 0 , 0 ) with s i , 0 [ 1 ] = q i − 1 s_{i,0}[1] = q_{i-1} s i , 0 [ 1 ] = q i − 1 );
Case a i = z e r o a_i = \mathit{zero} a i = zero : we have then ρ i : = γ i , 0 → 1 , e i γ i , 1 \rho_i := \gamma_{i,0} \xrightarrow{1,e_i} \gamma_{i,1} ρ i := γ i , 0 1 , e i γ i , 1 (since our construction guarantees that γ i , 0 = ( s i , 0 , 0 ) \gamma_{i,0} = (s_{i,0},0) γ i , 0 = ( s i , 0 , 0 ) with s i , 0 [ 1 ] = q i − 1 s_{i,0}[1] = q_{i-1} s i , 0 [ 1 ] = q i − 1 , this is possible)
Case a i = i n c a_i = \mathit{inc} a i = inc : we have then ρ i : = γ i , 0 → 1 + i , e − , 1 ⋯ → 1 + i , e − , m − → 1 , e i → 1 + i , e − γ i , m − + 2 \rho_i := \gamma_{i,0} \xrightarrow{1+i,e_{-,1}} \cdots\xrightarrow{1+i,e_{-,m_-}} \xrightarrow{1,e_i} \xrightarrow{1+i,e_-} \gamma_{i,m_-+2} ρ i := γ i , 0 1 + i , e − , 1 ⋯ 1 + i , e − , m − 1 , e i 1 + i , e − γ i , m − + 2 (the ( i + 1 ) (i+1) ( i + 1 ) th process goes to a point where its effect on the counter is 0 0 0 and ends in the state q − q_- q − , the first process does an increment and the ( i + 1 ) (i+1) ( i + 1 ) th process performs a decrement bringing back the counter to 0 0 0 );
Case a i = d e c a_i = \mathit{dec} a i = dec : we have then ρ i : = γ i , 0 → 1 + i , e + , 1 ⋯ → 1 + i , e + , m + γ i , m + → 1 , e i γ i , m + + 1 \rho_i := \gamma_{i,0} \xrightarrow{1+i,e_{+,1}} \cdots\xrightarrow{1+i,e_{+,m_+}} \gamma_{i,m_+} \xrightarrow{1,e_i} \gamma_{i,m_++1} ρ i := γ i , 0 1 + i , e + , 1 ⋯ 1 + i , e + , m + γ i , m + 1 , e i γ i , m + + 1 (the i + 1 i+1 i + 1 th process increments the counter and the first process brings it back to 0 0 0 ).
One can then show that the concatenation of the runs is possible to obtain finally an initial run ending in the configuration ( s m , ℓ m , v m , ℓ m ) (s_{m,\ell_m},v_{m,\ell_m}) ( s m , ℓ m , v m , ℓ m ) with s m , ℓ m [ 1 ] = q f s_{m,\ell_m}[1] = q_f s m , ℓ m [ 1 ] = q f . Consequently q f q_f q f is existentially reachable in P r \mathrm{Pr} Pr . ◀
Each of the conditions expressed by the previous lemma can be checked in non-deterministic logarithmic space, either because they correspond to a reachability query on the graph of the protocol or because we can apply the results of Theorem 3 on one-counter protocols.
Theorem 9. R e a c h \mathit{Reach} Reach restricted to one-counter protocols is NL-complete.
Solving Synchro in some restricted cases
No test and one counter
We will prove here that S y n c h r o \mathit{Synchro} Synchro for zero-test free one-counter protocols can be solved in NL. Again we will rely on some necessary and sufficient conditions on the paths of the considered protocols. In the sequel, we fix a zero-test free one-counter protocol P r = ( Q , 1 , q i n , q f , E ) \mathrm{Pr} = (Q,1,q_{\mathrm{in}},q_f,E) Pr = ( Q , 1 , q in , q f , E ) .
Strictly increasing paths
We say that a path P i n c P_{\mathrm{inc}} P inc of the protocol P r \mathrm{Pr} Pr is strictly increasing iff it is initial, final and val 1 ( P i n c ) > 0 \operatorname{val}_1(P_{\mathrm{inc}}) > 0 val 1 ( P inc ) > 0 . In order to decide in an efficient manner if a protocol has a strictly increasing path, we show that if there exists one, there exists a ’small’ one. To obtain this result, we look at the simple cycles in the original strictly increasing path: all the simple cycles with a negative value can be removed and we can keep the first strictly positive cycle to be repeated enough to reach the final state with a strictly positive value.
Lemma 10. If P r \mathrm{Pr} Pr has a strictly increasing path, then it has one P i n c P_{\mathrm{inc}} P inc such that len ( P i n c ) ≤ 2 ∣ Q ∣ 2 + 2 ∣ Q ∣ \operatorname{len}(P_{\mathrm{inc}}) \le2|Q|^2 + 2|Q| len ( P inc ) ≤ 2∣ Q ∣ 2 + 2∣ Q ∣ .
Proof. Let P i n c P_{\mathrm{inc}} P inc be a strictly increasing path of P r \mathrm{Pr} Pr . First note, that if P i n c = P . P ′ . P ′ ′ P_{\mathrm{inc}} = P.P'.P'' P inc = P . P ′ . P ′′ (with P P P or P ′ ′ P'' P ′′ that could be empty) where last ( P ′ ) = first ( P ′ ) \operatorname{last}(P') = \operatorname{first}(P') last ( P ′ ) = first ( P ′ ) and val 1 ( P ′ ) ≤ 0 \operatorname{val}_1(P') \le0 val 1 ( P ′ ) ≤ 0 then P . P ′ ′ P.P'' P . P ′′ is a strictly increasing path. We can hence assume that there is no such subpath P ′ P' P ′ in P i n c P_{\mathrm{inc}} P inc (they can all be removed). We can now deal with two cases:
There is no path P ′ P' P ′ such that last ( P ′ ) = first ( P ′ ) \operatorname{last}(P') = \operatorname{first}(P') last ( P ′ ) = first ( P ′ ) and P i n c = P . P ′ . P ′ ′ P_{\mathrm{inc}} = P.P'.P'' P inc = P . P ′ . P ′′ . In that case, it means that P i n c P_{\mathrm{inc}} P inc never goes twice through the same state and as a matter of fact len ( P i n c ) ≤ ∣ Q ∣ ≤ 2 ∣ Q ∣ 2 + 2 ∣ Q ∣ \operatorname{len}(P_{\mathrm{inc}}) \le|Q| \le2|Q|^2 + 2|Q| len ( P inc ) ≤ ∣ Q ∣ ≤ 2∣ Q ∣ 2 + 2∣ Q ∣ .
There is a path P ′ P' P ′ such that l a s t ( P ′ ) = f i r s t ( P ′ ) last(P') = first(P') l a s t ( P ′ ) = f i r s t ( P ′ ) and P i n c = P . P ′ . P ′ ′ P_{\mathrm{inc}} = P.P'.P'' P inc = P . P ′ . P ′′ . In that case, assume P i n c = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) … ( q m − 1 , a m , q m ) P_{\mathrm{inc}} = (q_0, a_1, q_1)(q_1, a_2, q_2)\ldots(q_{m-1}, a_m, q_m) P inc = ( q 0 , a 1 , q 1 ) ( q 1 , a 2 , q 2 ) … ( q m − 1 , a m , q m ) and let k k k be the smallest index such there exists ℓ > k \ell> k ℓ > k and q k = q ℓ q_k = q_\ell q k = q ℓ and for all k < i , j ≤ ℓ k < i,j \le\ell k < i , j ≤ ℓ such that i ≠ j i \ne j i = j , we have q i ≠ q j q_i \ne q_j q i = q j . We denote by P b e g P_{\mathrm{beg}} P beg the path ( q 0 , a 1 , q 1 ) … ( q k , a k , q k ) (q_0, a_1, q_1)\ldots(q_k, a_k, q_k) ( q 0 , a 1 , q 1 ) … ( q k , a k , q k ) and by P m i d P_{\mathrm{mid}} P mid the path (which is a simple cycle) ( q k , a k + 1 , q k + 1 ) ( q k + 1 , a k + 2 , q k + 2 ) … ( q ℓ − 1 , a ℓ , q ℓ ) (q_k, a_{k+1}, q_{k+1})(q_{k+1}, a_{k+2}, q_{k+2})\ldots(q_{\ell-1}, a_\ell, q_\ell) ( q k , a k + 1 , q k + 1 ) ( q k + 1 , a k + 2 , q k + 2 ) … ( q ℓ − 1 , a ℓ , q ℓ ) . Note that by definition we have l e n ( P b e g ) ≤ ∣ Q ∣ len(P_{\mathrm{beg}}) \le|Q| l e n ( P beg ) ≤ ∣ Q ∣ and l e n ( P m i d ) ≤ ∣ Q ∣ len(P_{\mathrm{mid}}) \le|Q| l e n ( P mid ) ≤ ∣ Q ∣ and v a l 1 ( P m i d ) > 0 val_1(P_{\mathrm{mid}}) > 0 v a l 1 ( P mid ) > 0 (since we assumed there is no cycle with a negative value in P i n c P_{\mathrm{inc}} P inc ). We consider finally the path P e n d = ( q ℓ , a ℓ , q ℓ + 1 ) ( q ℓ + 1 , a ℓ + 1 , q ℓ + 2 ) … ( q m − 1 , a m , q m ) P_{\mathrm{end}} = (q_\ell, a_\ell, q_{\ell+1})(q_{\ell+1}, a_{\ell+1}, q_{\ell+2})\ldots(q_{m-1}, a_m, q_m) P end = ( q ℓ , a ℓ , q ℓ + 1 ) ( q ℓ + 1 , a ℓ + 1 , q ℓ + 2 ) … ( q m − 1 , a m , q m ) . Note that this is a final path. We can modify it such that it does not contain cycle (i.e., subpath P P P such l a s t ( P ) = f i r s t ( P ) last(P) = first(P) l a s t ( P ) = f i r s t ( P ) ) to obtain another final path P e n d ′ P'_{\mathrm{end}} P end ′ such that f i r s t ( P e n d ′ ) = q ℓ first(P'_{\mathrm{end}}) = q_\ell f i r s t ( P end ′ ) = q ℓ and l e n ( P e n d ′ ) ≤ ∣ Q ∣ len(P'_{\mathrm{end}}) \le|Q| l e n ( P end ′ ) ≤ ∣ Q ∣ . Note that P e n d ′ P'_{\mathrm{end}} P end ′ cannot hence perform more that ∣ Q ∣ |Q| ∣ Q ∣ decrements and consequently v a l 1 ( P e n d ) ≥ − ∣ Q ∣ val_1(P_{\mathrm{end}}) \ge-|Q| v a l 1 ( P end ) ≥ − ∣ Q ∣ . We then build the following path P i n c ′ = P b e g ( P m i d ) 2 ∣ Q ∣ P e n d ′ P'_{\mathrm{inc}} = P_{\mathrm{beg}}(P_{\mathrm{mid}})^{2|Q|}P'_{\mathrm{end}} P inc ′ = P beg ( P mid ) 2∣ Q ∣ P end ′ where ( P m i d ) 2 ∣ Q ∣ (P_{\mathrm{mid}})^{2|Q|} ( P mid ) 2∣ Q ∣ means 2 ∣ Q ∣ 2|Q| 2∣ Q ∣ repetitions of the simple cycle P m i d P_{\mathrm{mid}} P mid . We have then that P i n c ′ P'_{\mathrm{inc}} P inc ′ is an initial and final path. We have that l e n ( P i n c ′ ) ≤ 2 ∣ Q ∣ 2 + 2 ∣ Q ∣ len(P'_{\mathrm{inc}}) \le2|Q|^2 + 2|Q| l e n ( P inc ′ ) ≤ 2∣ Q ∣ 2 + 2∣ Q ∣ . And finally, since l e n ( P b e g ) ≤ ∣ Q ∣ len(P_{\mathrm{beg}}) \le|Q| l e n ( P beg ) ≤ ∣ Q ∣ , we have that v a l 1 ( P b e g ) ≥ − ∣ Q ∣ val_1(P_{\mathrm{beg}}) \ge-|Q| v a l 1 ( P beg ) ≥ − ∣ Q ∣ and since v a l 1 ( P i n c ′ ) = v a l 1 ( P b e g ) + 2 ∣ Q ∣ v a l 1 ( P m i d ) + v a l 1 ( P e n d ′ ) val_1(P'_{\mathrm{inc}}) = val_1(P_{\mathrm{beg}}) + 2|Q|val_1(P_{\mathrm{mid}}) + val_1(P'_{\mathrm{end}}) v a l 1 ( P inc ′ ) = v a l 1 ( P beg ) + 2∣ Q ∣ v a l 1 ( P mid ) + v a l 1 ( P end ′ ) and v a l 1 ( P m i d ) > 0 val_1(P_{\mathrm{mid}}) > 0 v a l 1 ( P mid ) > 0 , we deduce that v a l 1 ( P i n c ′ ) > 0 val_1(P'_{\mathrm{inc}}) > 0 v a l 1 ( P inc ′ ) > 0 .
Hence to decide if P r \mathrm{Pr} Pr has a strictly increasing path, we can rely on a NL-algorithm which stores both the length of the path and its value (both can be stored in logarithmic space) and we obtain the matching lower bound from the reachability problem for directed graphs.
Corollary 11. Deciding the existence of a strictly increasing path in a zero-test free one counter protocol is an NL-complete problem.
The protocol has a strictly increasing path
We begin by providing a condition to solve S y n c h r o \mathrm{Synchro} Synchro for protocols with a strictly increasing path. In this case (if there is no trivial initial and final path labeled by τ ∗ \tau^* τ ∗ ) it suffices to have an initial and final path whose first action on the unique counter is an increment. This condition is enough to solve S y n c h r o \mathrm{Synchro} Synchro , because, we first select many processes (called the helpers) for taking this first increment to obtain a high enough counter value which enables the strictly increasing path, and then we select other processes to repeatedly take the strictly increasing path to obtain a high enough counter value so that all the helpers can reach the final control state.
Lemma 12. Assume P r \mathrm{Pr} Pr has a strictly increasing path, then q f q_f q f is universally reachable by P r \mathrm{Pr} Pr if and only if:
Either there exists an initial and final path P P P in P r \mathrm{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) is in τ ∗ \tau^* τ ∗ and l e n ( P ) ≤ ∣ Q ∣ len(P) \le|Q| l e n ( P ) ≤ ∣ Q ∣ ,
Or, there exists an initial and final path P P P in P r \mathrm{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) belongs to τ ∗ i n c A c t C o u n t ( 1 ) ∗ \tau^*\mathrm{inc}\,\mathrm{ActCount}(1)^* τ ∗ inc ActCount ( 1 ) ∗ and l e n ( P ) ≤ 2 ∣ Q ∣ len(P) \le2|Q| l e n ( P ) ≤ 2∣ Q ∣ .
Proof. First assume q f q_f q f is universally reachable by P r \mathrm{Pr} Pr . It means that there exists an initial n n n -process run ρ : = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho:= \gamma_0 \xrightarrow{p_{1},e_{1}} \gamma_1 \xrightarrow{p_{2},e_{2}} \gamma_2 \cdots\xrightarrow{p_{\ell},e_{\ell}} \gamma_\ell ρ := γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ such that γ ℓ ∈ V f \gamma_\ell\in\mathbb{V}_f γ ℓ ∈ V f . Note that by definition, we have that p a t h ( p ) ( ρ ) path^{(p)}(\rho) p a t h ( p ) ( ρ ) is an initial and final path for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] . Assume furthermore there does not exist a non-empty initial and final path P P P in P r \mathrm{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) is in τ ∗ \tau^* τ ∗ . In that case, the run ρ \rho ρ cannot be composed only of internal actions τ \tau τ and since it is a correct run (and the considered protocol is zero-test free), we deduce that there exists i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] such that e i e_i e i is of the form ( q , i n c , q ′ ) (q,\mathrm{inc},q') ( q , inc , q ′ ) and for all j ∈ [ 1 , i − 1 ] j \in[1,i-1] j ∈ [ 1 , i − 1 ] we have that e j e_j e j is of the form ( q ′ ′ , τ , q ′ ′ ′ ) (q^{\prime\prime},\tau,q^{\prime\prime\prime}) ( q ′′ , τ , q ′′′ ) . As a matter of fact l a b ( p a t h ( p i ) ( ρ ) ) lab(path^{(p_i)}(\rho)) l ab ( p a t h ( p i ) ( ρ )) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^*\operatorname{incActCount}(1)^* τ ∗ incActCount ( 1 ) ∗ .
Note that furthermore we can reduce the size of this path by deleting the cycles before the action performing the first inc ( 1 ) \operatorname{inc}(1) inc ( 1 ) and as well after. This gives us the bound of 2 ∣ Q ∣ 2|Q| 2∣ Q ∣ . Similarly if there exists a non-empty initial and final path P P P in Pr \operatorname{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) is in τ ∗ \tau^* τ ∗ , we can delete all the cycles it takes to obtain a path without cycles of length smaller than ∣ Q ∣ |Q| ∣ Q ∣ .
Assume now that there exists an initial and final path P P P in Pr \operatorname{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) is in τ ∗ \tau^* τ ∗ . Then we can build an initial 1-process execution ρ \rho ρ such that p a t h ( 1 ) ( ρ ) = P path^{(1)}(\rho)=P p a t h ( 1 ) ( ρ ) = P (the single process follows the path P P P performing only internal actions). In that case we have that l a s t ( ρ ) last(\rho) l a s t ( ρ ) belongs to Γ ∀ f \Gamma_{\forall f} Γ ∀ f (the process ends necessarily in q f q_f q f and as a matter of fact q f q_f q f is universally reachable by Pr \operatorname{Pr} Pr ).
Finally, assume there exists an initial and final path P P P in Pr \operatorname{Pr} Pr such that l a b ( P ) lab(P) l ab ( P ) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^*\operatorname{incActCount}(1)^* τ ∗ incActCount ( 1 ) ∗ and l e n ( P ) ≤ 2 ∣ Q ∣ len(P)\leq2|Q| l e n ( P ) ≤ 2∣ Q ∣ . We suppose that P = P ′ ( q , inc , q inc ) P ′ ′ P=P'(q,\operatorname{inc},q_{\operatorname{inc}})P^{\prime\prime} P = P ′ ( q , inc , q inc ) P ′′ where l a b ( P ′ ) lab(P') l ab ( P ′ ) belongs to τ ∗ \tau^* τ ∗ . Remember that we have assumed that Pr \operatorname{Pr} Pr has a strictly increasing path P inc P_{\operatorname{inc}} P inc . Let L inc = l e n ( P inc ) L_{\operatorname{inc}}=len(P_{\operatorname{inc}}) L inc = l e n ( P inc ) . We shall build an initial L inc + 2 ∣ Q ∣ L inc L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}} L inc + 2∣ Q ∣ L inc -process run which ends in a configuration where all the processes are in the final state q f q_f q f . The run begins with a first initial run ρ add \rho_{\operatorname{add}} ρ add where the first L inc L_{\operatorname{inc}} L inc processes follow the path P ′ P' P ′ (which is labeled only by internal actions) and take the transition ( q , inc ( 1 ) , q inc ) (q,\operatorname{inc}(1),q_{\operatorname{inc}}) ( q , inc ( 1 ) , q inc ) . Formally, we have:
f i r s t ( ρ add ) ∈ Γ in first(\rho_{\operatorname{add}})\in\Gamma_{\operatorname{in}} f i r s t ( ρ add ) ∈ Γ in , and,
p a t h ( p ) ( ρ add ) = P ′ ( q , inc , q inc ) path^{(p)}(\rho_{\operatorname{add}})=P'(q,\operatorname{inc},q_{\operatorname{inc}}) p a t h ( p ) ( ρ add ) = P ′ ( q , inc , q inc ) for all p ∈ [ 1 , L inc ] p\in[1,L_{\operatorname{inc}}] p ∈ [ 1 , L inc ] , and,
l a s t ( ρ add ) = ( s add , v add ) last(\rho_{\operatorname{add}})=(s_{\operatorname{add}},v_{\operatorname{add}}) l a s t ( ρ add ) = ( s add , v add ) where s add [ p ] = q inc s_{\operatorname{add}}[p]=q_{\operatorname{inc}} s add [ p ] = q inc for all p ∈ [ 1 , L inc ] p\in[1,L_{\operatorname{inc}}] p ∈ [ 1 , L inc ] and s add [ p ] = q in s_{\operatorname{add}}[p]=q_{\operatorname{in}} s add [ p ] = q in for all p ∈ [ L inc + 1 , L inc + 2 ∣ Q ∣ L inc ] p\in[L_{\operatorname{inc}}+1,L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}}] p ∈ [ L inc + 1 , L inc + 2∣ Q ∣ L inc ] and v add = L inc v_{\operatorname{add}}=L_{\operatorname{inc}} v add = L inc (since the unique operations we have performed on the counter are L inc L_{\operatorname{inc}} L inc increments).
Now knowing that the path P inc P_{\operatorname{inc}} P inc is strictly increasing and that it contains at most L inc L_{\operatorname{inc}} L inc decrements, the value of the counter is high enough to make the 2 ∣ Q ∣ L inc 2|Q|L_{\operatorname{inc}} 2∣ Q ∣ L inc last process follow, one after another the strictly increasing path P inc P_{\operatorname{inc}} P inc . Indeed each time a process follows this path, the reached counter value always remains strictly bigger than L inc L_{\operatorname{inc}} L inc , the path being strictly increasing. This gives rise to a new run ρ inc \rho_{\operatorname{inc}} ρ inc verifying:
f i r s t ( ρ inc ) = ( s add , v add ) first(\rho_{\operatorname{inc}})=(s_{\operatorname{add}},v_{\operatorname{add}}) f i r s t ( ρ inc ) = ( s add , v add ) , and,
p a t h ( p ) ( ρ inc ) = P inc path^{(p)}(\rho_{\operatorname{inc}})=P_{\operatorname{inc}} p a t h ( p ) ( ρ inc ) = P inc for all p ∈ [ L inc + 1 , L inc + 2 ∣ Q ∣ L inc ] p\in[L_{\operatorname{inc}}+1,L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}}] p ∈ [ L inc + 1 , L inc + 2∣ Q ∣ L inc ] , and,
l a s t ( ρ inc ) = ( s inc , v inc ) last(\rho_{\operatorname{inc}})=(s_{\operatorname{inc}},v_{\operatorname{inc}}) l a s t ( ρ inc ) = ( s inc , v inc ) where s inc [ p ] = q inc s_{\operatorname{inc}}[p]=q_{\operatorname{inc}} s inc [ p ] = q inc for all p ∈ [ 1 , L inc ] p\in[1,L_{\operatorname{inc}}] p ∈ [ 1 , L inc ] (theses processes did not move) and s inc [ p ] = q f s_{\operatorname{inc}}[p]=q_f s inc [ p ] = q f for all p ∈ [ L inc + 1 , L inc + 2 ∣ Q ∣ L inc ] p\in[L_{\operatorname{inc}}+1,L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}}] p ∈ [ L inc + 1 , L inc + 2∣ Q ∣ L inc ] (these processes all followed P inc P_{\operatorname{inc}} P inc which is final) and v inc > L inc + 2 ∣ Q ∣ L inc v_{\operatorname{inc}}>L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}} v inc > L inc + 2∣ Q ∣ L inc (the run takes 2 ∣ Q ∣ L inc 2|Q|L_{\operatorname{inc}} 2∣ Q ∣ L inc times the strictly increasing path and begins with counter value equal to L inc L_{\operatorname{inc}} L inc ).
We can now end the path by making the first L inc L_{\operatorname{inc}} L inc processes follow the path P ′ ′ P^{\prime\prime} P ′′ (which ends P P P ). This is possible, since this latter path performs at most 2 ∣ Q ∣ 2|Q| 2∣ Q ∣ decrements (we recall that l e n ( P ) ≤ 2 ∣ Q ∣ len(P)\leq2|Q| l e n ( P ) ≤ 2∣ Q ∣ ). Hence the L inc L_{\operatorname{inc}} L inc processes can follow the path without making the counter go below 0. Formally, we have the run ρ end \rho_{\operatorname{end}} ρ end verifying:
f i r s t ( ρ end ) = ( s inc , v inc ) first(\rho_{\operatorname{end}})=(s_{\operatorname{inc}},v_{\operatorname{inc}}) f i r s t ( ρ end ) = ( s inc , v inc ) , and,
p a t h ( p ) ( ρ end ) = P ′ ′ path^{(p)}(\rho_{\operatorname{end}})=P^{\prime\prime} p a t h ( p ) ( ρ end ) = P ′′ for all p ∈ [ 1 , L inc ] p\in[1,L_{\operatorname{inc}}] p ∈ [ 1 , L inc ] , and,
l a s t ( ρ end ) = ( s end , v end ) last(\rho_{\operatorname{end}})=(s_{\operatorname{end}},v_{\operatorname{end}}) l a s t ( ρ end ) = ( s end , v end ) where s end [ p ] = q f s_{\operatorname{end}}[p]=q_f s end [ p ] = q f for all p ∈ [ 1 , L inc ] ( p\in[1,L_{\operatorname{inc}}] ( p ∈ [ 1 , L inc ] ( P^{\prime\prime}$ is a final path) and s end [ p ] = q f s_{\operatorname{end}}[p]=q_f s end [ p ] = q f for all p ∈ [ L inc + 1 , L inc + 2 ∣ Q ∣ L inc ] p\in[L_{\operatorname{inc}}+1,L_{\operatorname{inc}}+2|Q|L_{\operatorname{inc}}] p ∈ [ L inc + 1 , L inc + 2∣ Q ∣ L inc ] (these processes did not move) and v end ≥ 0 v_{\operatorname{end}}\geq0 v end ≥ 0 .
By setting ρ = ρ add ⋅ ρ inc ⋅ ρ end \rho=\rho_{\operatorname{add}}\cdot\rho_{\operatorname{inc}}\cdot\rho_{\operatorname{end}} ρ = ρ add ⋅ ρ inc ⋅ ρ end , we obtain an initial run where all processes end in state q f q_f q f .
The protocol has no strictly increasing path
We now give a condition to solve Synchro \operatorname{Synchro} Synchro for protocols that do not have a strictly increasing path. In this case (if there is no trivial initial and final path labeled by τ ∗ \tau^* τ ∗ ) it suffices to have two initial and final paths with value 0, one whose first action on the unique counter is an increment and the other one whose last action on the counter is a decrement. This condition is enough to solve Synchro, because, we first select many processes (the incrementers) for taking this first increment to obtain a high enough counter value which enables the path reaching the decrement. Note that since this latter path has value 0, then just before reaching the decrement the path has strictly increased the counter value and we can make as many processes as we want (call the decrementers) follow this path in order to let all the incrementers reach the final state. Finally, the path of the incrementers having as well 0, we show that the decrementers can as well reach the final state. First, we need a technical lemma that states that when there is no strictly increasing path, all the paths followed by processes of an initial run bringing everyone in the final state have value 0.
Lemma 13. Assume Pr has no strictly increasing path. If ρ \rho ρ is an initial n n n -process run such that last ( ρ ) ∈ Γ ∀ f \operatorname{last}(\rho) \in\Gamma_{\forall f} last ( ρ ) ∈ Γ ∀ f , then val 1 ( path ( p ) ( ρ ) ) = 0 \operatorname{val}_{1}(\operatorname{path}^{(p)}(\rho)) = 0 val 1 ( path ( p ) ( ρ )) = 0 for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] and last ( ρ ) = ( s , 0 ) \operatorname{last}(\rho) = (s,0) last ( ρ ) = ( s , 0 ) .
Proof. Let ρ \rho ρ be an initial n n n -process run and let last ( ρ ) = ( s , v ) \operatorname{last}(\rho) = (s,v) last ( ρ ) = ( s , v ) . Since ρ \rho ρ is a run, we have v ≥ 0 v \ge0 v ≥ 0 . Note as well that by definition v = ∑ p ∈ [ 1 , n ] val 1 ( path ( p ) ( ρ ) ) v = \sum_{p \in[1,n]}\operatorname{val}_{1}(\operatorname{path}^{(p)}(\rho)) v = ∑ p ∈ [ 1 , n ] val 1 ( path ( p ) ( ρ )) . As Pr has no strictly increasing path, we know that val 1 ( path ( p ) ( ρ ) ) ≤ 0 \operatorname{val}_{1}(\operatorname{path}^{(p)}(\rho)) \le0 val 1 ( path ( p ) ( ρ )) ≤ 0 for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] . This allows us to deduce that ∑ p ∈ [ 1 , n ] val 1 ( path ( p ) ( ρ ) ) = 0 \sum_{p \in[1,n]}\operatorname{val}_{1}(\operatorname{path}^{(p)}(\rho)) = 0 ∑ p ∈ [ 1 , n ] val 1 ( path ( p ) ( ρ )) = 0 and that val 1 ( path ( p ) ( ρ ) ) = 0 \operatorname{val}_{1}(\operatorname{path}^{(p)}(\rho)) = 0 val 1 ( path ( p ) ( ρ )) = 0 for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] .
We can now state the necessary and sufficient condition for q f q_f q f to be universally reachable in the case Pr has no increasing path.
Lemma 14. Assume Pr has no strictly increasing path, then q f q_f q f is universally reachable by Pr if and only if:
Either there exists an initial and final path P P P in Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) is in τ ∗ \tau^* τ ∗ ,
Or, there exists two initial and final paths P i n c P_{\mathrm{inc}} P inc and P d e c P_{\mathrm{dec}} P dec in Pr such that lab ( P i n c ) \operatorname{lab}(P_{\mathrm{inc}}) lab ( P inc ) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^*\operatorname{incActCount}(1)^* τ ∗ incActCount ( 1 ) ∗ and lab ( P d e c ) \operatorname{lab}(P_{\mathrm{dec}}) lab ( P dec ) belongs to ActCount ( 1 ) ∗ dec τ ∗ \operatorname{ActCount}(1)^*\operatorname{dec}\tau^* ActCount ( 1 ) ∗ dec τ ∗ and val 1 ( P i n c ) = val 1 ( P d e c ) = 0 \operatorname{val}_{1}(P_{\mathrm{inc}}) = \operatorname{val}_{1}(P_{\mathrm{dec}}) = 0 val 1 ( P inc ) = val 1 ( P dec ) = 0 and len ( P i n c ) ≤ 2 ∣ Q ∣ + 1 \operatorname{len}(P_{\mathrm{inc}}) \le2|Q| + 1 len ( P inc ) ≤ 2∣ Q ∣ + 1 and len ( P d e c ) ≤ 2 ∣ Q ∣ + 1 \operatorname{len}(P_{\mathrm{dec}}) \le2|Q| + 1 len ( P dec ) ≤ 2∣ Q ∣ + 1 .
Proof. First assume q f q_f q f is universally reachable by Pr. It means that there exists an initial n n n -process run ρ : = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho:= \gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell ρ := γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ such that γ ℓ ∈ Γ ∀ f \gamma_\ell\in\Gamma_{\forall f} γ ℓ ∈ Γ ∀ f . Note that by definition, we have that path ( p ) ( ρ ) \operatorname{path}^{(p)}(\rho) path ( p ) ( ρ ) is an initial and final path for all p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] . Assume furthermore there does not exist a non-empty initial and final path P P P in Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) is in τ ∗ \tau^* τ ∗ . In that case, the run ρ \rho ρ cannot be only composed of internal actions τ \tau τ and since it is a correct run (and the considered protocol is zero-test free), we deduce that there exists i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] such that e i e_i e i is of the form ( q , inc , q ′ ) (q,\operatorname{inc},q') ( q , inc , q ′ ) and for all j ∈ [ 1 , i − 1 ] j \in[1,i-1] j ∈ [ 1 , i − 1 ] we have that e j e_j e j is of the form ( r , τ , r ′ ) (r,\tau,r') ( r , τ , r ′ ) . We denote by P i n c P_{\mathrm{inc}} P inc the initial and final path path ( p i ) ( ρ ) \operatorname{path}^{(p_i)}(\rho) path ( p i ) ( ρ ) . As a matter of fact lab ( P i n c ) \operatorname{lab}(P_{\mathrm{inc}}) lab ( P inc ) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^*\operatorname{incActCount}(1)^* τ ∗ incActCount ( 1 ) ∗ . Using Lemma 13, we furthermore know that γ ℓ = last ( ρ ) \gamma_\ell= \operatorname{last}(\rho) γ ℓ = last ( ρ ) is of the form ( s , 0 ) (s,0) ( s , 0 ) , this means that the last action performs on the counter in the run ρ \rho ρ (which is not only composed of internal actions) is a decrement, i.e., there exists k ∈ [ 1 , ℓ ] k \in[1,\ell] k ∈ [ 1 , ℓ ] such that e k e_k e k is of the form ( q ′ ′ , dec , q ′ ′ ′ ) (q'',\operatorname{dec},q''') ( q ′′ , dec , q ′′′ ) and for all j ∈ [ k + 1 , ℓ ] j \in[k+1,\ell] j ∈ [ k + 1 , ℓ ] we have that e j e_j e j is of the form ( r , τ , r ′ ) (r,\tau,r') ( r , τ , r ′ ) . We denote by P d e c P_{\mathrm{dec}} P dec the initial and final path path ( p k ) ( ρ ) \operatorname{path}^{(p_k)}(\rho) path ( p k ) ( ρ ) which verifies lab ( P d e c ) \operatorname{lab}(P_{\mathrm{dec}}) lab ( P dec ) belongs to ActCount ( 1 ) ∗ dec τ ∗ \operatorname{ActCount}(1)^*\operatorname{dec}\tau^* ActCount ( 1 ) ∗ dec τ ∗ . Thanks to Lemma 13, we have as well val 1 ( P i n c ) = val 1 ( P d e c ) = 0 \operatorname{val}_{1}(P_{\mathrm{inc}}) = \operatorname{val}_{1}(P_{\mathrm{dec}}) = 0 val 1 ( P inc ) = val 1 ( P dec ) = 0 .
We now prove that we can reduce the lengths of P i n c P_{\mathrm{inc}} P inc and P d e c P_{\mathrm{dec}} P dec to the desired one. Assume P i n c = P 1 ( q , inc , q ′ ) P 2 P_{\mathrm{inc}} = P_1(q,\operatorname{inc},q')P_2 P inc = P 1 ( q , inc , q ′ ) P 2 with lab ( P 1 ) \operatorname{lab}(P_1) lab ( P 1 ) belonging to τ ∗ \tau^* τ ∗ . First note that if the path P 1 P_1 P 1 goes twice through the same state, we can remove the cycle (labeled by internal actions) without changing the value of P i n c P_{\mathrm{inc}} P inc . Hence there exists a path P i n c ′ = P 1 ′ ( q , inc , q ′ ) P 2 P'_{\mathrm{inc}} = P'_1(q,\operatorname{inc},q')P_2 P inc ′ = P 1 ′ ( q , inc , q ′ ) P 2 with len ( P 1 ′ ) < ∣ Q ∣ \operatorname{len}(P'_1) < |Q| len ( P 1 ′ ) < ∣ Q ∣ and lab ( P 1 ′ ) \operatorname{lab}(P'_1) lab ( P 1 ′ ) belongs to τ ∗ \tau^* τ ∗ . Assume now that P 2 = P 2 ′ P 3 ′ P 4 ′ P_2 = P'_2P'_3P'_4 P 2 = P 2 ′ P 3 ′ P 4 ′ with first ( P 3 ′ ) = last ( P 3 ′ ) \operatorname{first}(P'_3) = \operatorname{last}(P'_3) first ( P 3 ′ ) = last ( P 3 ′ ) (i.e., P 3 ′ P'_3 P 3 ′ is a cycle). In that case, we cannot have val 1 ( P 3 ′ ) > 0 \operatorname{val}_{1}(P'_3) > 0 val 1 ( P 3 ′ ) > 0 , otherwise by iterating it a big enough number of times, we could obtain from P i n c ′ P'_{inc} P in c ′ a strictly increasing path. Note that it is as well not possible that val 1 ( P 3 ′ ) < 0 \operatorname{val}_{1}(P'_{3}) < 0 val 1 ( P 3 ′ ) < 0 , because otherwise by removing this cycle from P i n c ′ P'_{inc} P in c ′ (which as value 0) we would get a strictly increasing path. Consequently, val 1 ( P 3 ′ ) = 0 \operatorname{val}_{1}(P'_{3}) = 0 val 1 ( P 3 ′ ) = 0 and we can remove this cycle from P i n c ′ P'_{inc} P in c ′ without changing its value. We can repeat this operation until there is no more repeated states in P 2 P_{2} P 2 , this leads to a path P i n c ′ ′ = P 1 ′ ( q , inc , q ′ ) P 2 ′ ′ P''_{inc} = P'_{1}(q,\operatorname{inc},q')P''_{2} P in c ′′ = P 1 ′ ( q , inc , q ′ ) P 2 ′′ where len ( P 2 ′ ′ ) < ∣ Q ∣ \operatorname{len}(P''_{2}) < |Q| len ( P 2 ′′ ) < ∣ Q ∣ . Consequently P i n c ′ ′ P''_{inc} P in c ′′ is an initial and final path such that lab ( P i n c ′ ′ ) \operatorname{lab}(P''_{inc}) lab ( P in c ′′ ) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^{*}\operatorname{incActCount}(1)^{*} τ ∗ incActCount ( 1 ) ∗ and val 1 ( P i n c ′ ′ ) = 0 \operatorname{val}_{1}(P''_{inc}) = 0 val 1 ( P in c ′′ ) = 0 and len ( P i n c ′ ′ ) ≤ 2 ∣ Q ∣ \operatorname{len}(P''_{inc}) \leq2|Q| len ( P in c ′′ ) ≤ 2∣ Q ∣ . Similarly, from P d e c P_{dec} P d ec , we can build an initial and final path P d e c ′ ′ P''_{dec} P d ec ′′ such that lab ( P d e c ′ ′ ) \operatorname{lab}(P''_{dec}) lab ( P d ec ′′ ) belongs to ActCount ( 1 ) ∗ dec τ ∗ \operatorname{ActCount}(1)^{*}\operatorname{dec}\tau^{*} ActCount ( 1 ) ∗ dec τ ∗ and val 1 ( P d e c ′ ′ ) = 0 \operatorname{val}_{1}(P''_{dec}) = 0 val 1 ( P d ec ′′ ) = 0 and len ( P d e c ′ ′ ) ≤ 2 ∣ Q ∣ \operatorname{len}(P''_{dec}) \leq2|Q| len ( P d ec ′′ ) ≤ 2∣ Q ∣ .
As for the case with a strictly increasing path, if there exists a non-empty initial and final path P P P in Pr \operatorname{Pr} Pr such that lab ( P ) \operatorname{lab}(P) lab ( P ) is in τ ∗ \tau^{*} τ ∗ , then we can build an initial 1 process execution ρ \rho ρ such that path ( 1 ) ( ρ ) = P \operatorname{path}^{(1)}(\rho) = P path ( 1 ) ( ρ ) = P and last ( ρ ) \operatorname{last}(\rho) last ( ρ ) belongs to Γ ∀ f \Gamma_{\forall f} Γ ∀ f .
Finally, assume there exist two initial and final paths P i n c P_{inc} P in c and P d e c P_{dec} P d ec in Pr \operatorname{Pr} Pr such that lab ( P i n c ) \operatorname{lab}(P_{inc}) lab ( P in c ) belongs to τ ∗ incActCount ( 1 ) ∗ \tau^{*}\operatorname{incActCount}(1)^{*} τ ∗ incActCount ( 1 ) ∗ and lab ( P d e c ) \operatorname{lab}(P_{dec}) lab ( P d ec ) belongs to ActCount ( 1 ) ∗ dec τ ∗ \operatorname{ActCount}(1)^{*}\operatorname{dec}\tau^{*} ActCount ( 1 ) ∗ dec τ ∗ and val 1 ( P i n c ) = val 1 ( P d e c ) = 0 \operatorname{val}_{1}(P_{inc}) = \operatorname{val}_{1}(P_{dec}) = 0 val 1 ( P in c ) = val 1 ( P d ec ) = 0 . We suppose that P i n c = P 1 ( q , inc , q i n c ) P 3 P_{inc} = P_{1}(q,\operatorname{inc},q_{inc})P_{3} P in c = P 1 ( q , inc , q in c ) P 3 and that P d e c = P 2 ( q d e c , dec , q ′ ) P 4 P_{dec} = P_{2}(q_{dec},\operatorname{dec},q')P_{4} P d ec = P 2 ( q d ec , dec , q ′ ) P 4 where lab ( P 1 ) \operatorname{lab}(P_{1}) lab ( P 1 ) and lab ( P 4 ) \operatorname{lab}(P_{4}) lab ( P 4 ) belongs to τ ∗ \tau^{*} τ ∗ . Note that since val 1 ( P i n c ) = 0 \operatorname{val}_{1}(P_{inc}) = 0 val 1 ( P in c ) = 0 then val 1 ( P 3 ) = − 1 \operatorname{val}_{1}(P_{3}) = -1 val 1 ( P 3 ) = − 1 and since val 1 ( P d e c ) = 0 \operatorname{val}_{1}(P_{dec}) = 0 val 1 ( P d ec ) = 0 , then val 1 ( P 2 ) = 1 \operatorname{val}_{1}(P_{2}) = 1 val 1 ( P 2 ) = 1 . Let L i n c = len ( P i n c ) L_{inc} = \operatorname{len}(P_{inc}) L in c = len ( P in c ) and L d e c = len ( P d e c ) L_{dec} = \operatorname{len}(P_{dec}) L d ec = len ( P d ec ) . We show how to build an initial L d e c + L i n c L_{dec} + L_{inc} L d ec + L in c -process run which ends in a configuration in Γ ∀ f \Gamma_{\forall f} Γ ∀ f . The run begins with a first initial run ρ i n c \rho_{inc} ρ in c where the first L d e c L_{dec} L d ec follows the path P 1 ( q , inc , q i n c ) P_{1}(q,\operatorname{inc},q_{inc}) P 1 ( q , inc , q in c ) (remember that P 1 P_{1} P 1 is labeled only with internal actions). Formally, we have:
first ( ρ i n c ) ∈ Γ i n \operatorname{first}(\rho_{inc}) \in\Gamma_{in} first ( ρ in c ) ∈ Γ in , and,
path ( p ) ( ρ i n c ) = P 1 ( q , inc , q i n c ) \operatorname{path}^{(p)}(\rho_{inc}) = P_{1}(q,\operatorname{inc},q_{inc}) path ( p ) ( ρ in c ) = P 1 ( q , inc , q in c ) for all p ∈ [ 1 , L d e c ] p \in[1,L_{dec}] p ∈ [ 1 , L d ec ] , and,
last ( ρ i n c ) = ( s i n c , v i n c ) \operatorname{last}(\rho_{inc}) = (s_{inc},v_{inc}) last ( ρ in c ) = ( s in c , v in c ) where s i n c [ p ] = q i n c s_{inc}[p] = q_{inc} s in c [ p ] = q in c for all p ∈ [ 1 , L d e c ] p \in[1,L_{dec}] p ∈ [ 1 , L d ec ] and s i n c [ p ] = q i n s_{inc}[p] = q_{in} s in c [ p ] = q in for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p \in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] and v i n c = L d e c v_{inc} = L_{dec} v in c = L d ec (since the unique operations we have performed on the counter are L d e c L_{dec} L d ec increments).
Now knowing that P 2 P_{2} P 2 is an initial path whose increase strictly the counter value and that performs at most L d e c L_{dec} L d ec decrements, the value of the counter is high enough to make the L i n c L_{inc} L in c last processes follow, one after each other the path P 2 P_{2} P 2 (which ends in state q d e c q_{dec} q d ec ). Indeed each time a process follows this path, the reached counter value always remains strictly bigger than L d e c L_{dec} L d ec . This gives rise to a new run ρ d e c \rho_{dec} ρ d ec verifying:
first ( ρ d e c ) = ( s i n c , v i n c ) \operatorname{first}(\rho_{dec}) = (s_{inc},v_{inc}) first ( ρ d ec ) = ( s in c , v in c ) , and,
path ( p ) ( ρ d e c ) = P 2 \operatorname{path}^{(p)}(\rho_{dec}) = P_{2} path ( p ) ( ρ d ec ) = P 2 for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p \in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] , and,
last ( ρ d e c ) = ( s d e c , v d e c ) \operatorname{last}(\rho_{dec}) = (s_{dec},v_{dec}) last ( ρ d ec ) = ( s d ec , v d ec ) where s d e c [ p ] = q i n c s_{dec}[p] = q_{inc} s d ec [ p ] = q in c for all p ∈ [ 1 , L d e c ] p \in[1,L_{dec}] p ∈ [ 1 , L d ec ] (theses processes did not move) and s d e c [ p ] = q d e c s_{dec}[p] = q_{dec} s d ec [ p ] = q d ec for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p \in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] (these processes all followed P 2 P_{2} P 2 ) and v d e c = L d e c + L i n c v_{dec} = L_{dec} + L_{inc} v d ec = L d ec + L in c (the run takes L i n c L_{inc} L in c times the path P 2 P_{2} P 2 and begins with counter value equal to L d e c L_{dec} L d ec ).
The next step consists in bringing the first L d e c L_{dec} L d ec processes in the final state following P 3 P_{3} P 3 . We know that this path performs at most L i n c L_{inc} L in c decrements and at the end it has decreased the counter value of 1. As before, we can build a third run ρ i n c ′ \rho'_{inc} ρ in c ′ verifying:
first ( ρ i n c ′ ) = ( s d e c , v d e c ) \operatorname{first}(\rho'_{inc}) = (s_{dec},v_{dec}) first ( ρ in c ′ ) = ( s d ec , v d ec ) , and,
path ( p ) ( ρ i n c ′ ) = P 3 \operatorname{path}^{(p)}(\rho'_{inc}) = P_{3} path ( p ) ( ρ in c ′ ) = P 3 for all p ∈ [ 1 , L d e c ] p \in[1,L_{dec}] p ∈ [ 1 , L d ec ] , and,
last ( ρ i n c ′ ) = ( s i n c ′ , v i n c ′ ) \operatorname{last}(\rho'_{inc}) = (s'_{inc},v'_{inc}) last ( ρ in c ′ ) = ( s in c ′ , v in c ′ ) where s i n c ′ [ p ] = q f s'_{inc}[p] = q_{f} s in c ′ [ p ] = q f for all p ∈ [ 1 , L d e c ] p \in[1,L_{dec}] p ∈ [ 1 , L d ec ] (theses processes follow the final path P 3 P_{3} P 3 ) and s i n c ′ [ p ] = q d e c s'_{inc}[p] = q_{dec} s in c ′ [ p ] = q d ec for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p \in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] (these processes did not move) and v i n c ′ = L i n c v'_{inc} = L_{inc} v in c ′ = L in c (the run takes L d e c L_{dec} L d ec times the path P 3 P_{3} P 3 and begins with counter value equal to L d e c + L i n c L_{dec}+L_{inc} L d ec + L in c ).
The last step consists in bringing the last L i n c L_{inc} L in c which are in states q d e c q_{dec} q d ec in the final state following the path ( q d e c , dec , q ′ ) P 4 (q_{dec},\operatorname{dec},q')P_{4} ( q d ec , dec , q ′ ) P 4 , since P 4 P_{4} P 4 consists only of internal actions, it means we need to be able to perform L i n c L_{inc} L in c decrements, which is feasible as the value of the counter in ( s i n c ′ , v i n c ′ ) (s'_{inc},v'_{inc}) ( s in c ′ , v in c ′ ) is L i n c L_{inc} L in c . We hence can build a fourth run ρ d e c ′ \rho'_{dec} ρ d ec ′ verifying:
f i r s t ( ρ d e c ′ ) = ( s i n c ′ , v i n c ′ ) first(\rho'_{dec})=(s'_{inc},v'_{inc}) f i r s t ( ρ d ec ′ ) = ( s in c ′ , v in c ′ ) , and,
p a t h ( p ) ( ρ d e c ′ ) = ( q d e c , d e c , q ′ ) P 4 path^{(p)}(\rho'_{dec})=(q_{dec},dec,q')P_4 p a t h ( p ) ( ρ d ec ′ ) = ( q d ec , d ec , q ′ ) P 4 for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p\in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] , and,
l a s t ( ρ d e c ′ ) = ( s d e c ′ , v d e c ′ ) last(\rho'_{dec})=(s'_{dec},v'_{dec}) l a s t ( ρ d ec ′ ) = ( s d ec ′ , v d ec ′ ) where s d e c ′ [ p ] = q f s'_{dec}[p]=q_f s d ec ′ [ p ] = q f for all p ∈ [ 1 , L d e c ] p\in[1,L_{dec}] p ∈ [ 1 , L d ec ] (theses processes do not move) and s d e c ′ [ p ] = q f s'_{dec}[p]=q_f s d ec ′ [ p ] = q f for all p ∈ [ L d e c + 1 , L d e c + L i n c ] p\in[L_{dec}+1,L_{dec}+L_{inc}] p ∈ [ L d ec + 1 , L d ec + L in c ] (these processes follow the final path ( q d e c , d e c , q ′ ) P 4 (q_{dec},dec,q')P_4 ( q d ec , d ec , q ′ ) P 4 ) and v d e c ′ = 0 v'_{dec}=0 v d ec ′ = 0 (the run takes L i n c L_{inc} L in c times the path ( q d e c , d e c , q ′ ) P 4 (q_{dec},dec,q')P_4 ( q d ec , d ec , q ′ ) P 4 and begins with counter value equal to L i n c L_{inc} L in c ).
By setting ρ = ρ i n c . ρ d e c . ρ i n c ′ . ρ d e c ′ \rho=\rho_{inc}.\rho_{dec}.\rho'_{inc}.\rho'_{dec} ρ = ρ in c . ρ d ec . ρ in c ′ . ρ d ec ′ , we obtain an initial run where all processes end in state q f q_f q f .
Result
Thanks to Corollary 11, we have an NL algorithm to know whether we are in the case where a zero-test free one counter protocol has a strictly increasing path. In the positive case, using Lemma 12, we can design an NL algorithm for the synchronization problem. Indeed, we can check the sufficient and necessary condition given by the lemma, looking for paths of length at most twice the number of states and whose counter value is hence bounded as well by this value which can be stored in logarithmic space. The same reasoning holds for the negative case relying on Lemma 14. Here again we obtain the matching lower bound from the reachability problem in directed graph.
Theorem 15. Synchro restricted to zero-test free one-counter protocols is NL-complete.
A detour to rendez-vous networks
A well-studied model of parameterized networks is the one where the different processes communicate thanks to pairwise rendez-vous, a process sends a message m m m that has to be received simultaneously by another process (otherwise the sender cannot move). This model has been introduced in [16 ] and studied for instance in [2 , 4 , 20 ] . We shall see that we can use results obtained for this model to obtain complexity results for counter protocols.
For a finite set of messages Σ \Sigma Σ , we denote by A c t R d v ( Σ ) ActRdv(\Sigma) A c tR d v ( Σ ) the set of rendez-vous actions over Σ \Sigma Σ represented by { ! m , ? m } ∪ { τ } \{!m,?m\}\cup\{\tau\} { ! m , ? m } ∪ { τ } where ! m !m ! m [resp. ? m ?m ? m ] represents the request [resp. response] of a rendez-vous over the message m m m and τ \tau τ corresponds to an internal action.
Definition 16 (Rendez-vous protocol). A rendez-vous protocol RP is a tuple ( Q , Σ , q i n , q f , E ) (Q,\Sigma,q_{in},q_f,E) ( Q , Σ , q in , q f , E ) where Q Q Q is a finite set of states, Σ \Sigma Σ is a finite alphabet of messages, q i n ∈ Q q_{in}\in Q q in ∈ Q is the initial state, q f ∈ Q q_f\in Q q f ∈ Q is the final state such that q i n ≠ q f q_{in}\ne q_f q in = q f and E ⊆ Q × A c t R d v ( Σ ) × Q E\subseteq Q\times ActRdv(\Sigma)\times Q E ⊆ Q × A c tR d v ( Σ ) × Q is the set of edges labeled by rendez-vous actions over Σ \Sigma Σ .
A configuration ξ \xi ξ with n > 0 n>0 n > 0 processes of RP is a vector Q n Q^n Q n whose size n n n is denoted by ∥ ξ ∥ \lVert\xi\rVert ∥ ξ ∥ . The set of configurations is given by Ξ = ⋃ n ∈ N ∖ { 0 } Q n \Xi=\bigcup_{n\in\mathbb{N}\setminus\{0\}}Q^n Ξ = ⋃ n ∈ N ∖ { 0 } Q n . The set of initial configurations is equal to Ξ i n = { ξ ∈ Q n ∣ ξ [ p ] = q i n for all 0 < p ≤ ∥ ξ ∥ } \Xi_{in}=\{\xi\in Q^n\mid\xi[p]=q_{in}\text{ for all }0<p\leq\lVert\xi\rVert\} Ξ in = { ξ ∈ Q n ∣ ξ [ p ] = q in for all 0 < p ≤ ∥ ξ ∥} . We denote by Ξ ∀ f \Xi_{\forall f} Ξ ∀ f the set { ξ ∈ Q n ∣ ξ [ p ] = q f for all 0 < p ≤ ∥ ξ ∥ } \{\xi\in Q^n\mid\xi[p]=q_f\text{ for all }0<p\leq\lVert\xi\rVert\} { ξ ∈ Q n ∣ ξ [ p ] = q f for all 0 < p ≤ ∥ ξ ∥} where all processes are in state q f q_f q f .
The network semantics associated to a rendez-vous protocol RP = ( Q , Σ , q i n , q f , E ) =(Q,\Sigma,q_{in},q_f,E) = ( Q , Σ , q in , q f , E ) is given by the transition system ( Ξ , ⇒ ) (\Xi,\Rightarrow) ( Ξ , ⇒ ) where ⇒ ⊆ Ξ × Ξ \Rightarrow\subseteq\Xi\times\Xi ⇒⊆ Ξ × Ξ is the transition relation defined as follows. We have ξ ⇒ ξ ′ \xi\Rightarrow\xi' ξ ⇒ ξ ′ iff ∥ ξ ∥ = ∥ ξ ′ ∥ \lVert\xi\rVert=\lVert\xi'\rVert ∥ ξ ∥ = ∥ ξ ′ ∥ and one of the following conditions holds:
there exists p ∈ [ 1 , ∥ ξ ∥ ] p\in[1,\lVert\xi\rVert] p ∈ [ 1 , ∥ ξ ∥] such that ( ξ [ p ] , τ , ξ ′ [ p ] ) ∈ E (\xi[p],\tau,\xi'[p])\in E ( ξ [ p ] , τ , ξ ′ [ p ]) ∈ E and ξ [ p ′ ] = ξ ′ [ p ′ ] \xi[p']=\xi'[p'] ξ [ p ′ ] = ξ ′ [ p ′ ] for all p ′ ∈ [ 1 , ∥ ξ ∥ ] ∖ { p } p'\in[1,\lVert\xi\rVert]\setminus\{p\} p ′ ∈ [ 1 , ∥ ξ ∥] ∖ { p } (one process performs an internal action).
there exists p , p ′ ∈ [ 1 , ∥ ξ ∥ ] p,p' \in[1,\lVert\xi\rVert] p , p ′ ∈ [ 1 , ∥ ξ ∥] and m ∈ Σ m \in\Sigma m ∈ Σ such that ( ξ [ p ] , ! m , ξ ′ [ p ] ) , ( ξ [ p ′ ] , ? m , ξ ′ [ p ′ ] ) ∈ E (\xi[p],!m,\xi'[p]),(\xi[p'],?m,\xi'[p']) \in E ( ξ [ p ] , ! m , ξ ′ [ p ]) , ( ξ [ p ′ ] , ? m , ξ ′ [ p ′ ]) ∈ E and ξ [ p ′ ′ ] = ξ ′ [ p ′ ′ ] \xi[p''] = \xi'[p''] ξ [ p ′′ ] = ξ ′ [ p ′′ ] for all p ′ ′ ∈ [ 1 , ∥ ξ ∥ ] ∖ { p , p ′ } p'' \in[1,\lVert\xi\rVert] \setminus\{p,p'\} p ′′ ∈ [ 1 , ∥ ξ ∥] ∖ { p , p ′ } (two processes synchronize with a rendez-vous over message m m m ).
We denote then by ⇒ ∗ \Rightarrow^* ⇒ ∗ the reflexive and transitive closure of ⇒ \Rightarrow ⇒ . As for counter protocols, we say that the final state is universally reachable by the rendez-vous protocol RP iff there exists an initially configuration ξ i n ∈ Ξ i n \xi_{\mathrm{in}} \in\Xi_{\mathrm{in}} ξ in ∈ Ξ in and a configuration ξ f ∈ Ξ ∀ f \xi_f \in\Xi_{\forall f} ξ f ∈ Ξ ∀ f such that ξ i n ⇒ ∗ ξ f \xi_{\mathrm{in}} \Rightarrow^* \xi_f ξ in ⇒ ∗ ξ f .
In [4 ] , the authors study the cut-off problem for rendez-vous protocols, which consists in deciding whether there exists a bound B ∈ N B \in\mathbb{N} B ∈ N such that for all m ≥ B m \ge B m ≥ B and for all initial configurations ξ i n ∈ Q m \xi_{\mathrm{in}} \in Q^m ξ in ∈ Q m , there exists a configuration ξ f ∈ Ξ ∀ f \xi_f \in\Xi_{\forall f} ξ f ∈ Ξ ∀ f verifying ξ i n ⇒ ∗ ξ f \xi_{\mathrm{in}} \Rightarrow^* \xi_f ξ in ⇒ ∗ ξ f , and they show it can be solved in polynomial time. We can use this result to decide whether a final state is universally reachable by a rendez-vous protocol. The idea is to build another rendez-vous protocol where a process in the final state can send all the processes remained in the initial state to the final state (thanks to a specific message). We have then that the cut-off problem for rendez-vous protocols has a positive answer in this new protocol iff the final state is universally reachable by the original rendez-vous protocol.
Theorem 17. Given a rendez-vous protocol R P = ( Q , Σ , q i n , q f , E ) \mathrm{RP}=(Q,\Sigma,q_{\mathrm{in}},q_f,E) RP = ( Q , Σ , q in , q f , E ) , we can decide in P t i m e \mathrm{Ptime} Ptime whether q f q_f q f is universally reachable by RP or not.
Proof. Let R P = ( Q , Σ , q i n , q f , E ) \mathrm{RP}=(Q,\Sigma,q_{\mathrm{in}},q_f,E) RP = ( Q , Σ , q in , q f , E ) be a rendez-vous protocol. W.l.o.g we assume that there is no edge in E E E with destination q i n q_{\mathrm{in}} q in and no edge with source q f q_f q f , i.e., for all ( q , a , q ′ ) ∈ E (q,a,q') \in E ( q , a , q ′ ) ∈ E we have q ′ ≠ q i n q' \ne q_{\mathrm{in}} q ′ = q in and q ≠ q f q \ne q_f q = q f (the protocol being non-deterministic, we can make a copy of q i n q_{\mathrm{in}} q in and q f q_f q f respecting this property). From RP, we build another rendez-vous protocol R P ′ = ( Q , Σ ∪ { e n d } , q i n , q f , E ′ ) \mathrm{RP}'=(Q,\Sigma\cup\{\mathit{end}\},q_{\mathrm{in}},q_f,E') RP ′ = ( Q , Σ ∪ { end } , q in , q f , E ′ ) with the same set of states and such that E ′ = E ∪ { ( q i n , ? e n d , q f ) , ( q f , ! e n d , q f ) } E'=E \cup\{(q_{\mathrm{in}},?\mathit{end},q_f),(q_f,!\mathit{end},q_f)\} E ′ = E ∪ {( q in , ? end , q f ) , ( q f , ! end , q f )} . In RP′, a process in the final state q f q_f q f can send all the processes in q i n q_{\mathrm{in}} q in in the final state q f q_f q f . We have then that the cut-off problem for rendez-vous networks studied in [4 ] has a positive answer in RP′ iff q f q_f q f is universally reachable by RP.
No test and many counters
We show here that when the considered counter protocol has no test, we can translate it into a rendez-vous protocol and use the result of Theorem 17 to show that Synchro can be solved in polynomial time. The intuition is that in the constructed rendez-vous protocol, we have some processes simulating the behavior of processes of the counter protocol and other processes simulating the behavior of the counter. Intuitively, each time a process will increment a counter c c c , in the rendez-vous protocol, a rendez-vous request !inc( c ) (c) ( c ) will be performed and the process answering it to will be sent to a state 1 c 1_c 1 c (as a matter of fact, the number of processes in state 1 c 1_c 1 c will represent the associated counter value). A process in such a state can then answer to a request, doing ?dec( c ) (c) ( c ) , to decrement the counter, and in that case it is sent to the final state. A last trick is needed as in Synchro, we do not require the counter values to be 0 in the final configuration, so a process in the final state, will be able to request rendez-vous with !dec( c ) (c) ( c ) to send the remaining processes in 1 c 1_c 1 c to the final state. Not that in order to avoid, a process simulating a counter to play the role of process simulating a process of the counter protocol when reaching the final state, we rely on a new final state q f ′ q'_f q f ′ which can be reached by any process reaching the original final state q f q_f q f (but cannot be reached by a process simulating a counter).
We move now to the formal definition. Let P r = ( Q , k , q i n , q f , E ) \mathrm{Pr}=(Q,k,q_{\mathrm{in}},q_f,E) Pr = ( Q , k , q in , q f , E ) be a zero-test free counter protocol. We build the rendez-vous protocol R P = ( Q ′ , Σ , q i n , q f ′ , E ′ ) \mathrm{RP}=(Q',\Sigma,q_{\mathrm{in}},q'_f,E') RP = ( Q ′ , Σ , q in , q f ′ , E ′ ) with Q ′ = Q ∪ { 1 c ∣ c ∈ [ 1 , k ] } ∪ { q f ′ } Q'=Q \cup\{1_c \mid c \in[1,k]\} \cup\{q'_f\} Q ′ = Q ∪ { 1 c ∣ c ∈ [ 1 , k ]} ∪ { q f ′ } (with Q ∩ ( { 1 c ∣ c ∈ [ 1 , k ] } ∪ { q f ′ } ) = ∅ Q \cap(\{1_c \mid c \in[1,k]\} \cup\{q'_f\})=\varnothing Q ∩ ({ 1 c ∣ c ∈ [ 1 , k ]} ∪ { q f ′ }) = ∅ ) and Σ = { i n c ( c ) , d e c ( c ) ∣ c ∈ [ 1 , k ] } \Sigma=\{\mathit{inc}(c),\mathit{dec}(c) \mid c \in[1,k]\} Σ = { inc ( c ) , dec ( c ) ∣ c ∈ [ 1 , k ]} and E ′ E' E ′ verifies the following properties:
for all q , q ′ ∈ Q q,q' \in Q q , q ′ ∈ Q , we have ( q , ! i n c ( c ) , q ′ ) ∈ E ′ (q,!inc(c),q') \in E' ( q , ! in c ( c ) , q ′ ) ∈ E ′ iff ( q , i n c ( c ) , q ′ ) ∈ E (q,inc(c),q') \in E ( q , in c ( c ) , q ′ ) ∈ E , and,
for all q , q ′ ∈ Q q,q' \in Q q , q ′ ∈ Q , we have ( q , ! d e c ( c ) , q ′ ) ∈ E ′ (q,!dec(c),q') \in E' ( q , ! d ec ( c ) , q ′ ) ∈ E ′ iff ( q , d e c ( c ) , q ′ ) ∈ E (q,dec(c),q') \in E ( q , d ec ( c ) , q ′ ) ∈ E , and,
for all q , q ′ ∈ Q q,q' \in Q q , q ′ ∈ Q , we have ( q , τ , q ′ ) ∈ E ′ (q,\tau,q') \in E' ( q , τ , q ′ ) ∈ E ′ iff ( q , τ , q ′ ) ∈ E (q,\tau,q') \in E ( q , τ , q ′ ) ∈ E , and,
( q i n , ? i n c ( c ) , 1 c ) , ( 1 c , ? d e c ( c ) , q ′ ) ∈ E ′ (q_{in},?inc(c),1_c),(1_c,?dec(c),q') \in E' ( q in , ? in c ( c ) , 1 c ) , ( 1 c , ? d ec ( c ) , q ′ ) ∈ E ′ for all c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] , and,
( q f ′ , ! d e c ( c ) , q ′ ) ∈ E ′ (q'_f,!dec(c),q') \in E' ( q f ′ , ! d ec ( c ) , q ′ ) ∈ E ′ for all c ∈ [ 1 , k ] c \in[1,k] c ∈ [ 1 , k ] , and,
( q f , τ , q f ′ ) ∈ E (q_f,\tau,q'_f) \in E ( q f , τ , q f ′ ) ∈ E .
Relying on the two semantics of counter protocols and rendez-vous protocols, we can easily show that q f q_f q f is universally reachable in P r \mathit{Pr} Pr if and only if q f ′ q'_f q f ′ universally reachable in R P \mathit{RP} RP . Thanks to Theorem 17, we deduce the following result.
Theorem 18. Synchro restricted to zero-test free protocols is in P t i m e \mathsf{Ptime} Ptime .
Authorizing tests over a single counter
The translation towards rendez-vous protocols presented in the previous subsection does not work when allowing zero-tests because the communication with rendez-vous does not allow to test the absence of a process ready to communicate through a rendez-vous. However when dealing with a single counter, we can provide another translation relying on the fact that initial and final runs can be reordered into a normal form which can be simulated by rendez-vous protocols. Intuitively such a run will be in a normal form if it can be decomposed into a sequence of subruns, which are of three possible forms: either they consist of a run where a single process is performing some actions and where the counter value starts at value 0 and ends at value 0, or they are of length 2 and they correspond to an increment performed by a process followed by a decrement performed by another process or they correspond to a run involving a single process reaching the final control state. This observation allows us to build a rendez-vous protocol where the runs of the counter protocols performed by a single process between two states will be replaced by an internal actions (we can compute the pairs of states satisfying this property in NL relying on Theorem 3) or a rendez-vous between two processes will correspond to a sequence of an increment performed by a process and a decrement performed by another one. We now formalize these intuitions.
In the sequel, we consider a one-counter protocol P r = ( Q , 1 , q i n , q f , E ) \mathit{Pr}=(Q,1,q_{in},q_f,E) Pr = ( Q , 1 , q in , q f , E ) . W.l.o.g. we assume that there is no edge in E E E starting at q f q_f q f (i.e., for all ( q , a , q ′ ) ∈ E (q,a,q') \in E ( q , a , q ′ ) ∈ E , we have q ≠ q f q \ne q_f q = q f ). We introduce now some new definitions for the runs of P r \mathit{Pr} Pr . Let ρ = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho=\gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell ρ = γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ be a n n n -process run of P r \mathit{Pr} Pr with γ i = ( s i , v i ) \gamma_i=(s_i,v_i) γ i = ( s i , v i ) for all i ∈ [ 0 , ℓ ] i \in[0,\ell] i ∈ [ 0 , ℓ ] . We say that:
ρ \rho ρ is a single-active-process run iff there exists p ∈ [ 1 , n ] p \in[1,n] p ∈ [ 1 , n ] such that p i = p p_i=p p i = p for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] (in that case p p p is called the active process ); furthermore it is said to be final if s ℓ [ p ] = q f s_\ell[p]=q_f s ℓ [ p ] = q f .
ρ \rho ρ is a 0-run [resp. starts with 0] iff v 0 = v ℓ = 0 v_0=v_\ell=0 v 0 = v ℓ = 0 [resp. v 0 = 0 v_0=0 v 0 = 0 ].
ρ \rho ρ stays above 0 iff v i > 0 v_i>0 v i > 0 for all i ∈ [ 1 , ℓ − 1 ] i \in[1,\ell-1] i ∈ [ 1 , ℓ − 1 ] .
ρ \rho ρ is an inc/dec-run iff ℓ = 2 \ell=2 ℓ = 2 and p 1 ≠ p 2 p_1 \ne p_2 p 1 = p 2 and l a b ( e 1 ) = i n c lab(e_1)=inc l ab ( e 1 ) = in c and l a b ( e 2 ) = d e c lab(e_2)=dec l ab ( e 2 ) = d ec .
Note that if ρ \rho ρ stays above 0, it means that l a b ( e i ) ≠ z e r o lab(e_i) \ne zero l ab ( e i ) = z er o for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] . Furthermore a run ρ ′ = γ 0 → p 1 ′ , e 1 ′ γ 1 ′ → p 2 ′ , e 2 ′ γ 2 ′ ⋯ → p ℓ ′ , e ℓ ′ γ ℓ \rho'=\gamma_0 \xrightarrow{p'_1,e'_1} \gamma'_1 \xrightarrow{p'_2,e'_2} \gamma'_2 \cdots\xrightarrow{p'_\ell,e'_\ell} \gamma_\ell ρ ′ = γ 0 p 1 ′ , e 1 ′ γ 1 ′ p 2 ′ , e 2 ′ γ 2 ′ ⋯ p ℓ ′ , e ℓ ′ γ ℓ is a permutation of a run ρ = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \rho=\gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell ρ = γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ iff there exists a permutation π : [ 1 , ℓ ] ↦ [ 1 , ℓ ] \pi:[1,\ell]\mapsto[1,\ell] π : [ 1 , ℓ ] ↦ [ 1 , ℓ ] such that ( p i , e i ) = ( p π ( i ) ′ , e π ( i ) ′ ) (p_i,e_i)=(p'_{\pi(i)},e'_{\pi(i)}) ( p i , e i ) = ( p π ( i ) ′ , e π ( i ) ′ ) for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] (the two runs start and end with the same configurations). We say that a 0-run ρ \rho ρ is in normal form iff ρ = ρ 1 ⋅ ρ 2 ⋯ ρ m \rho=\rho_1\cdot\rho_2\cdots\rho_m ρ = ρ 1 ⋅ ρ 2 ⋯ ρ m where for all i ∈ [ 1 , m ] i \in[1,m] i ∈ [ 1 , m ] , we have that ρ i \rho_i ρ i is either a single-active-process 0-run or an inc/dec run.
Lemma 19. If ρ \rho ρ is 0-run, then there exists a permutation of ρ \rho ρ in normal form.
Proof. We reason by induction on the length of the run. If ρ \rho ρ is a 0-run of length 1, then ρ \rho ρ is in normal formal because it is a single-active-process 0-run. Assume now that the property holds for all the 0-runs of length ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 and let ρ \rho ρ be a 0-run of length ℓ + 1 \ell+ 1 ℓ + 1 . We have two different cases. If ρ \rho ρ does not stay above 0, then there exists two 0-runs ρ 1 \rho_1 ρ 1 and ρ 2 \rho_2 ρ 2 such that ρ = ρ 1 ⋅ ρ 2 \rho= \rho_1 \cdot\rho_2 ρ = ρ 1 ⋅ ρ 2 . By induction hypothesis, there exists ρ 1 ′ \rho'_1 ρ 1 ′ a permutation of ρ 1 \rho_1 ρ 1 in normal form and ρ 2 ′ \rho'_2 ρ 2 ′ a permutation of ρ 2 \rho_2 ρ 2 in normal form and the run ρ 1 ′ ⋅ ρ 2 ′ \rho'_1 \cdot\rho'_2 ρ 1 ′ ⋅ ρ 2 ′ corresponds to a permutation of ρ \rho ρ in normal form.
Assume now that ρ \rho ρ stays above 0 and that it is not a single-active-process run (otherwise the property holds directly). Then ρ \rho ρ has the following form ρ = ρ i n c ⋅ θ ⋅ ρ d e c \rho= \rho_{\mathrm{inc}} \cdot\theta\cdot\rho_{\mathrm{dec}} ρ = ρ inc ⋅ θ ⋅ ρ dec where ρ i n c = γ → p , ( q , i n c , q ′ ) γ ′ \rho_{\mathrm{inc}} = \gamma\xrightarrow{p,(q,\mathrm{inc},q')} \gamma' ρ inc = γ p , ( q , inc , q ′ ) γ ′ , ρ d e c = γ ′ ′ → p ′ , ( q ′ ′ , d e c , q ′ ′ ′ ) γ ′ ′ ′ \rho_{\mathrm{dec}} = \gamma'' \xrightarrow{p',(q'',\mathrm{dec},q''')} \gamma''' ρ dec = γ ′′ p ′ , ( q ′′ , dec , q ′′′ ) γ ′′′ and θ = γ 0 → p 1 , e 1 γ 1 → p 2 , e 2 γ 2 ⋯ → p ℓ , e ℓ γ ℓ \theta= \gamma_0 \xrightarrow{p_1,e_1} \gamma_1 \xrightarrow{p_2,e_2} \gamma_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma_\ell θ = γ 0 p 1 , e 1 γ 1 p 2 , e 2 γ 2 ⋯ p ℓ , e ℓ γ ℓ with γ 0 = γ ′ \gamma_0 = \gamma' γ 0 = γ ′ , γ ℓ = γ ′ ′ \gamma_\ell= \gamma'' γ ℓ = γ ′′ and for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] , we have l a b ( e i ) ≠ z e r o lab(e_i) \ne\mathrm{zero} l ab ( e i ) = zero and γ i = ( s i , v i ) \gamma_i = (s_i,v_i) γ i = ( s i , v i ) such that v 0 = v ℓ = 1 v_0 = v_\ell= 1 v 0 = v ℓ = 1 and v i ≥ 1 v_i \ge1 v i ≥ 1 .
Before we continue, we deal with the specific case where θ \theta θ is a single-active-process run with p p p as an active process. As ρ \rho ρ is not an single-active-process run, we have necessarily p ′ ≠ p p' \ne p p ′ = p . In that case, we can move the actions of ρ d e c \rho_{\mathrm{dec}} ρ dec just after ρ i n c \rho_{\mathrm{inc}} ρ inc to obtain a 0-run of the form ρ i n c ⋅ ρ d e c ′ ⋅ θ ′ \rho_{\mathrm{inc}} \cdot\rho'_{\mathrm{dec}} \cdot\theta' ρ inc ⋅ ρ dec ′ ⋅ θ ′ with a c t i o n s ( ρ d e c ′ ) = a c t i o n s ( ρ d e c ) = ( p ′ , ( q ′ ′ , d e c , q ′ ′ ′ ) ) actions(\rho'_{\mathrm{dec}}) = actions(\rho_{\mathrm{dec}}) = (p',(q'',\mathrm{dec},q''')) a c t i o n s ( ρ dec ′ ) = a c t i o n s ( ρ dec ) = ( p ′ , ( q ′′ , dec , q ′′′ )) and a c t i o n s ( θ ′ ) = θ actions(\theta') = \theta a c t i o n s ( θ ′ ) = θ . In that case, note that applying the induction hypothesis to θ ′ \theta' θ ′ we obtain a run θ ′ ′ \theta'' θ ′′ that is a permutation of θ ′ \theta' θ ′ in normal form and the run ρ i n c ⋅ ρ d e c ′ ⋅ θ ′ ′ \rho_{\mathrm{inc}} \cdot\rho'_{\mathrm{dec}} \cdot\theta'' ρ inc ⋅ ρ dec ′ ⋅ θ ′′ is a permutation of ρ \rho ρ in normal form.
We suppose now that θ \theta θ is not a single-active-process run with p p p as an active process. From θ \theta θ , we can build a 0-run θ ′ \theta' θ ′ which follows the same step as θ \theta θ starting at a counter value equal to 0 (instead of 1). Formally, θ ′ = γ 0 ′ → p 1 , e 1 γ 1 ′ → p 2 , e 2 γ 2 ′ ⋯ → p ℓ , e ℓ γ ℓ ′ \theta' = \gamma'_0 \xrightarrow{p_1,e_1} \gamma'_1 \xrightarrow{p_2,e_2} \gamma'_2 \cdots\xrightarrow{p_\ell,e_\ell} \gamma'_\ell θ ′ = γ 0 ′ p 1 , e 1 γ 1 ′ p 2 , e 2 γ 2 ′ ⋯ p ℓ , e ℓ γ ℓ ′ where for all i ∈ [ 1 , ℓ ] i \in[1,\ell] i ∈ [ 1 , ℓ ] we have γ i ′ = ( s i , v i ′ ) \gamma'_i = (s_i,v'_i) γ i ′ = ( s i , v i ′ ) with v i ′ = v i − 1 v'_i = v_i - 1 v i ′ = v i − 1 . Note that by construction a c t i o n s ( θ ′ ) = a c t i o n s ( θ ) actions(\theta') = actions(\theta) a c t i o n s ( θ ′ ) = a c t i o n s ( θ ) . We can now apply the induction hypothesis to obtain a run θ ′ ′ \theta'' θ ′′ that is a permutation of the run θ ′ \theta' θ ′ in normal form. Hence θ ′ ′ = θ 1 ⋅ θ 2 ⋯ θ m \theta'' = \theta_1 \cdot\theta_2 \cdots\theta_m θ ′′ = θ 1 ⋅ θ 2 ⋯ θ m where θ i \theta_i θ i is either a single-active process 0-run or an inc/dec run for all i ∈ [ 1 , m ] i \in[1,m] i ∈ [ 1 , m ] . Now take k k k to be the smallest index in [ 1 , m ] [1,m] [ 1 , m ] such that θ k \theta_k θ k is not a single-active-process 0-run with p p p as an active process (it necessarily exists as θ \theta θ is not a single-active-process run with p p p as an active process). We proceed with a case analysis:
θ k \theta_k θ k is a single-active-process 0-run with p ′ p' p ′ as an active process (and p ′ ≠ p p' \ne p p ′ = p ). In that case, from ρ = ρ i n c ⋅ θ ⋅ ρ d e c \rho= \rho_{\mathrm{inc}} \cdot\theta\cdot\rho_{\mathrm{dec}} ρ = ρ inc ⋅ θ ⋅ ρ dec we can build another 0-run of the form θ k ′ ⋅ ρ i n c ′ ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ d e c \theta'_k \cdot\rho'_{\mathrm{inc}} \cdot\theta'_1 \cdot\theta'_2 \cdots\theta'_{k-1} \cdot\theta'_{k+1} \cdots\theta'_m \cdot\rho_{\mathrm{dec}} θ k ′ ⋅ ρ inc ′ ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ dec where a c t i o n s ( ρ i n c ′ ) = a c t i o n ( ρ i n c ) actions(\rho'_{\mathrm{inc}}) = action(\rho_{\mathrm{inc}}) a c t i o n s ( ρ inc ′ ) = a c t i o n ( ρ inc ) and a c t i o n s ( θ i ′ ) = a c t i o n s ( θ i ) actions(\theta'_i) = actions(\theta_i) a c t i o n s ( θ i ′ ) = a c t i o n s ( θ i ) for all i ∈ [ 1 , m ] i \in[1,m] i ∈ [ 1 , m ] . This is possible as in θ ′ ′ \theta'' θ ′′ before the index k k k , the active process p ′ p' p ′ of θ k \theta_k θ k which is different than p p p did not perform any actions, this is why we can move its actions which have globally no effect on the counter value at the beginning of run ρ \rho ρ . We have that θ k ′ \theta'_k θ k ′ is a single-active-process 0-run and by applying the induction hypothesis on the 0-run ρ i n c ′ ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ d e c \rho'_{\mathrm{inc}} \cdot\theta'_1 \cdot\theta'_2 \cdots\theta'_{k-1} \cdot\theta'_{k+1} \cdots\theta'_m \cdot\rho_{\mathrm{dec}} ρ inc ′ ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ dec , we obtain a run permutation of ρ \rho ρ in normal form.
θ k \theta_k θ k is an inc/dec run with a c t i o n s ( θ k ) = ( p i n c , e i n c ) ( p d e c , e d e c ) actions(\theta_k) = (p_{\mathrm{inc}},e_{\mathrm{inc}})(p_{\mathrm{dec}},e_{\mathrm{dec}}) a c t i o n s ( θ k ) = ( p inc , e inc ) ( p dec , e dec ) . In that case, we can exchange the order of the two actions to obtain a run ρ ′ = ρ i n c ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k ( 1 ) ⋅ θ k ( 2 ) ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ d e c \rho' = \rho_{\mathrm{inc}} \cdot\theta'_1 \cdot\theta'_2 \cdots\theta'_{k-1} \cdot\theta_k^{(1)} \cdot\theta_k^{(2)} \cdot\theta'_{k+1} \cdots\theta'_m \cdot\rho_{\mathrm{dec}} ρ ′ = ρ inc ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k ( 1 ) ⋅ θ k ( 2 ) ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ dec where a c t i o n s ( ρ i n c ′ ) = a c t i o n ( ρ i n c ) actions(\rho'_{\mathrm{inc}}) = action(\rho_{\mathrm{inc}}) a c t i o n s ( ρ inc ′ ) = a c t i o n ( ρ inc ) and a c t i o n s ( θ i ′ ) = a c t i o n s ( θ i ) actions(\theta'_i) = actions(\theta_i) a c t i o n s ( θ i ′ ) = a c t i o n s ( θ i ) for all i ∈ [ 1 , m ] ∖ { k } i \in[1,m] \setminus\{k\} i ∈ [ 1 , m ] ∖ { k } and a c t i o n s ( θ k ( 1 ) ) = ( p d e c , e d e c ) actions(\theta_k^{(1)}) = (p_{\mathrm{dec}},e_{\mathrm{dec}}) a c t i o n s ( θ k ( 1 ) ) = ( p dec , e dec ) and a c t i o n s ( θ k ( 2 ) ) = ( p i n c , e i n c ) actions(\theta_k^{(2)}) = (p_{\mathrm{inc}},e_{\mathrm{inc}}) a c t i o n s ( θ k ( 2 ) ) = ( p inc , e inc ) . This exchange is possible because in the run θ \theta θ the counter never goes below 1. The runs ρ i n c ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k ( 1 ) \rho_{\mathrm{inc}} \cdot\theta'_1 \cdot\theta'_2 \cdots\theta'_{k-1} \cdot\theta_k^{(1)} ρ inc ⋅ θ 1 ′ ⋅ θ 2 ′ ⋯ θ k − 1 ′ ⋅ θ k ( 1 ) and θ k ( 2 ) ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ d e c \theta_k^{(2)} \cdot\theta'_{k+1} \cdots\theta'_m \cdot\rho_{\mathrm{dec}} θ k ( 2 ) ⋅ θ k + 1 ′ ⋯ θ m ′ ⋅ ρ dec are then 0-runs, which can both be put in normal form by induction hypothesis to obtain a run that is a permutation of ρ \rho ρ in normal form.
Relying on this we can extend our definition of runs in normal forms to initial runs bringing every process in the final state q f q_f q f . We say that an initial n n n -process run ρ \rho ρ such that l a s t ( ρ ) ∈ Γ V f last(\rho) \in\Gamma_{\mathit{Vf}} l a s t ( ρ ) ∈ Γ Vf is in normal form iff ρ = ρ 1 ⋅ ρ 2 ⋯ ρ m \rho= \rho_1 \cdot\rho_2 \cdots\rho_m ρ = ρ 1 ⋅ ρ 2 ⋯ ρ m where for all i ∈ [ 1 , m ] i \in[1,m] i ∈ [ 1 , m ] , we have that $\rho_i is either a single-active-process 0-run or an inc/dec run or a final single-active-process run with active process p p p such that p a t h ( p ) ( ρ i ) path^{(p)}(\rho_i) p a t h ( p ) ( ρ i ) is a path feasible with 1 process. Relying one the previous lemma and on a similar reasoning, we can prove the following result.
Lemma 20. If ρ \rho ρ is a run starting with 0 such that l a s t ( ρ ) ∈ Γ ∀ f last(\rho) \in\Gamma_{\forall f} l a s t ( ρ ) ∈ Γ ∀ f , then there exists a permutation of ρ \rho ρ in normal form.
Proof. Consider a run ρ \rho ρ starting with 0 and such that l a s t ( ρ ) ∈ Γ ∀ f last(\rho) \in\Gamma_{\forall f} l a s t ( ρ ) ∈ Γ ∀ f . Here again, as for the proof of Lemma 19, we can reason by induction on the length of ρ \rho ρ . If it is of length 1, then it is a single-active-process run and the path of the active process is a final path feasible with 1 process. If ρ \rho ρ does not stay above 0, we can cut it into two runs: the first one is a 0-run for which we can apply Lemma 19 and the second one on which we apply the induction hypothesis. If ρ \rho ρ stays above 0, then its first action is an increment and as for the proof of Lemma 19, we can consider the 0-run ρ ′ \rho' ρ ′ build from ρ \rho ρ by deleting this first action and following them the same step. By induction hypothesis there exists a permutation ρ ′ ′ \rho'' ρ ′′ of ρ ′ \rho' ρ ′ which is in normal formal. If in ρ ′ ′ \rho'' ρ ′′ there is no inc/dec run, then all the processes involved in ρ ′ ′ \rho'' ρ ′′ can reach q f q_f q f on their own and replacing the process performing the increment in ρ \rho ρ at the beginning of ρ ′ ′ \rho'' ρ ′′ we obtain again a run where all processes can reach on their own q f q_f q f . If in ρ ′ ′ \rho'' ρ ′′ there is an inc/dec run, then we can exchange the order locally between the increment and decrement and we obtain again a 0-run followed by a run bringing everyone to q f q_f q f , both of them can be put in normal form applying Lemma 19 and the induction hypothesis.
:::
This lemma allows us to build from the counter protocol Pr a rendez-vous protocol RP which simulates the behavior of a run in normal form. We have indeed the following cases to deal with. Either each process can perform actions on their own going from a state q q q to q ′ q' q ′ leaving the counter equal to 0, in that case we can compute such pairs of states in Pr and simulate their path by an internal action on RP. Or one process performs an increment followed by a decrement of another process; this can be simulated by a rendez-vous (note that afterwards, if the counter was equal to 0 before, it stays equal after). Or a process can go on its own to q f q_f q f (which is by hypothesis a deadlock state) and this is again simulated by an internal action in RP. Formally, we rely on the two following sets of states: S 0 → ∗ 0 = { ( q , q ′ ) ∈ Q 2 ∣ ( [ q ] , [ 0 ] ) → ∗ ( [ q ′ ] , [ 0 ] ) } S_{0\to^*0} = \{(q,q') \in Q^2 \mid([q],[0]) \to^* ([q'],[0])\} S 0 → ∗ 0 = {( q , q ′ ) ∈ Q 2 ∣ ([ q ] , [ 0 ]) → ∗ ([ q ′ ] , [ 0 ])} (pair of states from which there exists a 1-process 0-run starting in the first state and ending in the second state) and S 0 → ∗ f = { q ∈ Q ∣ ( [ q ] , [ 0 ] ) → ∗ ( [ q f ] , [ v ] ) for some v ∈ N } S_{0\to^*f} = \{q \in Q \mid([q],[0]) \to^* ([q_f],[v]) \text{ for some } v \in\mathbb{N}\} S 0 → ∗ f = { q ∈ Q ∣ ([ q ] , [ 0 ]) → ∗ ([ q f ] , [ v ]) for some v ∈ N } (states from which there is a 1-process run reaching the final state). Thanks to Theorem 3, these two sets can be computed in polynomial time. We build the rendez-vous protocol RP = ( Q , Σ , q i n , q f , E ′ ) = (Q,\Sigma,q_{in},q_f,E') = ( Q , Σ , q in , q f , E ′ ) which has the same set of states as Pr, where the alphabet of messages Σ \Sigma Σ is such that Σ = i − d \Sigma= i - d Σ = i − d and where E ′ E' E ′ verifies:
( q , τ , q ′ ) ∈ E ′ (q,\tau,q') \in E' ( q , τ , q ′ ) ∈ E ′ iff ( q , q ′ ) ∈ S 0 → ∗ 0 (q,q') \in S_{0\to^*0} ( q , q ′ ) ∈ S 0 → ∗ 0 or ( q ′ = q f (q' = q_f ( q ′ = q f and q ∈ S 0 → ∗ f q \in S_{0\to^*f} q ∈ S 0 → ∗ f ), and,
( q , ! i − d , q ′ ) ∈ E ′ (q,!i-d,q') \in E' ( q , ! i − d , q ′ ) ∈ E ′ iff ( q , i n c , q ′ ) ∈ E (q,inc,q') \in E ( q , in c , q ′ ) ∈ E , and
( q , ? i − d , q ′ ) ∈ E ′ (q,?i-d,q') \in E' ( q , ? i − d , q ′ ) ∈ E ′ iff ( q , d e c , q ′ ) ∈ E (q,dec,q') \in E ( q , d ec , q ′ ) ∈ E .
Now thanks to Lemma 20 and relying on the semantics of the two protocols, we have that q f q_f q f is universally reachable by Pr iff q f q_f q f is universally reachable by RP. Relying on Theorem 17 and on the fact that RP can be computed in polynomial time (as we have explained before), this leads us to the last result of this section.
Theorem 21. Synchro restricted to one-counter protocols is in Ptime.