# State Complexity of Protocols With Leaders

Jérôme Leroux<EMAIL_ADDRESS>LaBRI, CNRS, Univ. BordeauxTalenceFrance

(2021)

###### Abstract.

Population protocols are a model of computation in which an arbitrary number
of anonymous finite-memory agents are interacting in order to decide by stable
consensus a predicate. In this paper, we focus on the counting predicates that
asks, given an initial configuration, whether the number of agents in some
initial state $i$ is at least $n$. In 2018, Blondin, Esparza, and Jaax shown
that with a fix number of leaders and interaction-width, there exists
infinitely many $n$ for which the counting predicate is stably computable by a
protocol with at most $O(\log\log(n))$ states. We provide in this paper a
matching lower-bound (up to a square root) that improves the inverse-
Ackermannian lower-bound presented at PODC in 2021.

††copyright: none††journalyear: 2021††conference: ; ;

##  1\. Introduction

Population protocols were introduced by Angluin, Aspnes, Diamadi, Fischer, and
Peralta in (Angluin et al., 2004, 2006b) to study the computational power of
networks of resource-limited mobile agents. In this model, each agent has a
state in a finite set of states. When agents interact, their states are
updated accordingly to a finite interaction table. This table corresponds
intuitively to a conservative Petri net (the Petri net is conservative since
the number of agents is preserved by each transition) where each line of the
interaction table is matched by a transition of the Petri net. In this model,
an agent may accept or reject depending only on it own state. A population
protocol is said to be stably computing a predicate, if for any initial
configurations, eventually and forever, under some natural fairness
conditions, either all agents accept or all agents reject. Moreover, this
outcome should only depend on the initial configuration and not on the way
interactions are performed.

Deciding if a protocol stably computes some unknown predicate is a problem
called the _well-specification problem_. This problem was proved to be
decidable in (Esparza et al., 2015, 2017) by observing that well-specification
problem is equivalent to the reachability problem for Petri nets up to
elementary reductions. Since this last problem was recently proved to be
Ackermannian-complete (Leroux, 2021; Czerwinski and Orlikowski, 2021), it
means that deciding the well-specification problem is Ackermannian-complete.
Intuitively, population protocols maybe intrinsically very complicated.

Despite this Ackermannian complexity result, in (Angluin et al., 2007),
Angluin, Aspnes, Eisenstat, and Ruppert have shown that predicates stably
computable by population protocols cannot be more complicated than the one
definable in the Presburger arithmetic. Combined with (Angluin et al., 2004,
2006b), it follows that predicates stably computable by population protocols
are exactly the predicates definable in the Presburger arithmetic.

Since deciding if a population protocol is stably computing some Presburger
predicate is Ackermannian-complete, a natural question is the conciseness of
population protocols. Intuitively, is it possible to define a population
protocol computing predicates that are very complex compared to the number of
states of the protocol ? This problem is related to the so-called _state
complexity_ of a Presburger predicate intuitively defined as the minimal
number of states of a population protocols deciding it.

State complexity upper-bounds are obtained thanks to algorithms computing from
predicates protocols stably computing it with a number of states as small as
possible. In (Blondin et al., 2020), by revisiting the construction of
population protocols deciding Presburger predicates, some improvement on state
complexity upper-bounds was derived. On the other side, state complexity
lower-bounds is also a difficult task since such a bound requires to prove
that there is no way to stably compute a predicate with a given amount of
states. In this context, focusing on the state complexity of simple Presburger
predicates is a natural question. The simplest non trivial Presburger
predicates are clearly the counting predicates that corresponds to the set of
configurations such that the number of agents in a given state is larger than
or equal to some positive number $n$. In 2018, Blondin, Esparza, and Jaax
shown in (Blondin et al., 2018) that with a fix number of leaders and
interaction-width (the number of agents that can interact at each interaction
step), there exists infinitely many $n$ for which the counting predicate is
stably computable by a protocol with at most $O(\log\log(n))$ states.

This state complexity upper-bound was recently completed by a state complexity
lower-bound in (Czerner and Esparza, 2021). In that paper, Czerner and Esparza
shown that the number of states of a population protocol deciding a counting
predicate with a bounded number of leaders and a bounded interaction-width is
at least $\Omega(A^{-1}(n))$ where $A$ is some Ackermannian function, leaving
a gap between the $O(\log\log(n))$ upper-bound and the $\Omega(A^{-1}(n))$
lower-bound.

Main result. In this paper, we follow the model of protocols introduced by
Dana Angluin, James Aspnes, and David Eisenstat in 2006 that allows agents
creations and destructions (Angluin et al., 2006a). We slightly extends that
model to allow leaders. We close the previously mentioned state complexity gap
by proving that for any $h<\frac{1}{2}$, and under a fix number of leaders and
a bounded number of interaction-width, any protocol stably computing a
counting predicate requires at least $\Omega((\log\log(n))^{h})$ states.

Outline. In Section 2 we recall some basic definitions and results about
protocols. In Section 3, we introduce the notion of communication-width of a
protocol and show that protocol with finite communication-width are naturally
related to the model of Petri nets. In Section 4 we introduce the state
complexity problem and show that counting the number of states of protocols
without taking into account the number of leaders or the communication-width
is not relevant. In Section 5 we introduce the notions of stabilized
configurations and show that those configurations are characterized by their
small values. Those results are obtained thanks to Rackoff’s techniques
originally introduced in the context of the coverability problem for Petri
nets. Section 6 contains the central technical lemma. It is a lemma about
Petri nets that intuitively shows that from any initial configuration we can
reach with short executions kind of bottom configurations. Section 7 recalls
the model of Petri net with control-states and provides a result on small
cycles satisfying some properties. This last result is obtained by introducing
a linear system and by applying Pottier’s techniques (Pottier, 1991) in order
to obtain small solutions for that linear system. Results of the previous
sections are combined in Section 8 to obtain our state complexity lower-bound.
Some related open problems and future work are presented in Section 9.

##  2\. Protocols

In this section, we introduce our model of protocols that slightly differs
from the one introduced in (Angluin et al., 2006a) by allowing leaders. We
extend the definition of stably computing a predicate with such a protocol.
This definition is a straight-forward extension of the one given in (Angluin
et al., 2006a) that generalizes several definitions of _fair computations_ in
particular in the context of unconservative protocols.

Let $P$ be a finite set of elements called _states_. A _$P$ -configuration_
(or just a _configuration_ if $P$ is clear from the context) is a mapping in
$\mathbb{N}^{P}$. Given a configuration $\rho$, the number
$|\rho|\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{p\in
P}\rho(p)$ is called the _number of agents_ in $\rho$. Let $Q$ be another
finite set of states. We associate with a $P$-configuration $\rho$ the
$Q$-configuration $\rho|_{Q}$ defined for every $q\in Q$ by
$\rho|_{Q}(q)=\rho(q)$ if $q\in P$ and zero otherwise. Notice that $Q$ is not
necessarily a subset of $P$. Given $p\in P$ we simply denote by $p|_{P}$ (or
just $p$ when $P$ is clear from the context) the mapping in $\mathbb{N}^{P}$
that maps $p$ on $1$ and the other states on zero. The sum $\alpha+\beta$ of
two configurations $\alpha,\beta$ and the product $n.\rho$ where
$n\in\mathbb{N}$ and $\rho$ is a configuration are defined component-wise as
expected.

Let $R$ be a binary relation on $P$-configurations for some finite set of
states $P$. We say that $R$ is _additive_ if $(\alpha,\beta)\in R$ implies
$(\alpha+\rho,\beta+\rho)\in R$ for every configuration $\alpha,\rho,\beta$.
As usual, $R$ is called a _preorder_ if it is _reflexive_ and _transitive_. We
also say that $R$ is _conservative_ if $|\alpha|=|\beta|$ for every
$(\alpha,\beta)\in R$.

A _protocol_ is a tuple $(P,\xrightarrow{*},\rho_{L},I,\gamma)$ where $P$ is a
finite set of _states_ , $\xrightarrow{*}$ is an additive preorder on the
$P$-configurations, $\rho_{L}$ is a $P$-configuration called the
_configuration of leaders_ , $I\subseteq P$ is the set of _initial states_ ,
and $\gamma:P\rightarrow\\{0,\star,1\\}$ is the _output function_. The value
$|\rho_{L}|$ is called the number of _leaders_. A protocol is said to be
_leaderless_ when this number is zero. A configuration of the form
$\rho_{L}+\rho|_{P}$ with $\rho\in\mathbb{N}^{I}$ is called an _initial
configuration_. A protocol is said to be _conservative_ if $\xrightarrow{*}$
is conservative. The function $\gamma$ is extended on any
$\rho\in\mathbb{N}^{P}$ by:

$\gamma(\rho)=\\{j\in\\{0,\star,1\\}\mid\exists p\in
P~{}\rho(p)>0~{}\wedge~{}\gamma(p)=j\\}$

For $j\in\\{0,1\\}$, we introduce the following sets $S_{j}$ called the
$j$-output stable configurations. Notice that $S_{0}$ and $S_{1}$ are not
defined exactly the same way in order to manage the zero configuration. With
our definition we interpret the output of the zero configuration as $0$.
Notice that the definition of $0$-output stable configurations introduced in
(Angluin et al., 2006a) does not care about the zero configuration since
protocols are semantically restricted to non zero configurations. We do not
introduce a set $S_{\star}$ since intuitively the element $\star$ in the image
of $\gamma$ is interpreted as an undetermined output.

$\displaystyle S_{0}$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{\alpha\in\mathbb{N}^{P}\mid\forall\beta~{}\alpha\xrightarrow{*}\beta\Rightarrow\gamma(\beta)\subseteq\\{0\\}\\}$
$\displaystyle S_{1}$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{\alpha\in\mathbb{N}^{P}\mid\forall\beta~{}\alpha\xrightarrow{*}\beta\Rightarrow\gamma(\beta)=\\{1\\}\\}$

A _predicate_ is a mapping $\phi:\mathbb{N}^{I}\rightarrow\\{0,1\\}$. We say
that a protocol stably computes $\phi$ if for every $\rho\in\mathbb{N}^{I}$
and for every $\alpha\in\mathbb{N}^{P}$ such that
$\rho_{L}+\rho|_{P}\xrightarrow{*}\alpha$, there exists $\beta\in
S_{\phi(\rho)}$ such that $\alpha\xrightarrow{*}\beta$. A predicate $\phi$ is
_stably computable_ if there exists a protocol that stably computes it.

###### Remark 1.

In (Angluin et al., 2006a), predicates that are stably computable by
leaderless protocols restricted to functions $\gamma$ such that
$\gamma(P)\subseteq\\{0,1\\}$ are proved to be exactly the predicates
definable in the Presburger arithmetic. We think that this property can be
extended to any protocol with leaders and using the $\star$ element in the
definition of $\gamma$. We left this problem open since it is outside of the
scope of this paper.

##  3\. Interaction-Width

The class of additive preorders is central for defining protocols as shown in
the previous section. Additive preorders are a natural generalization of the
Petri net reachability relations used in classical population protocols. For
parameterized complexity purposes, we introduce in this section the notion of
interaction-width that intuitively limits the number of agents that can
communicate together in a single interaction step. As expected additive
preorders with finite interaction-width are exactly the reachability relations
of Petri nets.

A _$P$ -transition_ (or simply a _transition_ when the finite set $P$ is clear
from the context) is a _pair_
$t\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(\alpha_{t},\beta_{t})$
of $P$-configurations. Given such a transition, we introduce
$|t|\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\max\\{|\alpha_{t}|,|\beta_{t}|\\}$
called the _interaction-width_ of $t$. We associate with a transition $t$ the
binary relation $\xrightarrow{t}$ over the configurations defined by
$\alpha\xrightarrow{t}\beta$ if there exists a configuration $\rho$ such that
$\alpha=\alpha_{t}+\rho$ and $\beta=\beta_{t}+\rho$. Notice that
$\xrightarrow{t}$ is the minimal for the inclusion additive binary relation
that contains $t$. Given a word $\sigma=t_{1}\ldots t_{k}$ of transitions, we
introduce the binary relation $\xrightarrow{\sigma}$ over the configurations
defined by $\alpha\xrightarrow{\sigma}\beta$ if there exists a sequence
$\rho_{0},\ldots,\rho_{k}$ of configurations such that:

$\alpha=\rho_{0}\xrightarrow{t_{1}}\rho_{1}\cdots\xrightarrow{t_{k}}\rho_{k}=\beta$

An additive preorder $R$ is said to have a _finite interaction-width_ if there
exists $m\in\mathbb{N}$ such that for every $(\alpha,\beta)\in R$, there
exists a word $\sigma$ of transitions in $R$ with an interaction-width bounded
by $m$ and such that $\alpha\xrightarrow{\sigma}\beta$. The minimal $m$
satisfying this property is called the _interaction-width_ of $R$, and it is
denoted as $\operatorname{width}(R)$. When $R$ does not have a finite
interaction-width, we define
$\operatorname{width}(R)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\omega$.
The _interaction-width of a protocol_ is defined as the interaction-width of
its implicit additive preorder.

Finite interaction-width additive preorders are related to Petri nets as
follows. A $P$-Petri net $T$ (or simply a Petri net when $P$ is clear from the
context) is a finite set of $P$-transitions. The reachability relation of a
Petri net $T$ is the binary relation $\xrightarrow{T^{*}}$ over the
configurations defined by $\alpha\xrightarrow{T^{*}}\beta$ if there exists
$\sigma\in T^{*}$ such that $\alpha\xrightarrow{\sigma}\beta$. Observe that
the reachability relation of a Petri net $T$ is an additive preorder with an
interaction-width bounded by $\max_{t\in T}|t|$. Moreover, if $R$ is an
additive preorder with a finite interaction-width then $R$ is the reachability
relation of the Petri net $\\{t\in R\mid|t|\leq\operatorname{width}(R)\\}$. It
follows that the class of additive preorders with finite interaction-widths is
equal to the class of Petri net reachability relations.

##  4\. State-complexity of Protocols

The state-complexity of a predicate is intuitively the minimal number of
states of a protocol that stably computes it. In this section, we show that
the state-complexity must involve the interaction-width and the number of
leaders to discard trivial results.

Since our paper focuses on the so-called counting predicates, let us first
introduce those predicates. The _$(i\geq n)$ predicate_ where $i$ is a state
and $n$ a positive natural number is the predicate $\phi_{i\geq
n}:\mathbb{N}^{I}\rightarrow\\{0,1\\}$ where
$I\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{i\\}$ satisfying
$\phi_{i\geq n}(\rho)=1$ if, and only if $\rho(i)\geq n$ for every
configuration $\rho\in\mathbb{N}^{I}$. Such a predicate is called a _counting
predicate_.

The following two examples show that counting the minimal number of states of
protocols stably computing a counting predicate without taking into account
the interaction-width or the number of leaders is not relevant.

###### Example 4.1.

This example shows that the predicate $\phi_{i\geq n}$ is stably computable by
a leaderless conservative protocol with a number of states bounded $2$. We
introduce the protocol $(P,\xrightarrow{*},\rho_{L},I,\gamma)$ where
$P\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{i,p\\}$ for some state
$p\not=i$, $\rho_{L}$ is the zero configuration,
$I\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{i\\}$,
$\gamma^{-1}(\\{0\\})=\\{i\\}$, $\gamma^{-1}(\\{1\\})=\\{p\\}$, and
$\xrightarrow{*}$ is the additive preorder defined by
$\alpha\xrightarrow{*}\beta$ if there exists $m\in\mathbb{N}$ such that
$\beta+m.i=\alpha+m.p$ and such that $m=0\vee|\alpha|\geq n$. In fact, notice
that for every $\rho\in\mathbb{N}^{I}$ and $\alpha\in\mathbb{N}^{P}$ such that
$\rho|_{P}\xrightarrow{*}\alpha$, then either $\rho(i)<n$ and in that case
$\alpha=\rho|_{P}$ is a $0$-output stable configuration, or $\rho(i)\geq n$
and in that case $\alpha\xrightarrow{*}\beta$ where $\beta$ is the $1$-output
stable configuration defined as $\rho(i).p$. We have proved that the protocol
stably computes $\phi_{i\geq n}$. The interaction-width of the previous
protocol is bounded by $n$. In fact, just observe that the reachability
relation of the Petri net
$\\{(\rho+i,\rho+p)\mid\rho\in\mathbb{N}^{P}\wedge|\rho|=n-1\\}$ is equal to
$\xrightarrow{*}$. It follows that $\operatorname{width}(\xrightarrow{*})\leq
n$. In fact, one can easily prove that
$\operatorname{width}(\xrightarrow{*})=n$.

###### Example 4.2.

This example shows that the predicate $\phi_{i\geq n}$ is stably computable by
a conservative protocol with a number of states bounded $6$ and an
interaction-width bounded by $2$. We introduce the protocol
$(P,\xrightarrow{T^{*}},n.\bar{i},I,\gamma)$ where
$P\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{i,\bar{i},p,\bar{p},q,\bar{q}\\}$,
$I\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{i\\}$,
$\gamma^{-1}(\\{1\\})=\\{i,p,q\\}$,
$\gamma^{-1}(\\{0\\})=\\{\bar{i},\bar{p},\bar{q}\\}$, and
$T\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{t,t_{p},\bar{t}_{p},t_{q},\bar{t}_{q},t_{\bar{p}},t_{\bar{q}}\\}$
is the Petri net defined as follows:

$t\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(i+\bar{i},p+q)~{}~{}~{}\begin{array}[]{r@{}l@{}}t_{p}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(\bar{p}+i,p+i)\\\
\bar{t}_{p}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(p+\bar{i},\bar{p}+\bar{i})\end{array}~{}~{}~{}\begin{array}[]{r@{}l@{}}t_{q}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(\bar{q}+i,q+i)\\\
\bar{t}_{q}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(q+\bar{i},\bar{q}+\bar{i})\end{array}~{}~{}~{}\begin{array}[]{r@{}l@{}}t_{\bar{q}}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(p+\bar{q},p+q)\\\
t_{\bar{p}}&\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(q+\bar{p},q+p)\end{array}$

Notice that each transition, except $t$, can only change the bar statue of an
agent in states $p$ and $q$. Let $\rho\in\mathbb{N}^{I}$ and let $\alpha$ be a
configuration such that $n.\bar{i}+\rho|_{P}\xrightarrow{T^{*}}\alpha$ and let
us prove that there exists a $\phi_{i\geq n}(\rho)$-output stable
configuration $\beta$ such that $\alpha\xrightarrow{T^{*}}\beta$. First of
all, by executing $\min\\{\alpha(i),\alpha(\bar{i})\\}$ times the transition
$t$ from $\alpha$, we can assume without loss of generality that $\alpha(i)=0$
or $\alpha(\bar{i})=0$. Observe that $\alpha(\bar{i})=0$ if and only if
$\phi_{i\geq n}(\rho)=1$. Assume first that $\alpha(\bar{i})>0$. In that case,
by executing the transitions $\bar{t}_{p}$ and $\bar{t}_{q}$ the right number
of times, we get from $\alpha$ a configuration $\beta$ such that
$\beta(i)=\beta(p)=\beta(q)=0$. Notice that $\beta$ is $0$-output stable.
Next, assume that $\alpha(i)>0$. In that case, by executing the transitions
$t_{p}$ and $t_{q}$ the right number of times, we get a configuration $\beta$
such that $\beta(\bar{i})=\beta(\bar{p})=\beta(\bar{q})=0$. This configuration
is $1$-output stable. Finally, assume that $\alpha(i)=0$ and
$\alpha(\bar{i})=0$. Since $n>0$, by identifying the last time transition $t$
is executed, we deduce that there exist configurations $\mu,\delta$ such that
$n.\bar{i}+\rho|_{P}\xrightarrow{T^{*}}\mu\xrightarrow{t}\delta\xrightarrow{T_{0}^{*}}\alpha$
such that $\delta(i)=\delta(\bar{i})=0$ where
$T_{0}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{t_{\bar{q}},t_{\bar{p}}\\}$.
Notice that $\delta(p)>0$ and $\delta(q)>0$. Since this property is invariant
by executing the transitions in $T_{0}$, we deduce that $\alpha(p)>0$ and
$\alpha(q)>0$. By executing $t_{\bar{p}}$ and $t_{\bar{q}}$ the right number
of times, we get from $\alpha$ a configuration $\beta$ such that
$\beta(\bar{i})=\beta(\bar{p})=\beta(\bar{q})=0$. This configuration is
$1$-output stable. We have proved that the protocol stably computes
$\phi_{i\geq n}$.

In (Blondin et al., 2018), it is exhibited an infinite set of natural numbers
$n$ for which there exists a conservative population protocol stably computing
the counting predicate $(i\geq n)$ with an interaction-width bounded by $2$, a
number of leaders bounded by $2$, and a number of states bounded by
$O(\log\log(n))$. This paper left open the optimality of that bound. In this
paper we show that such a bound is almost optimal by proving the following
main theorem.

###### Theorem 4.3.

For every protocol $(P,\xrightarrow{*},\rho_{L},I,F)$ with a finite
interaction-width that stably computes $\phi_{i\geq n}$, we have:

$n\leq(4+4\operatorname{width}(\xrightarrow{*})+2|\rho_{L}|)^{|P|^{(|P|+2)^{2}}}$

We deduce the following state complexity lower-bound as a corollary.

###### Corollary 4.4.

Let $h<\frac{1}{2}$ and let $m\geq 1$. The number of states of a protocol
stably computing the $(i\geq n)$ predicate with an interaction-width bounded
by $m$ and a number of leaders bounded by $m$ is at least
$\Omega((\log\log(n))^{h})$.

###### Proof.

Let us consider $\varepsilon>0$ such that $\frac{1}{2+\varepsilon}\geq h$.
Notice that for $d\in\mathbb{N}$ large enough, we have $d\leq
2^{(d+2)^{\varepsilon}}$. It follows that $d^{(d+2)^{2}}\leq
2^{(d+2)^{2+\varepsilon}}$ for $d$ large enough. Theorem 4.3 shows that a
protocol stably computing the $(i\geq n)$ predicate with an interaction-width
bounded by $m$ and a number of leaders bounded by $m$ satisfies:

$n\leq(10m)^{|P|^{(|P|+2)^{2}}}$

It follows that if $n$ is large enough, then $|P|$ is large enough to satisfy
$|P|^{(|P|+2)^{2}}\leq 2^{(|P|+2)^{2+\varepsilon}}$. It follows that
$\log\log(n)\leq\log\log(10m)+\log(2)(|P|+2)^{2+\varepsilon}$. In particular:

$|P|\geq\left(\frac{\log\log(n)-\log\log(10m)}{\log(2)}\right)^{h}-2$

We have proved the corollary. ∎

##  5\. Small Stable Configurations

A $P$-configuration $\rho$ is said to be _$(T,F)$ -stabilized_ where $T$ is a
$P$-Petri net, and $F$ is a subset of $P$ if for every configuration $\beta$
such that $\rho\xrightarrow{T^{*}}\beta$, we have $\beta(p)=0$ for every $p\in
P\backslash F$. In this section, we show that $(T,F)$-stabilized
configurations are characterized by “small values”. This result is obtained by
applying classical Rackoff’s techniques originally introduced for the Petri
net coverability problem. The definition of stabilized configurations is
related to the output stable configurations of protocols as shown by the
following lemma.

###### Lemma 5.1.

Let $(P,\xrightarrow{T^{*}},\rho_{L},I,\gamma)$ be a protocol where $T$ is a
Petri net and let
$F\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\gamma^{-1}(\\{0\\})$. A
configuration is $(T,F)$-stabilized if, and only if, it is $0$-output stable.

###### Proof.

By definition. ∎

We first introduce some notations. Given a $P$-configuration $\rho$, we
introduce
${\mathopen{\|}\rho\mathclose{\|}}_{\infty}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\max_{p\in
P}\rho(p)$. Given a transition $t=(\alpha_{t},\beta_{t})$, we also introduce
${\mathopen{\|}t\mathclose{\|}}_{\infty}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\max\\{{\mathopen{\|}\alpha_{t}\mathclose{\|}}_{\infty},{\mathopen{\|}\beta_{t}\mathclose{\|}}_{\infty}\\}$.
Given a Petri net $T$, we define
${\mathopen{\|}T\mathclose{\|}}_{\infty}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\max_{t\in
T}{\mathopen{\|}t\mathclose{\|}}_{\infty}$. Given a finite set $Q$ of states,
we define several restrictions related to $Q$ as follows. Let us recall that
given a $P$-configuration $\rho$, we previously defined $\rho|_{Q}$ as the
$Q$-configuration defined by
$\rho|_{Q}(q)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho(q)$ if
$q\in Q$, and zero otherwise. Given a $P$-transition
$t=(\alpha_{t},\beta_{t})$, we define the $Q$-transition $t|_{Q}$ as the pair
$t|_{Q}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(\alpha_{t}|_{Q},\beta_{t}|_{Q})$.
Given a $P$-Petri net $T$, we introduce the $Q$-Petri net
$T|_{Q}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{t|_{Q}\mid t\in
T\\}$. Given a word $\sigma=t_{1}\ldots t_{k}$ of $P$-transitions, we
introduce the word $\sigma|_{Q}=t_{1}|_{Q}\ldots t_{k}|_{Q}$ of
$Q$-transitions. Notice that $\alpha\xrightarrow{\sigma}\beta$ for some
$P$-configurations $\alpha,\beta$ implies
$\alpha|_{Q}\xrightarrow{\sigma|_{Q}}\beta|_{Q}$. The converse property is
true in some cases as shown by the following lemma.

###### Lemma 5.2.

Assume that $\alpha|_{Q}\xrightarrow{\sigma|_{Q}}\rho$ for some
$P$-configurations $\alpha,\rho$, some word $\sigma$ of transitions in a
$P$-Petri net $T$, and some finite set $Q$. If
$\alpha(p)\geq|\sigma|{\mathopen{\|}T\mathclose{\|}}_{\infty}$ for every $p\in
P\backslash Q$ then there exists a configuration $\beta$ such that
$\alpha\xrightarrow{\sigma}\beta$, $\beta|_{Q}=\rho$, and
$\beta(p)\geq\alpha(p)-|\sigma|{\mathopen{\|}T\mathclose{\|}}_{\infty}$ for
every $p\in P\backslash Q$.

###### Proof.

Simple induction on $|\sigma|$. ∎

A configuration $\rho$ is said to be _$T$ -coverable_ from a configuration
$\alpha$ where $T$ is a Petri net if there exists a word $\sigma\in T^{*}$
such that $\alpha\xrightarrow{\sigma}\beta\geq\rho$ for some configuration
$\beta$. The minimal length of such a word $\sigma$ can be bounded using
Rackoff’s techniques with respect to
${\mathopen{\|}\rho\mathclose{\|}}_{\infty}$,
${\mathopen{\|}T\mathclose{\|}}_{\infty}$, and $|Q|$ as shown by the following
result introduced in (Rackoff, 1978) to prove that the $T$-coverability
problem is decidable in exponential space.

###### Lemma 5.3 ((Rackoff, 1978)).

If a configuration $\rho$ is $T$-coverable from a configuration $\alpha$ where
$T$ is a $P$-Petri net, then there exists $\sigma\in T^{*}$ with a length
bounded by
$({\mathopen{\|}\rho\mathclose{\|}}_{\infty}+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{{|P|}^{|P|}}$,
and a configuration $\beta$ such that
$\alpha\xrightarrow{\sigma}\beta\geq\rho$.

###### Proof.

This is a classical result obtained by Rackoff in (Rackoff, 1978) by induction
on $|P|$. ∎

We deduce the following lemma that shows that $(T,F)$-stabilized
configurations are characterized by “small values” (the values $\rho(p)$ for
$p\in R$). In the statement of that lemma the relation $\leq$ over the
$P$-configurations is defined by $\alpha\leq\beta$ if there exists a
$P$-configuration $\rho$ such that $\beta=\alpha+\rho$.

###### Lemma 5.4.

Let $\rho$ be a $(T,F)$-stabilized $P$-configuration with $F\subseteq P$, let
$h$ be a positive integer satisfying
$h\geq{\mathopen{\|}T\mathclose{\|}}_{\infty}(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{{|P|}^{|P|}}$,
and let $R\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{p\in
P\mid\rho(p)<h\\}$. Every $P$-configuration $\alpha$ such that
$\alpha|_{R}\leq\rho|_{R}$ is $(T,F)$-stabilized.

###### Proof.

Let us consider a $P$-configuration $\alpha$ such that
$\alpha|_{R}\leq\rho|_{R}$. There exists a $R$-configuration $\mu$ such that
$\rho|_{R}=\alpha|_{R}+\mu$. Assume by contradiction that $\alpha$ is not
$(T,F)$-stabilized. It follows that there exists a configuration $\beta$ such
that $\alpha\xrightarrow{T^{*}}\beta$ and $\beta(p)>0$ for some place $p\in
P\backslash F$. Since $p\not\in F$ and $\rho$ is $(T,F)$-stabilized, we deduce
that $\rho(p)=0$. In particular $p\in R$ since $h>0$. Since $p|_{P}$ is
$T$-coverable from $\alpha$, Lemma 5.3 shows there exists a word $\sigma\in
T^{*}$ of length bounded by
$(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{{|P|}^{|P|}}$ and a
configuration $\eta$ such that $\alpha\xrightarrow{\sigma}\eta\geq p|_{P}$. It
follows that $\alpha|_{R}\xrightarrow{\sigma|_{R}}\eta|_{R}$. From this
relation and $\rho_{R}=\alpha|_{R}+\mu$, we deduce that
$\rho_{R}\xrightarrow{\sigma|_{R}}\eta|_{R}+\mu$. Lemma 5.2 shows that there
exists a configuration $\delta$ such that $\rho\xrightarrow{\sigma}\delta$ and
$\delta|_{R}=\eta|_{R}+\mu$. Since $p\in R$, we deduce that
$\delta(p)=\eta(p)+\mu(p)\geq p|_{P}(p)=1$. As $p\not\in F$, it follows that
$\rho$ is not $(T,F)$-stabilized and we get a contradiction. We have proved
the lemma. ∎

###### Remark 2.

A similar result was provided in (Czerner and Esparza, 2021) in the context of
conservative Petri nets with interaction-width bounded by two.

##  6\. Bottom Configurations

Let $T$ be a $P$-Petri net. The _$T$ -component_ of a $P$-configuration $\rho$
is the set of configurations $\beta$ such that
$\rho\xrightarrow{T^{*}}\beta\xrightarrow{T^{*}}\rho$. A configuration $\rho$
is said to be _$T$ -bottom_ if its $T$-component is finite and every
configuration $\beta$ such that $\rho\xrightarrow{T^{*}}\beta$ satisfies
$\beta\xrightarrow{T^{*}}\rho$.

In this section we prove the following theorem that intuitively provides a way
to reach with short words kind of bottom configurations with small size (small
and short meaning doubly-exponential in that context). Other results proved in
this section are only used for proving the following theorem and are no longer
used in the sequel.

###### Theorem 6.1.

Let $T$ be a $P$-Petri net, let $\rho$ be a $P$-configuration, and let
$b\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(4+4{\mathopen{\|}T\mathclose{\|}}_{\infty}+2{\mathopen{\|}\rho\mathclose{\|}}_{\infty})^{d^{d}(1+(2+d^{d})^{d+1})}$
with $d\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|P|$. There exist
two words $\sigma,w\in T^{*}$, a set of places $Q\subseteq P$, and two
$P$-configurations $\alpha,\beta$ such that:

  * •

$\rho\xrightarrow{\sigma}\alpha\xrightarrow{w}\beta$.

  * •

$\alpha|_{Q}=\beta|_{Q}$.

  * •

$\alpha(p)<\beta(p)$ for every state $p\in P\backslash Q$.

  * •

$\alpha|_{Q}$ is $T|_{Q}$-bottom.

  * •

The cardinal of the $T|_{Q}$-component of $\alpha|_{Q}$ is bounded by $b$.

  * •

$|\sigma|,|w|,d{\mathopen{\|}\alpha\mathclose{\|}}_{\infty},d{\mathopen{\|}\beta\mathclose{\|}}_{\infty}\leq
b$.

The proof of the previous theorem is obtained by iterating the following lemma
in order to obtain an increasing sequence of sets $Q$.

###### Lemma 6.2.

Let $T$ be a $P$-Petri net, let $\rho$ be a $P$-configuration, let $Q$ be a
set of states included in $P$ such that $\rho|_{Q}$ is $T|_{Q}$-bottom, let
$s$ be the cardinal of the $T|_{Q}$-component of $\rho|_{Q}$, and let
$d\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|P\backslash Q|$.

There exist a word $\sigma\in T^{*}$ such that
$|\sigma|\leq(1+d(1+s{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho\mathclose{\|}}_{\infty})^{d^{d}})s$,
and a $P$-configuration $\rho^{\prime}$ such that
$\rho\xrightarrow{\sigma}\rho^{\prime}$ and such that:

  * •

either $\rho^{\prime}|_{Q}=\rho|_{Q}$ and $\rho^{\prime}(p)>\rho(p)$ for every
$p\in P\backslash Q$,

  * •

or there exists a set $Q^{\prime}\subseteq P$ that strictly contains $Q$ such
that $\rho^{\prime}|_{Q^{\prime}}$ is $T|_{Q^{\prime}}$-bottom and the
cardinal $s^{\prime}$ of the $T|_{Q^{\prime}}$-component of
$\rho^{\prime}|_{Q^{\prime}}$ satisfies:

$s^{\prime}\leq(1+d(1+s{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho\mathclose{\|}}_{\infty})^{d^{d}})s$

###### Proof.

Let us introduce the sequence $\lambda_{1},\ldots,\lambda_{d}$ of natural
numbers satisfying
$\lambda_{d}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}1+s{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho\mathclose{\|}}_{\infty}$
and satisfying
$\lambda_{n}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}s\lambda_{n+1}^{d-n}{\mathopen{\|}T\mathclose{\|}}_{\infty}+\lambda_{n+1}$
for every $n\in\\{1,\ldots,d-1\\}$. Observe that
$\lambda_{1}\geq\cdots\geq\lambda_{d}$. Moreover,
$\lambda_{n}\leq\lambda_{d}\lambda_{n+1}^{d-n}$ for every $1\leq n<d$. We
deduce by induction that $\lambda_{1}^{d}\leq\lambda_{d}^{d^{d}}$.

Let $\rho_{0}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho$. We are
going to build by induction on $n$ a sequence $\rho_{1},\ldots,\rho_{n}$ of
configurations, a sequence $\sigma_{1},\ldots,\sigma_{n}$ of words in $T^{*}$,
and a sequence $p_{1},\ldots,p_{n}$ of states in $P\backslash Q$ such that for
every $i\in\\{1,\ldots,n\\}$ we have:

  * (i)

$\rho_{i-1}\xrightarrow{\sigma_{i}}\rho_{i}$.

  * (ii)

$|\sigma_{i}|\leq\lambda_{i}^{d-i+1}s$.

  * (iii)

$\rho_{i}(p)\geq\lambda_{i}$ for every $p\in\\{p_{1},\ldots,p_{i}\\}$.

So, let us assume that $\rho_{1},\ldots,\rho_{n}$,
$\sigma_{1},\ldots,\sigma_{n}$, and $p_{1},\ldots,p_{n}$ are built for some
$n\geq 0$. Since $p_{1},\ldots,p_{n}$ are distinct elements in $P\backslash
Q$, it follows that $n\leq d$.

Let us first assume that $n=d$. In that case, we have
$\rho_{d}(p)\geq\lambda_{d}$ for every $p\in P\backslash Q$. As $\rho|_{Q}$ is
a $T|_{Q}$-bottom configuration and
$\rho|_{Q}\xrightarrow{(\sigma_{1}\ldots\sigma_{d})|_{Q}}\rho_{d}|_{Q}$ and
since the cardinal of the $T|_{Q}$-component of $\rho|_{Q}$ is bounded by $s$,
we deduce that there exists a word $w\in T^{*}$ such that
$\rho_{d}|_{Q}\xrightarrow{w|_{Q}}\rho|_{Q}$ and $|w|<s$. Since
$\lambda_{d}\geq
s{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq|w|{\mathopen{\|}T\mathclose{\|}}_{\infty}$,
Lemma 5.2 shows that $\rho_{d}\xrightarrow{w}\rho^{\prime}$ for some
configuration $\rho^{\prime}$ such that $\rho^{\prime}|_{Q}=\rho|_{Q}$ and
such that for every $p\in P\backslash Q$ we have
$\rho^{\prime}(p)\geq\rho(p)-|w|{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq\lambda_{d}-s{\mathopen{\|}T\mathclose{\|}}_{\infty}>\rho(p)$
by definition of $\lambda_{d}$. Let us introduce
$\sigma\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sigma_{1}\ldots\sigma_{d}w$
and notice that
$|\sigma|\leq(\lambda_{1}^{d}+\cdots+\lambda_{d}^{d-d+1}+1)s\leq(1+d\lambda_{1}^{d})s$
and we have proved that the lemma holds (first case).

So we can assume that $n<d$. Let us introduce the set $R_{n}=(P\backslash
Q)\backslash\\{p_{1},\ldots,p_{n}\\}$. Since $|R_{n}|=d-n$, the set $R_{n}$ is
non empty.

Assume first that for every configuration $\beta$ such that
$\rho_{n}\xrightarrow{T^{*}}\beta$ we have $\beta(p)<\lambda_{n+1}$ for every
$p\in R_{n}$. In that case let
$Q^{\prime}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}Q\cup R_{n}$. It
follows that the cardinal of the set of configurations $\beta^{\prime}$ such
that $\rho_{n}|_{Q^{\prime}}\xrightarrow{T|_{Q^{\prime}}^{*}}\beta^{\prime}$
is bounded by $s\lambda_{n+1}^{d-n}$. Hence, there exists a configuration
$\beta^{\prime}$ that is $T|_{Q^{\prime}}$-bottom and a word $w\in T^{*}$ such
that $\rho_{n}|_{Q^{\prime}}\xrightarrow{w|_{Q^{\prime}}}\beta^{\prime}$ and
such that $|w|<s\lambda_{n+1}^{d-n}$. Notice that the cardinal $s^{\prime}$ of
the $T|_{Q^{\prime}}$-component of $\beta^{\prime}$ is bounded by
$s\lambda_{n+1}^{d-n}\leq s\lambda_{1}^{d}$. As $\rho_{n}(p)\geq\lambda_{n}$
for every $p\in\\{p_{1},\ldots,p_{n}\\}$ and
$\lambda_{n}\geq(s\lambda_{n+1}^{d-n}-1){\mathopen{\|}T\mathclose{\|}}_{\infty}\geq|w|{\mathopen{\|}T\mathclose{\|}}_{\infty}$,
Lemma 5.2 shows that there exists a configuration $\rho^{\prime}$ such that
$\rho_{n}\xrightarrow{w}\rho^{\prime}$, and
$\rho^{\prime}|_{Q^{\prime}}=\beta^{\prime}$. Let us consider the word
$\sigma\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sigma_{1}\ldots\sigma_{n}w$.
Notice that
$|\sigma|\leq(\lambda_{1}^{d}+\cdots+\lambda_{n}^{d-n+1}+\lambda_{n+1}^{d-n})s\leq
d\lambda_{1}^{d}s$ and we have proved that the lemma holds (second case).

Finally, assume that there exists a configuration $\rho_{n+1}$ such that
$\rho_{n}\xrightarrow{\sigma_{n+1}}\rho_{n+1}$ for some word $\sigma_{n+1}\in
T^{*}$ and such that $\rho_{n+1}(p_{n+1})\geq\lambda_{n+1}$ for some state
$p_{n+1}\in R_{n}$. We assume that $|\sigma_{n+1}|$ is minimal. Observe that
every intermediate configuration $\beta$ such that
$\rho_{n}\xrightarrow{u}\beta\xrightarrow{v}\rho_{n+1}$ with $uv=\sigma_{n+1}$
and $|v|\geq 1$ satisfies $\beta(p)<\lambda_{n+1}$ for every $p\in R_{n}$ by
minimality of $|\sigma_{n+1}|$. We deduce that there exists a word $w\in
T^{*}$ such that $\rho_{n}|_{Q\cup R_{n}}\xrightarrow{w|_{Q\cup
R_{n}}}\rho_{n+1}|_{Q\cup R_{n}}$ and such that $|w|\leq
s\lambda_{n+1}^{d-n}$. As $\rho_{n}(p)\geq\lambda_{n}$ for every
$p\in\\{p_{1},\ldots,p_{n}\\}$ and $\lambda_{n}\geq
s\lambda_{n+1}^{d-n}{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq|w|{\mathopen{\|}T\mathclose{\|}}_{\infty}$,
Lemma 5.2 shows that there exists a configuration $\beta$ such that
$\rho_{n}\xrightarrow{w}\beta$ and $\beta|_{Q\cup R_{n}}=\rho_{n+1}|_{Q\cup
R_{n}}$. In particular $\beta(p_{n+1})=\rho_{n+1}(p_{n+1})\geq\lambda_{n+1}$.
By minimality of $|\sigma_{n+1}|$, we get $|\sigma_{n+1}|\leq|w|\leq
s\lambda_{n+1}^{d-n}$. Now, observe that for every
$p\in\\{p_{1},\ldots,p_{n}\\}$ we have
$\rho_{n+1}(p)\geq\rho_{n}(p)-|\sigma_{n+1}|{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq\lambda_{n}-s\lambda_{n+1}^{d-n}{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq\lambda_{n+1}$
by definition of $\lambda_{n}$. We have extended our sequence in such a way
$(i)$, $(ii)$, and $(iii)$ are fulfilled.

We have proved the lemma. ∎

Now, let us prove Theorem 6.1. Observe that if $d=0$ the theorem is trivial.
So, we can assume that $d\geq 1$. Let
$Q_{0}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\emptyset$,
$\rho_{0}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho$, and
$s_{0}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}1$. Notice that
$\rho_{0}|_{Q_{0}}$ is $T|_{Q_{0}}$-bottom and the cardinal of the
$T|_{Q_{0}}$-component of $\rho_{0}|_{Q_{0}}$ contains $s_{0}$ elements. We
build by induction on $n$ a sequence $Q_{1},\ldots,Q_{n}$ of subsets of $P$, a
sequence $\rho_{1},\ldots,\rho_{n}$ of configurations, a sequence
$\sigma_{1},\ldots,\sigma_{n}$ of words in $T^{*}$ such that for every
$i\in\\{1,\ldots,n\\}$:

  * •

$\rho_{i-1}\xrightarrow{\sigma_{i}}\rho_{i}$.

  * •

$\rho_{i}|_{Q_{i}}$ is $T|_{Q_{i}}$-bottom.

  * •

The cardinal of the $T|_{Q_{i}}$-component of $\rho_{i}|_{Q_{i}}$ is equal to
$s_{i}$.

  * •

$Q_{i-1}\subset Q_{i}$.

  * •

$|\sigma_{i}|,s_{i}\leq(1+d(1+s_{i-1}{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho_{i-1}\mathclose{\|}}_{\infty})^{d^{d}})s_{i-1}$.

Assume the sequence built for some $n\geq 0$. Lemma 6.2 on the configuration
$\rho_{n}$ and the set $Q_{n}$ shows that there exist a word $\sigma_{n+1}$
such that
$|\sigma_{n+1}|\leq(1+d(1+s_{n}{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho_{n}\mathclose{\|}}_{\infty})^{d^{d}})s_{n}$,
and a configuration $\rho_{n+1}$ such that
$\rho_{n}\xrightarrow{\sigma_{n}}\rho_{n+1}$, such that:

  * •

either $\rho_{n+1}|_{Q_{n}}=\rho_{n}|_{Q_{n}}$ and $\rho_{n+1}(p)>\rho_{n}(p)$
for every $p\in P\backslash Q_{n}$,

  * •

or there exists $Q_{n+1}$ such that $Q_{n}\subset Q_{n+1}\subseteq P$ such
that $\rho_{n+1}|_{Q_{n+1}}$ is $T|_{Q_{n+1}}$-bottom and the cardinal
$s_{n+1}$ of its $T|_{Q_{n+1}}$-component satisfies:

$s_{n+1}\leq(1+d(1+s_{n}{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho_{n}\mathclose{\|}}_{\infty})^{d^{d}})s_{n}$

Observe that in the second case we have extended the sequences. In the first
case, let $\alpha\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho_{n}$,
$\beta\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho_{n+1}$,
$\sigma\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sigma_{1}\ldots\sigma_{n}$,
$w\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sigma_{n+1}$, and
$Q\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}Q_{n}$. Since
$Q_{0}\subset Q_{1}\cdots\subset Q_{n}$ are subsets of $P$, we deduce that
$n\leq d$. Let us introduce
$a=(1+d)(2+2{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho\mathclose{\|}}_{\infty})^{d^{d}}$
and $h=2+d^{d}$ and let us prove by induction on $i$ that we have
$|\sigma_{i}|,|s_{i}|\leq a^{h^{i}}$ and
${\mathopen{\|}\rho_{i}\mathclose{\|}}_{\infty}\leq(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})a^{h^{i}}$
with the convention $\sigma_{0}=\varepsilon$.

The rank $i=0$ is immediate. Assume the rank $i-1$ proved. We have:

$\displaystyle|\sigma_{i}|,s_{i}$
$\displaystyle\leq(1+d(1+s_{i-1}{\mathopen{\|}T\mathclose{\|}}_{\infty}+{\mathopen{\|}\rho_{i-1}\mathclose{\|}}_{\infty})^{d^{d}})s_{i-1}$
$\displaystyle\leq(1+d)(2+2{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d^{d}}a^{h^{i-1}(d^{d}+1)}$
$\displaystyle\leq a^{1+h^{i-1}(h-1)}$ $\displaystyle\leq a^{h^{i}}$

Since $\rho_{i-1}\xrightarrow{\sigma_{i}}\rho_{i}$, we deduce that
${\mathopen{\|}\rho_{i}\mathclose{\|}}_{\infty}\leq{\mathopen{\|}\rho_{i-1}\mathclose{\|}}_{\infty}+|\sigma_{i}|{\mathopen{\|}T\mathclose{\|}}_{\infty}\leq(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})a^{h^{i}}$.
The induction is proved.

It follows that $|\sigma|\leq da^{h^{d}}$, $|w|\leq a^{h^{d+1}}$, and
$d{\mathopen{\|}\alpha\mathclose{\|}}_{\infty},d{\mathopen{\|}\beta\mathclose{\|}}_{\infty}\leq
d(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})a^{h^{d+1}}\leq a^{1+h^{d+1}}$.
Since $d\geq 1$, we deduce that $(1+d)\leq 2^{d^{d}}$. In particular
$a\leq(4+4{\mathopen{\|}T\mathclose{\|}}_{\infty}+2{\mathopen{\|}\rho\mathclose{\|}}_{\infty})^{d^{d}}$.
We have proved Theorem 6.1.

##  7\. Petri Nets with Control-States

A _$P$ -Petri net with control-states_ (or simply a Petri net with control-
states when the finite set of states $P$ is clear from the context) is a
triple $(S,T,E)$ where $S$ is a non empty finite set of elements called
_control-states_ , $T$ is a $P$-Petri net, and $E\subseteq S\times T\times S$
is a set of elements called _edges_. The _Parikh image_ of a word
$\pi=e_{1}\ldots e_{k}$ of edges is the mapping $\\#\pi\in\mathbb{N}^{E}$
defined by $\\#\pi(e)=|\\{j\in\\{1,\ldots,k\\}\mid e_{j}=e\\}|$. The
_displacement_ of a transition $t=(\alpha_{t},\beta_{t})$ is the function
$\Delta(t)\in\mathbb{Z}^{P}$ defined by
$\Delta(t)(p)=\beta_{t}(p)-\alpha_{t}(p)$ for every $p\in P$. The
_displacement_ of an edge $e=(s,t,s^{\prime})$ is defined as
$\Delta(e)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\Delta(t)$. The
displacement of a word $\pi=e_{1}\ldots e_{k}$ of edges is
$\Delta(\pi)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{1\leq
j\leq k}\Delta(e_{j})$. We denote by
$|\pi|\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}k$ the _length_ of
$\pi$. A _path_ $\pi$ from a control-state $s$ to a control-state $s^{\prime}$
is a word $\pi=e_{1}\ldots e_{k}$ of edges in $E$ such that there exists
control-states $s_{0},\ldots,s_{k}$ in $S$ and transitions
$t_{1},\ldots,t_{k}$ in $T$ such that $s_{0}=s$, $s_{k}=s^{\prime}$, and such
that $e_{j}=(s_{j-1},t_{j},s_{j})$ for every $1\leq j\leq k$. Such a path is
called a _cycle_ if $s=s^{\prime}$. A cycle $\theta$ of a Petri net with
control-states is said to be _total_ if $\\#\theta(e)>0$ for every $e\in E$.
The cycle is said to be _simple_ if the control-states $s_{1},\ldots,s_{k}$
are distinct. A _multicycle_ $\Theta$ is a sequence
$\theta_{1},\ldots,\theta_{k}$ of cycles. We denote by
$|\Theta|\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{j=1}^{k}|\theta_{j}|$,
the _length_ of a multicycle $\Theta$. We introduce the _Parikh image_
$\\#\Theta\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{j=1}^{k}\\#\theta_{j}$
and the _displacement_
$\Delta(\Theta)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{j=1}^{k}\Delta(\theta_{j})$
of such a multicycle $\Theta$. A multicycle $\Theta$ is said to be _total_ if
$\\#\Theta(e)>0$ for every $e\in E$.

A _Petri net with control-states_ $(S,T,E)$ is said to be _strongly connected_
if for every pair $(s,s^{\prime})$ of control-states in $S$, there exists a
path from $s$ to $s^{\prime}$. Let us recall the classical Euler lemma in the
context of Petri nets with control-states.

###### Lemma 7.1 (Euler Lemma).

For every total multicycle $\Theta$ in a strongly connected Petri net with
control-states there exists a total cycle $\theta$ such that
$\\#\theta=\\#\Theta$.

We deduce the following lemma.

###### Lemma 7.2.

For any strongly connected Petri net with control-states $(S,T,E)$, there
exists a total cycle $\theta$ with a length bounded by $|E||S|$.

###### Proof.

Every edge $e\in E$ occurs in at least one simple cycle $\theta_{e}$. It
follows that the multicycle $\Theta=(\theta_{e})_{e\in E}$ is total. From
Lemma 7.1 we deduce that there exists a total cycle $\theta$ such that
$\\#\theta=\\#\Theta$. Notice that $|\theta|=\sum_{e\in
E}|\theta_{e}|\leq|E||S|$. ∎

A mapping $a\in\mathbb{Z}^{P}$ is called a _$P$ -action_ (or simply an action
if $P$ is clear from the context). Notice that displacements of transitions,
edges, paths, and multicyles are actions. We associate with an action $a$ the
value
${\mathopen{\|}a\mathclose{\|}}_{1}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{p\in
P}|a(p)|$. Given a finite set $Q$, we denote by $a|_{Q}$ the action defined
for every $q\in Q$ by
$a|_{Q}(q)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}a(q)$ if $q\in
P$, and zero otherwise.

###### Lemma 7.3.

Let $\Theta$ be a multicycle of a $P$-Petri net with control-states $(S,T,E)$
with ${\mathopen{\|}T\mathclose{\|}}_{\infty}>0$, let $Q\subseteq P$, let
$d\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|P|$, and let
$k>{\mathopen{\|}\Delta(\Theta)|_{Q}\mathclose{\|}}_{1}(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$.

There exists a multicycle $\Theta^{\prime}$ such that:

  * •

For every $p\in P$ we have:

    * –

$\Delta(\Theta^{\prime})(p)\leq 0$ if $\Delta(\Theta)(p)\leq 0$.

    * –

$\Delta(\Theta^{\prime})(p)<0$ if $\Delta(\Theta)(p)\leq-k$.

    * –

$\Delta(\Theta^{\prime})(p)\geq 0$ if $\Delta(\Theta)(p)\geq 0$.

    * –

$\Delta(\Theta^{\prime})(p)>0$ if $\Delta(\Theta)(p)\geq k$.

  * •

For every $q\in Q$ we have $\Delta(\Theta^{\prime})(q)=0$.

  * •

For every edge $e\in E$ we have $\\#\Theta^{\prime}(e)>0$ if $\\#\Theta(e)\geq
k$.

  * •

$|\Theta^{\prime}|\leq(|E|+d)(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$.

###### Proof.

Since every cycle can be decomposed into a sequence of simple cycles without
changing the Parikh image, we can assume without loss of generality that
$\Theta$ is a sequence of simple cycles. We introduce the set $A$ of actions
$\Delta(\theta)$ where $\theta$ ranges over the simple cycles, and
$n\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|A|$ its cardinal. Notice
that for every $a\in A$ and for every $p\in P$, we have
$|a(p)|\leq|S|{\mathopen{\|}T\mathclose{\|}}_{\infty}$. It follows that
$n\leq(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d}$.

We denote by $s$ the sign function of $a$ formally defined by
$s(c)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}1$ if
$\Delta(\Theta)(c)\geq 0$,
$s(c)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}-1$ otherwise. We also
introduce the $P$-configuration $f$ defined by
$f(p)\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|\Delta(\Theta)(p)|$
for every $p\in P$, and the function $g:A\rightarrow\mathbb{N}$ such that
$g(a)$ is the number of simple cycle $\theta$ that occurs in $\Theta$ such
that $\Delta(\theta)=a$.

Notice that $s(p)f(p)=\sum_{a\in A}g(a)a(p)$ for every $p\in P$. We introduce
the following linear system over the free variables
$(\alpha,\beta)\in\mathbb{N}^{P}\times\mathbb{N}^{A}$:

(1) $\bigwedge_{p\in P}s(p)\alpha(p)=\sum_{a\in A}\beta(a)a(p)$

Notice that $(f,g)$ is a solution of that system. From (Pottier, 1991), there
exists a finite set $H$ of solutions $(\alpha,\beta)$ of that system such that
$(f,g)=\sum_{(\alpha,\beta)\in H}(\alpha,\beta)$ and such that for every
$(\alpha,\beta)\in H$, we have
${\mathopen{\|}\alpha\mathclose{\|}}_{1}+{\mathopen{\|}\beta\mathclose{\|}}_{1}\leq(2+\sum_{a\in
A}{\mathopen{\|}a\mathclose{\|}}_{\infty})^{d}$. As $\sum_{a\in
A}{\mathopen{\|}a\mathclose{\|}}_{\infty}\leq(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d}|S|{\mathopen{\|}T\mathclose{\|}}_{\infty}$
we deduce (by using $|S|{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq 1$):

(2)
${\mathopen{\|}\alpha\mathclose{\|}}_{1}+{\mathopen{\|}\beta\mathclose{\|}}_{1}\leq(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$

We introduce the set $H_{0}$ of pairs $(\alpha,\beta)\in H$ such that
$\alpha(q)=0$ for every $q\in Q$. Observe that $\sum_{q\in
Q}\sum_{(\alpha,\beta)\in H}\alpha(q)$ is equal to $\sum_{q\in
Q}|\Delta(\Theta)(q)|={\mathopen{\|}\Delta(\Delta)|_{Q}\mathclose{\|}}_{1}$,
and it is also equals to $\sum_{q\in Q}\sum_{(\alpha,\beta)\in H\backslash
H_{0}}\alpha(q)\geq|H\backslash H_{0}|$. In particular we have:

$|H\backslash H_{0}|\leq{\mathopen{\|}\Delta(\Delta)|_{Q}\mathclose{\|}}_{1}$

We introduce the set $F$ of edges $e\in E$ such that $\Theta(e)\geq k$. Let
$e\in F$. The sum $\sum_{(\alpha,\beta)\in H}\beta(e)$ is equals to
$\\#\Theta(e)$ and it is also equals to $\sum_{(\alpha,\beta)\in H\backslash
H_{0}}\beta(e)+\sum_{(\alpha,\beta)\in H_{0}}\beta(e)$. As
$\sum_{(\alpha,\beta)\in H\backslash H_{0}}\beta(e)\leq|H\backslash
H_{0}|(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$ we deduce that
$\sum_{(\alpha,\beta)\in H_{0}}\beta(e)>0$. In particular there exists
$(\alpha,\beta)\in H_{0}$ such that $\beta(e)>0$.

We also introduce the set $R$ of $p\in P$ such that $|\Delta(\Theta)(p)|\geq
k$. Let $p\in R$. The sum $\sum_{(\alpha,\beta)\in H}\alpha(p)$ is equals to
$|\Delta(\Theta)(p)|$ and it is also equals to $\sum_{(\alpha,\beta)\in
H\backslash H_{0}}\alpha(p)+\sum_{(\alpha,\beta)\in H_{0}}\alpha(p)$. As
$\sum_{(\alpha,\beta)\in H\backslash H_{0}}\alpha(p)\leq|H\backslash
H_{0}|(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$ we deduce that
$\sum_{(\alpha,\beta)\in H_{0}}\alpha(p)>0$. In particular there exists
$(\alpha,\beta)\in H_{0}$ such that $\alpha(p)>0$.

Now, let us introduce for each $e\in F$ a pair $(\alpha_{e},\beta_{e})\in
H_{0}$ such that $\beta_{e}(e)>0$, and let us introduce for each $p\in R$ a
pair $(\alpha_{p},\beta_{p})\in H_{0}$ such that $\alpha_{p}(p)>0$. Let us
introduce
$(\alpha^{\prime},\beta^{\prime})\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\sum_{e\in
F}(\alpha_{e},\beta_{e})+\sum_{p\in R}(\alpha_{p},\beta_{p})$ and observe that
$\alpha^{\prime}(e)>0$ for every $e\in F$, $\beta^{\prime}(p)>0$ for every
$p\in R$, and $\beta^{\prime}(q)=0$ for every $q\in Q$. Moreover, since
$(\alpha^{\prime},\beta^{\prime})$ is a solution of (1), it follows that there
exists a multicycle $\Theta^{\prime}$ such that
$\\#\Theta^{\prime}=\beta^{\prime}$. In particular
$\Delta(\Theta^{\prime})=\Delta(\beta^{\prime})$. Notice that
$\Delta(\Theta^{\prime})=\alpha^{\prime}$, and
$|\Theta^{\prime}|={\mathopen{\|}\beta^{\prime}\mathclose{\|}}_{1}\leq(|F|+|R|)(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}\leq(|E|+d)(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$
and we have proved the lemma. ∎

##  8\. Proof of Theorem 4.3

In this section we provide a proof of Theorem 4.3.

We consider a finite interaction-width protocols
$(P,\xrightarrow{*},\rho_{L},I,\gamma)$ that stably computes the $(n>i)$
predicate. Notice that $I=\\{i\\}$. We introduce the Petri net
$T\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{t\in\xrightarrow{*}\mid\operatorname{width}(t)\leq\operatorname{width}(\xrightarrow{*})\\}$.
Let us recall that the additive preorder $\xrightarrow{*}$ is equal to
$\xrightarrow{T^{*}}$. Let
$d\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}|Q|$ and
$F=\gamma^{-1}(\\{0\\})$. Notice that if $d=1$ then $n=1$ and the proof of the
theorem is done in that case. So, we can assume that $d\geq 2$. We introduce
the following numbers:

$\displaystyle b$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}(4+4{\mathopen{\|}T\mathclose{\|}}_{\infty}+2{\mathopen{\|}\rho_{L}\mathclose{\|}}_{\infty})^{(d-1)^{d-1}(1+(2+(d-1)^{d-1})^{d})}$
$\displaystyle h$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}d(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})b$
$\displaystyle k$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}dh^{d^{2}+d+1}$
$\displaystyle a$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}h^{2d+3}$
$\displaystyle\ell$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}h^{5d^{2}}$
$\displaystyle r$
$\displaystyle\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}2(d-1)^{d-1}(1+(2+(d-1)^{d-1})^{d})(5d^{2}+2d+4)$

We introduce
${P^{\prime}}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}P\backslash
I$. It follows that $|{P^{\prime}}|=d-1$. Theorem 6.1 applied on the Petri net
$T|_{P^{\prime}}$ and the configuration $\rho_{L}|_{P^{\prime}}$ shows that
there exist two words $\sigma,w\in T^{*}$, a set $Q\subseteq{P^{\prime}}$, and
two configurations $\alpha,\beta$ such that:

  * •

$\rho_{L}|_{P^{\prime}}\xrightarrow{\sigma|_{P^{\prime}}}\alpha\xrightarrow{w|_{P^{\prime}}}\beta$.

  * •

$\alpha|_{Q}=\beta|_{Q}$.

  * •

$\alpha(p)<\beta(p)$ for every $p\in{P^{\prime}}\backslash Q$

  * •

$\alpha|_{Q}$ is $T|_{Q}$-bottom.

  * •

The cardinal of the $T|_{Q}$-component of $\alpha|_{Q}$ is bounded by $b$.

  * •

$|\sigma|,|w|,d{\mathopen{\|}\alpha\mathclose{\|}}_{\infty},d{\mathopen{\|}\beta\mathclose{\|}}_{\infty}\leq
b$.

Notice that $|T|\leq(1+2{\mathopen{\|}T\mathclose{\|}}_{\infty})^{2d}\leq
h^{2d}$.

We introduce the Petri net with control-states $(S,T,E)$ where $S$ is the
$T|_{Q}$-component of $\alpha|_{Q}$, and $E$ is the set of edges
$(s,t,s^{\prime})\in S\times T\times S$ such that
$s\xrightarrow{t|_{Q}}s^{\prime}$. Observe that $|E|\leq|S||T|$ since for
every $(s,t,s^{\prime})$ in $E$ the value of $s^{\prime}$ is determined by the
pair $(s,t)$. It follows that we have:

$|E|\leq h^{2d+1}$

Lemma 7.2 shows that there exists a total cycle $\theta_{E}$ of $(S,T,E)$ with
a length bounded by $|S||E|$. Without loss of generality we can assume that
this total cycle is on the control-state $\alpha|_{Q}$ by considering a
rotation of that cycle. We denote by $\sigma_{E}$ the label in $T^{*}$ of this
total cycle. Observe that
${\mathopen{\|}T\mathclose{\|}}_{\infty}|\sigma_{E}|\leq a$.

Since $\alpha\xrightarrow{w|_{P^{\prime}}}\beta$, $\alpha|_{Q}=\beta|_{Q}$,
and $\alpha(p)<\beta(p)$ for every $p\in{P^{\prime}}\backslash Q$, we deduce
that there exists a configuration $\eta$ such that $\eta(p)\geq a\ell$ for
every $p\in{P^{\prime}}\backslash Q$, such that $\alpha|_{Q}=\eta|_{Q}$, and
such that:

$\alpha\xrightarrow{w^{a\ell}|_{P^{\prime}}}\eta$

Moreover, since $\sigma_{E}$ is the label of a cycle on $\alpha|_{Q}$ we
deduce that $\alpha|_{Q}\xrightarrow{\sigma_{E}|_{Q}}\alpha|_{Q}$. From
$\eta|_{Q}=\alpha|_{Q}$ it follows that
$\eta|_{Q}\xrightarrow{\sigma_{E}^{\ell}|_{Q}}\alpha|_{Q}$. As $\eta(p)\geq
a\ell\geq{\mathopen{\|}T\mathclose{\|}}_{\infty}|\sigma_{E}^{\ell}|$ for every
$p\in{P^{\prime}}\backslash Q$, Lemma 5.2 shows that there exists a
$P^{\prime}$-configuration $\delta$ such that $\delta|_{Q}=\alpha|_{Q}$ and
such that:

$\eta\xrightarrow{\sigma_{E}^{\ell}|_{P^{\prime}}}\delta$

Observe that $|\sigma
w^{a\ell}\sigma_{E}^{\ell}|{\mathopen{\|}T\mathclose{\|}}_{\infty}\leq(b+ba\ell){\mathopen{\|}T\mathclose{\|}}_{\infty}+a\ell\leq
2ba\ell({\mathopen{\|}T\mathclose{\|}}_{\infty}+1)\leq a\ell h\leq
h^{2d+4}\ell$.

Assume by contradiction that $n>h^{2d+4}\ell$, and let us introduce the
configuration $\rho^{\prime}$ defined by
$\rho^{\prime}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\rho_{L}+(n-1).i$
where $i$ is the state such that $I=\\{i\\}$. Lemma 5.2 shows that there exist
$P$-configurations $\alpha^{\prime},\eta^{\prime},\delta^{\prime}$ such that
$\alpha^{\prime}|_{P^{\prime}}=\alpha$, $\eta^{\prime}|_{P^{\prime}}=\eta$,
$\delta^{\prime}|_{P^{\prime}}=\delta$ and such that:

$\rho^{\prime}\xrightarrow{\sigma}\alpha^{\prime}\xrightarrow{w^{\alpha\ell}}\eta^{\prime}\xrightarrow{\sigma_{E}^{\ell}}\delta^{\prime}$

Since the population protocol is stably computing the $(i\geq n)$ predicate
and $n-1<n$, there exists a $0$-output stable configuration $\mu$ and a word
$\sigma^{\prime}\in T^{*}$ such that
$\delta^{\prime}\xrightarrow{\sigma^{\prime}}\mu$. Lemma 5.1 shows that $\mu$
is $(T,F)$-stabilized. Observe that
$w^{\alpha\ell}\sigma_{E}^{\ell}\sigma^{\prime}$ is the label of a path of
$(S,T,E)$ from $\alpha|_{Q}$ to $\mu|_{Q}$. It follows that the Parikh image
of that path can be decomposed as the Parikh image of a multicycle $\Theta$
and the Parikh image of an elementary path $\pi$. Observe
$\Delta(\Theta)+\Delta(\pi)=\Delta(w^{\alpha\ell}\sigma_{E}^{\ell}\sigma^{\prime})=\mu-\alpha^{\prime}$.
Notice that $\\#\Theta(e)\geq\ell$ for every $e\in E$ since $\sigma_{E}$ is
the label of a total cycle on $\alpha|_{Q}$. Since $\pi$ is an elementary
path, we deduce that ${\mathopen{\|}\Delta(\pi)\mathclose{\|}}_{1}\leq
d|S|{\mathopen{\|}T\mathclose{\|}}_{\infty}\leq
db{\mathopen{\|}T\mathclose{\|}}_{\infty}\leq h-db$.

We introduce the set
$R\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}\\{p\in
P\mid\mu(p)<h\\}$. Since
$h\geq{\mathopen{\|}T\mathclose{\|}}_{\infty}(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d^{d}}$,
Lemma 5.4 shows that every configuration $\mu^{\prime}$ such that
$\mu|_{R}=\mu^{\prime}|_{R}$ is $(T,F)$-stabilized. Observe that if $i\not\in
R$ then $\mu+i$ is $(T,F)$-stabilized, and by additivity, we deduce that
$\rho_{L}+n.i\xrightarrow{T^{*}}\mu+i$. Since $\mu+i$ is $(T,F)$-stabilized,
this configuration cannot reach a $1$-output stable configuration. In
particular the protocol is not stably computing the $(i\geq n)$ predicate and
we get a contradiction. It follows that $i\in R$.

We introduce
$R^{\prime}\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}R\backslash I$.
Since $d{\mathopen{\|}\alpha\mathclose{\|}}_{\infty}\leq b$ and
$\alpha^{\prime}|_{P^{\prime}}=\alpha|_{P^{\prime}}$, we deduce that
$d{\mathopen{\|}\alpha^{\prime}|_{R^{\prime}}\mathclose{\|}}_{\infty}\leq b$.
From $\Delta(\Theta)=\mu-\alpha^{\prime}-\Delta(\pi)$ we deduce:

${\mathopen{\|}\Delta(\Theta)|_{R^{\prime}}\mathclose{\|}}_{1}\leq(d-1)h+b+h-db\leq
dh$

As $1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty}\leq 1+h-2b<h$, we deduce
that
$k>{\mathopen{\|}\Delta(\Theta)|_{R^{\prime}}\mathclose{\|}}_{1}(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$,
Lemma 7.3 shows that there exists a multicycle $\Theta^{\prime}$ such that:

  * •

For every $p\in P$ we have:

    * –

$\Delta(\Theta^{\prime})(p)\leq 0$ if $\Delta(\Theta)(p)\leq 0$.

    * –

$\Delta(\Theta^{\prime})(p)<0$ if $\Delta(\Theta)(p)\leq-k$.

    * –

$\Delta(\Theta^{\prime})(p)\geq 0$ if $\Delta(\Theta)(p)\geq 0$.

    * –

$\Delta(\Theta^{\prime})(p)>0$ if $\Delta(\Theta)(p)\geq k$.

  * •

For every $p\in R^{\prime}$ we have $\Delta(\Theta^{\prime})(p)=0$.

  * •

For every $e\in E$ we have $\\#\Theta^{\prime}(e)>0$ if $\\#\Theta(e)\geq k$.

  * •

${\mathopen{\|}\Theta^{\prime}\mathclose{\|}}_{1}\leq(|E|+d)(1+2|S|{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$

Let
$m\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}-\Delta(\Theta^{\prime})(i)$
and let us prove that $m>0$. We have
$\Delta(\Theta)(i)=\mu(i)-\alpha^{\prime}(i)-\Delta(\pi)(i)$. Since $i\in R$,
we get $\mu(i)<h$. Since
$\rho_{L}+(n-1).i\xrightarrow{\sigma}\alpha^{\prime}$, we deduce that
$\alpha^{\prime}(i)=\rho_{L}(i)+(n-1)-\Delta(\sigma)(i)\geq n-h$ since
$|\sigma|\leq b$. We deduce that $\Delta(\Theta)(i)<h-n+h+h\leq 3h-n\leq-k$.
Hence $\Delta(\Theta^{\prime})(i)<0$. It follows that $m>0$.

Let
$\eta\stackrel{{\scriptstyle\textrm{{\tiny{def}}}}}{{=}}m.i+\Delta(\Theta^{\prime})$.
Notice that $\eta(i)=0$ and $\eta(p)=0$ for every $p\in R^{\prime}$. In
particular $\eta(p)=0$ for every $p\in R$. Let us prove that $\eta$ is a
configuration. For every $p\in P\backslash R$ we have
$\Delta(\Theta)(p)=\mu(p)-\eta^{\prime}(p)-\Delta(\pi)(p)\geq
db{\mathopen{\|}T\mathclose{\|}}_{\infty}+b-b-
db{\mathopen{\|}T\mathclose{\|}}_{\infty}\geq 0$. It follows that
$\Delta(\Theta^{\prime})(p)\geq 0$. In particular $\eta(p)\geq 0$. We have
proved that $\eta$ is a configuration.

Finally, observe that $\\#\Theta(e)\geq\ell\geq k$ for every $e\in E$. In
particular $\\#\Theta^{\prime}(e)>0$. Lemma 7.1 shows that
$\\#\Theta^{\prime}$ is the Parikh image of a cycle $\theta$ on $x|_{Q}$. Let
$u$ be the label of that cycle. Since
$|u|={\mathopen{\|}\Theta^{\prime}\mathclose{\|}}_{1}$, we deduce that:

$\displaystyle|u|{\mathopen{\|}T\mathclose{\|}}_{\infty}$
$\displaystyle\leq{\mathopen{\|}T\mathclose{\|}}_{\infty}(|E|+d)(1+2b{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d(d+1)}$
$\displaystyle\leq
d(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{2d}(1+2b{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d^{2}+d+1}$
$\displaystyle\leq\ell$

Lemma 5.2 shows that:

$\eta^{\prime}+m.i\xrightarrow{u}\eta^{\prime}+\eta$

We have proved:

$\rho_{L}+(n-1+m).i\xrightarrow{\sigma
w^{a\ell}u\sigma_{E}^{\ell}\sigma^{\prime}}\mu+\eta$

Since $(\mu+\eta)|_{R}=\mu|_{R}$ we deduce that $\mu+\eta$ is
$(T,F)$-stabilized. It follows that this configuration cannot reach a
$1$-output stable configuration. In particular the protocol is not stably
computing the $(i\geq n)$ predicate and we get a contradiction. It follows
that $n\leq h^{2d+4}\ell=h^{5d^{2}+2d+4}$.

Notice that $d(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})\leq
2^{d}(1+{\mathopen{\|}T\mathclose{\|}}_{\infty})^{d}\leq b$. Thus $h\leq
b^{2}$. We deduce that
$n\leq(4+4{\mathopen{\|}T\mathclose{\|}}_{\infty}+2{\mathopen{\|}\rho_{L}\mathclose{\|}}_{\infty})^{r}$.
Since $d\geq 2$, we deduce that
$d^{d}=((d-1)+1)^{d}\geq(d-1)^{d}+d(d-1)^{d-1}+1\geq(d-1)^{d-1}+2+1$. Hence
$1+(2+(d-1)^{d-1})^{d}\leq 1+(d^{d}-1)^{d}\leq d^{d^{2}}$. Moreover,
$2(d-1)^{d-1}\leq d^{d}$. Notice that $2d\leq d^{2}$ and $4\leq d^{2}$. Hence
$5d^{2}+2d+4\leq 7d^{2}\leq d^{5}$ since $7\leq d^{3}$. We deduce that $r$ is
bounded by $d^{d^{2}+d+3}$. As $d^{2}+d+3\leq(d+2)^{2}$, we get $r\leq
d^{(d+2)^{2}}$.

We have proved Theorem 4.3 just by observing that
${\mathopen{\|}\rho_{L}\mathclose{\|}}_{\infty}\leq|\rho_{L}|$ and
${\mathopen{\|}T\mathclose{\|}}_{\infty}\leq\operatorname{width}(\xrightarrow{*})$.

##  9\. Conclusion

This paper introduces protocols that allow agents destructions/creations and
leaders. Our definition of stably computing is a straight-forward extension of
the one introduced by Dana Angluin, James Aspnes, and David Eisenstat in
(Angluin et al., 2006a).

We provided in this paper state complexity lower-bounds of the form
$\Omega(\log\log(n)^{h})$ for any $h<\frac{1}{2}$ for protocols stably
computing the counting predicates when the number of leaders and the
interaction-width are bounded. This lower-bound almost matches the upper-bound
$O(\log\log(n))$ introduced in (Blondin et al., 2018) by Blondin, Esparza, and
Jaax. We left as open the exact asymptotic state complexity.

Notice that for leaderless protocols, the state complexity is still open since
there is an exponential gap between the upper-bound $O(\log(n))$ given in
(Blondin et al., 2018) and the lower-bound introduced in this paper.

###### Acknowledgements.

The author is supported by the grant ANR-17-CE40-0028 of the French National
Research Agency ANR (project BRAVAS)

## References

  * (1)
  * Angluin et al. (2004) Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2004\.  Computation in networks of passively mobile finite-state sensors. In _Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004_ , Soma Chaudhuri and Shay Kutten (Eds.). ACM, 290–299.  https://doi.org/10.1145/1011767.1011810
  * Angluin et al. (2006b) Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2006b.  Computation in networks of passively mobile finite-state sensors.  _Distributed Comput._ 18, 4 (2006), 235–253.  https://doi.org/10.1007/s00446-005-0138-3
  * Angluin et al. (2006a) Dana Angluin, James Aspnes, and David Eisenstat. 2006a.  Stably computable predicates are semilinear. In _Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006_ , Eric Ruppert and Dahlia Malkhi (Eds.). ACM, 292–299.  https://doi.org/10.1145/1146381.1146425
  * Angluin et al. (2007) Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. 2007.  The computational power of population protocols.  _Distributed Comput._ 20, 4 (2007), 279–304.  https://doi.org/10.1007/s00446-007-0040-2
  * Blondin et al. (2020) Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. 2020.  Succinct Population Protocols for Presburger Arithmetic. In _37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France_ _(LIPIcs, Vol. 154)_ , Christophe Paul and Markus Bläser (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 40:1–40:15.  https://doi.org/10.4230/LIPIcs.STACS.2020.40
  * Blondin et al. (2018) Michael Blondin, Javier Esparza, and Stefan Jaax. 2018\.  Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In _35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France_ _(LIPIcs, Vol. 96)_ , Rolf Niedermeier and Brigitte Vallée (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16:1–16:14.  https://doi.org/10.4230/LIPIcs.STACS.2018.16
  * Czerner and Esparza (2021) Philipp Czerner and Javier Esparza. 2021.  Lower Bounds on the State Complexity of Population Protocols. In _PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021_ , Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 45–54.  https://doi.org/10.1145/3465084.3467912
  * Czerwinski and Orlikowski (2021) Wojciech Czerwinski and Lukasz Orlikowski. 2021.  Reachability in Vector Addition Systems is Ackermann-complete.  _CoRR_ abs/2104.13866 (2021).  arXiv:2104.13866 https://arxiv.org/abs/2104.13866
  * Esparza et al. (2015) Javier Esparza, Pierre Ganty, Jérôme Leroux, and Rupak Majumdar. 2015.  Verification of Population Protocols. In _26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015_ _(LIPIcs, Vol. 42)_ , Luca Aceto and David de Frutos-Escrig (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 470–482.  https://doi.org/10.4230/LIPIcs.CONCUR.2015.470
  * Esparza et al. (2017) Javier Esparza, Pierre Ganty, Jérôme Leroux, and Rupak Majumdar. 2017.  Verification of population protocols.  _Acta Informatica_ 54, 2 (2017), 191–215.  https://doi.org/10.1007/s00236-016-0272-3
  * Leroux (2021) Jérôme Leroux. 2021\.  The Reachability Problem for Petri Nets is Not Primitive Recursive.  _CoRR_ abs/2104.12695 (2021).  arXiv:2104.12695 https://arxiv.org/abs/2104.12695
  * Pottier (1991) Loic Pottier. 1991\.  Minimal Solutions of Linear Diophantine Systems: Bounds and Algorithms. In _Proceedings of the 4th International Conference on Rewriting Techniques and Applications_ _(RTA ’91)_. Springer-Verlag, London, UK, UK, 162–173.  http://dl.acm.org/citation.cfm?id=647192.720494
  * Rackoff (1978) Charles Rackoff. 1978\.  The Covering and Boundedness Problems for Vector Addition Systems.  _Theor. Comput. Sci._ 6 (1978), 223–231.  https://doi.org/10.1016/0304-3975(78)90036-1