11institutetext: Facultad de Ingeniería, Universidad Católica de la Santísima
Concepción, Chile 11email<EMAIL_ADDRESS>Facultad de
Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Chile 22email:
<EMAIL_ADDRESS>
# The Hardness of Local Certification of Finite-State Dynamics

Diego Maldonado 11 Pedro Montealegre 22 Martín Ríos-Wilson 22

###### Abstract

Finite-State Dynamics (FSD) is one of the simplest and constrained distributed
systems. An FSD is defined by an $n$-node network, with each node maintaining
an internal state selected from a finite set. At each time-step, these nodes
synchronously update their internal states based solely on the states of their
neighboring nodes.

Rather than focusing on specific types of local functions, in this article,
our primary focus is on the problem of determining the maximum time required
for an FSD to reach a stable global state. This global state can be seen as
the acceptance state or as the output of a distributed computation. For fixed
$k$ and $q$, we define the problem $\text{convergence}(k,q)$, which consists
of deciding if a $q$-state FSD converges in at most $k$ time-steps.

Our main focus is to study the problem convergence from the perspective of
distributed certification, with a focus on the model of proof-labeling schemes
(PLS). First, we study the problem convergence on arbitrary graphs and show
that every PLS has certificates of size $\Theta(n^{2})$ (up to logarithmic
factors). Then, we turn to the restriction of the problem on graphs of maximum
degree $\Delta$. Roughly, we show that the problem admits a PLS with
certificates of size $\Delta^{k+1}$, while every PLS requires certificates of
size at least $2^{k/6}\cdot 6/k$ on graphs of maximum degree $3$.

###### Keywords:

Local Certification Proof Labeling Schemes Finite State Dynamics

##  1 Introduction

Networks serve as the backbone of numerous scientific domains, ranging from
the social sciences, where they represent human connections, to logistics, as
seen in traffic patterns, and even electrical engineering, as in circuitry.
Distributed computing explores the capabilities and constraints of algorithms
that operate across these networks. Given the pervasive influence of the
Internet, most contemporary models aim to understand devices capable of
accessing it. Typically, distributed computing employs the message-passing
model, where nodes can send extensive messages to neighboring nodes and
perform local computations. However, some networks, such as emerging wireless
networks like ad-hoc or sensor networks, do not perfectly conform to this
traditional model. Their underlying devices have constraints that do not align
with the classical message-passing model

A recent trend involves using distributed computing techniques, especially the
message-passing model, for sub-microprocessor networks like those in
biological cells or nano-mechanical devices [11]. However, the fundamental
differences in capability between biological or nano nodes and silicon-based
devices necessitate a distinct network model, one designed for nodes
inherently more limited than Turing machines. A natural model to consider in
that context is the one of finite-state dynamics [9, 22, 28]. Within this
framework, numerous agents are interconnected through an undirected graph
known as the _interaction graph_. Each agent communicates solely with its
immediate neighbors. Every node on this graph has an inherent local state,
with the collective states of all nodes forming a _configuration_ or global
state for the dynamic system. This internal state gets updated, relying on its
prior state and those of its neighbors. This updating is governed by a _local
rule_. Moreover, the function that transforms one configuration into another
using local rules is termed the _global rule_. As this rule is repeatedly
applied, a series of global configurations ensues. Given that there is a
finite number of configurations, the dynamics will eventually lead to a
repetitive sequence of node states. If, after successive applications of the
global rule, the system reaches a stable configuration where the internal
state of each node remains unchanged, we say that the system _converges_.

An interesting feature of the finite-state dynamics formalism is its capacity
to describe complex behavior while utilizing a constant-size information
representation through the states of the nodes [3]. In the realm of
theoretical computer science, the study of finite-state dynamics revolves
around several key topics. One significant question involves investigating
whether the structure of the underlying interaction graph can influence its
dynamics [23, 24, 25]. Another well-explored approach is the study of decision
problems linked to the dynamics, often motivated by specific questions
pertaining to particular models. In this context, a central question centers
on determining the point at which the complexity of the dynamics, viewed as
the complexity of a particular decision problem, becomes related to the
dynamical behavior.

In the field of distributed systems, numerous models exhibit similarities or
share characteristics with finite-state dynamics. An example of a model in
which the messages distributed by the nodes in the network are bounded is the
case of the beeping model [8, 18]. In this model, nodes can either beep or
stay silent, and they can only distinguish between two situations: when all
their neighbors are silent or when at least one neighbor is beeping. In
addition, they can either beep or listen to their neighbors, but they cannot
do both at the same time. A crucial difference between the FSD model and the
beeping model is that in the latter, the local computation is performed by a
Turing machine (so the set of states is not finite). This model has
interesting applications as the beeping process can be interpreted as
communication between simple machines, such as sensors, or it can be seen as a
way to communicate messages in a biological network [1, 2].

Another example of a model related to finite-state dynamics is the model
called networked state machines (nFSM) introduced in [11]. In this case, the
local computation is done using a finite set of states, but the essential
difference between this model and finite-state dynamics is that nFSM operates
asynchronously and incorporates elements of randomness. In the previously
cited papers, the dynamics induced by these models are interpreted as the
distributed computing of coloring or a maximal independent set [1, 2, 11].

Generally speaking, the main measure of performance in distributed systems is
the number of rounds required to output a solution in the worst case. In this
sense, studying the time required for the system to compute a solution, the
convergence time, is crucial. However, to our knowledge, this has not been
addressed from a more dynamics-centered approach or a local certification
approach.

Existing literature has established a connection between the computational
complexity of these problems and the dynamical properties of the system [34,
5, 26]. Nevertheless, to our knowledge, these problems have not been explored
from a distributed standpoint.

Recently, a novel approach based on distributed algorithms and local decisions
has been introduced [32]. This approach has been applied to study opinion
dynamics in social systems. In this work, we extend this approach to examine a
broader framework, specifically focusing on distributed certification for
determining whether the dynamics converge.

###  1.1 The model

We now define the model more formally, while we refer to the preliminaries
section for further details. We consider simple finite undirected graphs $G$.
Each node has one over a finite set of states $Q$. A node $u$ of $G$ also
knows a deterministic local function $f_{u}$, that specifies how the node
updates its state, computed according to the states on its closed
neighborhood. In order to simplify the model, we consider only synchronous
dynamics, meaning that all nodes update their states at the same time on each
time-step. The synchronous application of the local functions on every node
produces a _global function_ $F$ over $G$, which establishes how the
configuration of states of every node evolves over time. The pair $(G,F)$ is
called a _finite-state dynamic system_.

Since the possible state configurations of the system is finite, and the local
functions are deterministic, we have that every sequence of state
configurations of a finite-state dynamics system is eventually periodic. A
state configuration is called a _fixed point_ if the dynamics does not change
under the application of the global function. A finite-state dynamics system
is _convergent_ if every state configuration reaches a fixed point after a
certain number of times-steps. The _convergence time_ of a system is the
maximum number of time-steps required to reach a fixed point from any initial
configuration. Obviously, the _convergence time_ of a system is finite only if
the system is convergent.

###  1.2 The Convergence problem

In the study of finite-state dynamics, there are multiple possible research
questions. Most of these questions are related to the study of one particular
dynamical behavior. However, instead of focusing on a specific system, the
main aim of this work is to focus on identifying properties of an arbitrary
dynamics that can be studied using distributed methods. A natural task in this
context consists of predicting the long-term behavior of the system. For
example, it might be interesting to ask if observing the dynamics for a given
number of time-steps is enough for the system to attain a particular state
(such as an acceptance state, for instance), or ascertain whether a
computation processed by the network will eventually converge.

Within distributed systems characterized by finite states, the properties
based on localized knowledge of the update rules constitute a key element to
consider. In fact, given the inherent nature of distributed systems, it
becomes crucial to understand the evolution of the dynamics and the long-term
behavior of the system based solely on this local data.

The main research question of this article is: Using local knowledge, can we
predict if a dynamic system will converge within a given number of time-steps?
More precisely, given a pair of positive integers $k$ and $q$, we define the
problem $\textsc{Convergence}(k,q)$ which consists of, given a $q$-state
finite-state dynamic system, determining if the dynamics converges in at most
$k$ time-steps.

This problem is not solvable by a local algorithm, as the state evolution of a
node might be affected by the state configuration in remote locations of the
network. For that reason, we tackle the $\textsc{Convergence}(k,q)$ problem
from the perspective of local certification, more specifically, _proof-
labeling schemes_.

###  1.3 Local certification.

A local certification algorithm for a distributed decision problem is a
prover-verifier pair where the prover is an untrustworthy oracle assigning
certificates to the nodes, and the verifier is a distributed algorithm
enabling the nodes to check the correctness of the certificates by a certain
number of communication rounds with their neighbors. Note that the
certificates may not depend on the instance $G$ only, but also on the
identifiers id assigned to the nodes. Proof-labeling schemes (PLSs) are a
specific type of local certification algorithms, where the information
exchanged between the nodes during the verification phase is limited to only
one round, and the contents are limited to the certificates. The prover-
verifier pair must satisfy the following two properties.

Completeness: On yes-instances, the untrustworthy prover can assign
certificates to the nodes such that the verifier accepts at all nodes;

Soundness: On no-instances, for every certificate assignment to the nodes by
the untrustworthy prover, the verifier rejects in at least one node.

The main complexity measure for proof-labeling schemes is the size of the
certificates assigned to the nodes by the prover.

###  1.4 Our Results

First, we observe that for each pair of positive integers $k$ and $q$, the
$\textsc{Convergence}(k,q)$ problem can be verified on $n$-node graphs with
certificates of size

$b_{\max}(k+1)\cdot\log(\textsf{id}_{\max})\cdot|f_{\max}(n,q)|,$

where $b_{\max}(k+1)$ is the maximum number of edges having an endpoint in a
node at distance at most $k+1$, the identifiers are assigned with values in
$[\textsf{id}_{\max}]$ and $|f_{\max}(n,q)|$ is the maximum number of bits
required to encode a local function. This is achieved by providing each node
with the necessary part of the network to simulate $k+1$ time-steps of any
configuration. In our first main result, we show that such a simple algorithm
is in fact the best one possible in general, up to logarithmic factors. More
precisely, we show that every Proof-Labeling Scheme (PLS) for
$\textsc{Convergence}(2,4)$ requires certificates of size $\Omega(n^{2}/(\log
n))$.

Observe that even if we consider a finite number of states, the encoding of a
local function can be exponentially large relative to the number of neighbors
of a node. Therefore, we consider local rules that admit _succinct
representations_ , which can be encoded using a logarithmic number of bits per
neighbor. Examples of such local rules are the ones found in artificial neural
networks, the modeling of opinion dynamics, or different biological processes.
Our lower-bound does not hide the complexity in the encoding of the local
rules, as it holds even when the problem is restricted to local functions that
admit a succinct representation.

Later, we focus on graphs with bounded degree. Restricted to this case, the
straightforward approach gives a PLS for $\textsc{Convergence}(k,q)$ with
certificates of size at most

$\Delta((\Delta-1)^{k+1}-1)\cdot
q^{\Delta+1}\log(q)\cdot\log(\textsf{id}_{\max})$

where $\Delta\geq 2$ is the maximum degree of the input graph. In our second
main result, we show that the exponential dependency on $k$ cannot be avoided
in the bounded degree case. More precisely, we show that every PLS for problem
$\textsc{Convergence}(k,3)$ requires certificates of size at least
$2^{k/6}\cdot 6/k$ even when the problem is restricted to input graphs of
maximum degree $3$.

###  1.5 Related Work

Finite-state dynamics and majority voting dynamics. An interesting distributed
problem is the one of predicting the result of a two-candidate election. This
process is typically modeled as a majority voting dynamics. The model can be
seen as a group of $n$ agents represented by nodes in a network who are
surveyed about their preferred candidate in an upcoming election with two
choices. Over a series of time steps, each agent adjusts their vote based on
the majority opinion of their network neighbors, ultimately determining the
leading candidate after $T$ time steps. The challenge lies in predicting the
leading candidate which in general is a very hard task.

In [32] the authors study the problem Election-Prediction, consisting of
predicting the leading candidate after a certain number of time-steps from the
perspective of local certification. In particular, they show that graphs with
sub-exponential growth admit a proof labeling scheme of size $\mathcal{O}(\log
n)$ for problem Election-Prediction. Additionally, they deduce upper bounds
for graphs with bounded degree, where certificate sizes are sub-linear in $n$.
Furthermore, they explore lower bounds for the unbounded degree case,
establishing that the local certification of Election-Prediction on arbitrary
$n$-node graphs require certificates of at least $\Omega(n)$ bits.
Interestingly, the authors show that the upper bounds are tight, even for
graphs with constant growth.

In terms of the techniques used in this paper, the authors present an
interesting approach for deriving an upper bound based on the analysis of the
maximum number of time steps in which an individual may change their opinion
during the majority dynamics. In particular, they show for different families
of graphs (one of them being the graphs with sub-exponential growth) that this
number is bounded when the dynamics are observed at every two time steps. In
addition, the lower bounds are deduced via a reduction to the disjointedness
problem in non-deterministic communication complexity.

Local certification. Since the introduction of PLSs [30], various variants
have been introduced. As we mentioned, a stronger form of PLS are locally
checkable proofs [27], where each node can send not only its certificates but
also its state and look around within a given radius. Other stronger forms of
local certifications are $d$-PLS [15], where nodes perform communication at a
distance of $d\geq 1$ before deciding. Authors have studied many other
variants of PLSs, such as randomized PLSs [21], quantum PLSs [19], interactive
protocols [10, 29, 33], zero-knowledge distributed certification [6], and
certain PLSs that use global certificates in addition to the local ones [17],
among others. On the other hand, some trade-offs between the size of the
certificates and the number of rounds of the verification protocol have been
exhibited [15]. Also, several hierarchies of certification mechanisms have
been introduced, including games between a prover and a disprover [4, 14].

PLSs have been shown to be effective for recognizing many graph classes. For
example, there are compact PLSs (i.e., with logarithmic size certificates) for
the recognition of acyclic graphs [30], planar graphs [16], graphs with
bounded genus [12], and $H$-minor-free graphs, provided that $H$ contains no
more than four vertices [7]. In a recent breakthrough, Bousquet et al. [13]
proved a ’meta-theorem’, stating that there exists a PLS for deciding any
monadic second-order logic property with $O(\log n)$-bit certificates on
graphs of bounded _tree-depth_. This result has been extended by Fraigniaud et
al [20] to the larger class of graphs with bounded _tree-width_ , using
certificates on $O(\log^{2}n)$ bits.

##  2 Preliminaries

In this article, we denote by $[m,n]$ the set of integers greater than or
equal to $m$ and less than or equal to $n$. We also denote $[n]$ as the
interval $[1,n]$.

Let $G=(V,E)$ be a graph. We denote by $N_{G}(v)$ the _neighborhood of $v$ in
$G$_, defined by $N_{G}(v)=\\{u\in V:\\{u,v\\}\in E\\}$. The _degree_ of $v$,
denoted $d_{G}(v)$, is the cardinality of $N_{G}(v)$. The _maximum degree_ of
$G$, denoted $\Delta_{G}$, is the maximum value of $d_{G}(v)$ taken over all
$v\in V$. We denote by $N_{G}[v]$ the set $N_{G}(v)\cup\\{v\\}$ and call it
the _close neighborhood_ of $v$. We say that two nodes $u,v\in V$ are
_connected_ if there exists a path in $G$ joining them. In the following, we
only consider connected graphs. The _distance_ between $u,v$, denoted
$d_{G}(u,v)$, is the minimum length (number of edges) of a path connecting
them. For a graph $G$, $v\in V(G)$, and $p\geq 0$, we denote $B_{v}(p)$ as the
set of all edges where one of the endpoints is a node at distance at most $p$
from $v$ in $G$. We denote by $b_{v}(p)$ the cardinality of $B_{v}(p)$, and
denote by $b_{\max}(p)$ the maximum $b_{v}(p)$ over $v\in V(G)$. In the
following, we omit the sub-indices when they are obvious by the context.

###  2.1 Finite state dynamics

Let $G=(V,E)$ be a graph, $Q$ a finite set. A _finite state dynamic system
over $G$_ is a function $F:Q^{V}\to Q^{V}$ such that, for each $v\in V$ there
exists a function $f_{v}:Q^{N[v]}\rightarrow Q$ satisfying
$F(x)_{v}=f_{v}(x|_{N[v]})$. The functions $\\{f_{v}\\}_{v\in V}$ are called
the _local functions_ of $F$ and the elements of $Q$ are the _states_ of $F$.
The elements of $Q^{V}$ are called _configurations_ of $G$.

We consider the model where $F$ is distributed over the network in a way that
each node $v$ receives its local function $f_{v}:Q^{N[v]}\rightarrow Q$ as
input. A vertex $v$ identifies $d(v)$ ports that enumerate its incident edges,
where $d(v)$ is the size of the neighborhood of $v$. Each input variable of
$f_{v}$ is identified with one of the ports, except one that is identified
with $v$. Therefore, $f_{v}$ can be encoded in at most
$|Q|^{d(v)+1}\log{|Q|}+(d(v)+1)\log(d(v)+1)$ bits.

In some cases we are interested in the local functions that can be encoded
with much fewer bits. For instance, consider the dynamics with states
$Q=\\{-1,1\\}$ and where each node takes the majority state over its
neighbors, which can be encoded with a constant number of bits per node. We
say that $F:Q^{V}\to Q^{V}$ is _succinct_ if, for each $v\in V$ we have that
$f_{v}$ can be encoded with $\mathcal{O}(d(v)\log(d(v)))$ bits.

###  2.2 Local decision

Let $G=(V,E)$ be a simple connected $n$-node graph. A _distributed language_
$\mathcal{L}$ is a Turing-decidable collection of tuples
$(G,\textsf{id},\textsf{In})$, called _network configurations_ , where
$\textsf{In}:V\rightarrow\\{0,1\\}^{*}$ is called an _input function_ and
$\textsf{id}:V\rightarrow[n^{c}]$ is an injective function that assigns to
each vertex a unique identifier in $[n^{c}]$ with $c>1$. In this article, all
our distributed languages are independent of the id assignments. In other
words, if $(G,\textsf{id},\textsf{In})\in\mathcal{L}$ for some id, then
$(G,\textsf{id}^{\prime},\textsf{In})\in\mathcal{L}$ for every other
$\textsf{id}^{\prime}$.

Given $d>0$, a _local decision algorithm_ for a distributed language
$\mathcal{L}$ is an algorithm on instance $(G,\textsf{id},\textsf{In})$, where
each node $v$ in $V(G)$ receives the subgraph induced by all nodes within a
distance of at most $d$ from $v$, including their identifiers and inputs. The
integer $d>0$ depends only on the algorithm, not on the size of the input.
Each node performs unbounded computation on the information received, and
decides whether to accept or reject, with the following requirements:

  * •

When $(G,\textsf{id},\textsf{In})\in\mathcal{L}$, then every node accepts.

  * •

When $(G,\textsf{id},\textsf{In})\notin\mathcal{L}$, there is at least one
vertex that rejects.

###  2.3 Distributed languages for finite-state dynamics

Consider a graph $G$, a finite-state dynamic (FSD) $F$ over $G$, and a
configuration $x$. The _orbit_ of $x$ is the sequence of configurations
$\\{x^{t}\\}_{t>0}$ such that $x^{0}=x$ and for every $t>0$,
$x^{t}=F(x^{t-1})$. We say that the dynamics of $x$ _converge_ in at most
$k\geq 0$ time-steps if $x^{k}$ is a fixed point, i.e., $x^{k}=F(x^{k})$. We
denote by $\textsc{Convergence}(k,q)$ the set of pairs $(G,F)$ satisfying that
every configuration $x$ converges in at most $k$ time-steps. Formally,

$\textsc{Convergence}(k,q)=\left\\{(G,F):\begin{array}[]{l}F:Q^{V(G)}\rightarrow
Q^{V(G)}\textrm{ is a FSD over }G,\\\ |Q|\leq q,\textrm{ and }\\\
F(x^{k})=x^{k}\textrm{ for every }x\in Q^{V(G)}\end{array}\right\\}$

It is easy to see that there are no local decision algorithms for
$\textsc{Convergence}(k,q)$. That is, there are no algorithms in which every
node of a network exchanges information solely with nodes in its vicinity and
decides whether the dynamics converge within a limited number of time-steps.

###  2.4 Communication Complexity

Given a Boolean function $f:X\times Y\rightarrow\\{0,1\\}$, where Alice is
given an input $x\in X$ and Bob is given an input $y\in Y$, the deterministic
communication complexity of $f$ is the minimum number of bits Alice and Bob
need to exchange to compute $f(x,y)$, over all possible deterministic
communication protocols. In the non-deterministic version of communication
complexity, a third party, called the prover, is allowed to send a message
(called a certificate) to one or both of the communicating parties to assist
in computing the function. The challenge is to determine the minimal size of
such a hint that would enable the parties to compute the function with the
least amount of communication between them. More formally, the non-
deterministic communication complexity of a Boolean function $f:X\times
Y\rightarrow\\{0,1\\}$, denoted $N^{\textrm{cc}}(f)$, is the minimum integer
$k$ such that there exists a function $g:X\times
Y\times\\{0,1\\}^{k}\rightarrow\\{0,1\\}$ (where $\\{0,1\\}^{k}$ represents
the hint from a prover) satisfying:

  1. 1.

$f(x,y)=1$ implies there exists a certificate $c\in\\{0,1\\}^{k}$ such that
$g(x,y,c)=1$,

  2. 2.

$f(x,y)=0$ implies that for all certificates $c\in\\{0,1\\}^{k}$,
$g(x,y,c)=0$.

The nondeterministic communication complexity is then the maximum over all
pairs $(x,y)$ of the sum of the number of bits exchanged and the size of the
certificate. In this article, we prove our lower-bounds by reducing
Convergence to a problem Disjointness in communication complexity. This
problem corresponds to the function $\textsc{Disjointness}_{n}:2^{[n]}\times
2^{[n]}\rightarrow\\{0,1\\}$ such that

$\textsc{Disjointness}_{n}(A,B)=1\textrm{ if and only if }A\cap B=\emptyset.$

The following result is shown in [31].

###### Proposition 1

$N^{\textrm{cc}}(\textsc{Disjointness}_{n})=n$.

##  3 Finite-State Dynamics on Arbitrary Graphs

In this section, we tackle problem Convergence on arbitrary graphs. We begin
by giving an upper bound on the certification size. For $q>0$, we denote by
$|f_{\max}(n,q)|$ the maximum number of bits required to encode a local
function of finite-state dynamics over an $n$-node graph on $q$ states.

###### Theorem 3.1

For each $q>1$, $\textsc{Convergence}(k,q)$ admits a Proof-Labeling Scheme
(PLS) with certificates of size

$b_{\max}(k+1)\cdot\log(\textsf{id}_{\max})\cdot|f_{\max}(n,q)|,$

on graphs with identifiers in $[\textsf{id}_{\max}]$.

###### Proof

Let $G,F$ be an instance of $\textsc{Convergence}(k,q)$. The certification
algorithm provides each node $v\in V(G)$ with the following information:

  * $\bullet$

The set $B^{v}_{v}(k+1)$ representing $B_{v}(k+1)$.

  * $\bullet$

The set of all local functions $f^{v}_{w}$ of nodes $w$ that are endpoints of
edges in $B^{v}_{v}(k+1)$.

Observe that the certificates can be encoded in at most

$b_{\max}(k+1)\cdot\log(\textsf{id}_{\max})\cdot|f_{\max}(n,q)|$

bits. Given the certificates, $v$ can reconstruct all the neighborhoods and
local functions of nodes at distance at most $k+1$ from $v$. In particular,
$v$ can determine all the nodes up to distance $k+2$ and all the local
functions of nodes up to distance $k+1$.

In the verification algorithm, each node $v$ checks the consistency of the
information provided to its neighbors and verifies that $v$ converges to a
fixed-point in $k$ time-steps for every configuration assigned to nodes with
endpoints in $B_{v}(k)$. Formally, $v$ checks the following conditions for
each node $u\in N(v)$:

  1. a.

All the edges in $B^{u}_{u}(k)$ belong to $B^{v}_{v}(k+1)$.

  2. b.

If $w$ is an endpoint of an edge in $B_{u}(k+1)\cap B_{v}(k+1)$ then
$f^{v}_{w}=f^{u}_{w}$. In particular, $f^{v}_{v}=f^{u}_{v}$.

  3. c.

For every configuration of the nodes with endpoints in $B^{v}_{v}(k+1)$, $v$
simulates $k+1$ time-steps and checks that the configuration reached by $v$
after $k$ time-steps is a fixed point.

Node $v$ accepts only if all conditions are satisfied. Let us analyze now the
soundness and completeness.

_Completeness:_ Let us suppose that $(G,F)$ is a _yes-instance_. Clearly, if
every node $v$ receives the certificates as they are defined (i.e.,
$B^{v}_{v}(k+1)=B_{v}(k+1)$, $f_{w}^{v}=f_{w}$ for every $w$ that is an
endpoint of an edge in $B_{v}(k+1)$), then every node accepts.

_Soundness:_ Let us suppose that $(G,F)$ is a _No-instance_. In other words,
there exists a configuration $x$ of $G$ for which $F(x^{k})\neq x^{k}$. Let
$v$ be a node such that $F(x^{k})_{v}\neq x^{k}_{v}$. Assuming that every node
accepts conditions a. and b., and since these conditions are satisfied for
every node, we have that $B^{v}_{v}(k+1)=B_{v}(k+1)$ and $f_{w}^{v}=f_{w}$ for
every $w$ that is an endpoint of an edge in $B_{v}(k+1)$. Observe that
$x^{k+1}_{v}$ only depends on the initial configuration of nodes at distance
at most $k+2$ from $v$, and the local functions of nodes at distance at most
$k+1$ from $v$. Therefore, $v$ rejects the condition c of the verification
algorithm. ∎

Notice that when $b_{\max}(k+1)=\mathcal{O}(n^{2})$ (for instance, on dense
graphs of small diameter), the upper bound above is
$\mathcal{O}(n^{2}\log(\textsf{id}_{\max})|f_{\max}|)$, which is greater than
the trivial upper bound
$\mathcal{O}(n^{2}\log(\textsf{id}_{\max})+n|f_{\max}|)$ that involves
providing each node with all the edges of the graph and all the local
functions. In the next theorem, we show that, up to logarithmic factors, there
is also a quadratic lower bound for the convergence in at most two time-steps,
and specifically for dynamics on four states that admit a succinct
representation.

###### Theorem 3.2

Every Proof Labeling Scheme for $\textsc{Convergence}(2,4)$ has certificates
of size $\Omega(n^{2}/(\log n))$. This holds even when the problem is
restricted to local functions that admit a succinct representation.

###### Proof

We reduce $\textsc{Convergence}(2,4)$ to Disjointness in two-player
communication complexity. Given an instance of Disjointness, we build an
instance of problem $\textsc{Convergence}(2,4)$, which is composed of a
_lower-bound graph_ and a dynamic picked from a family of _lower-bound
dynamics_.

We begin by giving a high-level description of the construction. Let $n$ be a
positive integer, and let ${\bf A},{\bf B}\subseteq\binom{[n]}{2}$ be a pair
of sets, interpreted as an instance of Disjointness. The set $\bf A$ is
associated with the graph $G_{\bf A}$ with the vertex set
$\\{v_{1},\dots,v_{n}\\}$ such that, for each $i,j\in[n]$, node $v_{i}$ is
adjacent to $v_{j}$ if and only if $\\{i,j\\}\in{\bf A}$. The graph $G_{\bf
B}$ is defined analogously using the set ${\bf B}$ instead of ${\bf A}$.

The lower-bound graph has vertices containing disjoint copies of $G_{\bf A}$
and $G_{\bf B}$, as well as a _bit gadget_ , which is connected to every other
vertex. A configuration satisfies an _admissibility condition_ when the state
of the bit gadget encodes the binary representation of an element of
$[n]\times[n]$, and this element represents an edge that is both in $G_{\bf
A}$ and $G_{\bf B}$ (i.e., when ${\bf A}\cap{\bf B}\neq\emptyset$). The
dynamic of the system is designed to oscillate in a limit-cycle of period two
only when the admissibility condition is satisfied. When the admissibility
condition is not satisfied, the dynamic reaches a fixed point in at most two
time-steps.

Lower-bound graph. For each $n>0$, the _lower-bound graph_ $G({\bf A,B})$ is a
graph of size $2n+4\lceil\log n\rceil$ (see Figure 1). The vertex set of
$G({\bf A,B})$ is partitioned into four subsets, namely,
$V_{A}=\\{v^{A}_{1},\dots,v^{A}_{n}\\}$,
$V_{B}=\\{v^{B}_{1},\dots,v^{B}_{n}\\}$,
$D_{A}=\\{d^{A}_{1},\dots,d^{A}_{\ell}\\}$ and
$D_{B}=\\{d^{B}_{1},\dots,d^{B}_{\ell}\\}$, where $\ell=2\lceil\log n\rceil$.
The edge set of $G_{\bf A,B}=(V,E)$ contains all the edges with one endpoint
in $V_{A}$ and the other in $D_{A}$, all edges between nodes in $V_{B}$ and
$D_{B}$, and all edges with endpoints in $D_{A}\cup D_{B}$. It also contains,
for each $i,j\in[n]$ the edge $\\{v_{i}^{A},v_{j}^{A}\\}$ (respectively,
$\\{v_{i}^{B},v_{j}^{B}\\}$) if node $v_{i}$ is adjacent to $v_{j}$ in $G_{\bf
A}$ (respectively, $G_{\bf B}$).

Nodes in $D_{A}\cup D_{B}$ are called the _bit gadget_ and the nodes of
$V_{A}\cup V_{B}$ are the _set gadget_.

$v_{1}^{A}$$v_{2}^{A}$$v_{3}^{A}$$v_{4}^{A}$$d_{1}^{B}$$d_{2}^{B}$$d_{3}^{B}$$d_{4}^{B}$$d_{1}^{A}$$d_{2}^{A}$$d_{3}^{A}$$d_{4}^{A}$$v_{1}^{B}$$v_{2}^{B}$$v_{3}^{B}$$v_{4}^{B}$$V_{A}$$D_{A}$$D_{B}$$V_{B}$
Figure 1: Lower-bound graph $G({\bf A,B})$ when $n=4$, ${\bf
A}=\\{\\{1,3\\},\\{1,4\\},\\{3,4\\}\\}$ and ${\bf
B}=\\{\\{2,3\\},\\{2,4\\}\\}$

States of the system. For all nodes the set of states is
$Q=\\{0,1\\}\times\\{0,1\\}$. Given a node $u$ in state $s(u)=(m(u),c(u))\in
Q$ we say that $m(u)$ is the _mark_ of $u$ and $c(u)$ is the _clock_ of $u$.

Given the set of states $Q$, we define now lower-bound dynamics given by
lower-bound local functions, that we call $F(\bf{A,B})$. The local functions
of nodes in $D_{A}\cup D_{B}$ will be independent on the input of the players,
while the ones nodes of $V_{A}$ (respectively $V_{B}$) depend only on ${\bf
A}$ (respectively ${\bf B}$). We describe first the local functions of nodes
in $D_{A}\cup D_{B}$.

Local functions of nodes of the bit gadget. First, we define the following
_admissibility conditions_ for a given configuration, which is checked for
every node in $D_{A}$ (respectively $D_{B}$):

  * d1)

Every node in $D_{A}\cup D_{B}$ has the same clock.

  * d2)

There are exactly two nodes in $V_{A}$ (resp. $V_{B}$) with mark $1$.

  * d3)

For each $s\in\\{1,\dots,\ell\\}$, the mark of $d^{A}_{s}$ equals the one of
$d^{B}_{s}$.

The dynamic of the nodes $u$ in $D_{A}$ and $D_{B}$ is then defined as
follows: if the admissibility conditions are satisfied, then the mark of $u$
remains unchanged, and the clock of $u$ switches to $0$ if the clock was $1$
and vice-versa. If the admissibility condition is not satisfied, the whole
state of $u$ (mark and clock) remains unchanged. In any case, the marks in the
nodes of the bit gadget do not change under any circumstances.

For each $s\in[\ell]$, the local function of $d_{s}^{A}$ (respectively
$d_{s}^{B}$) is succinct. Indeed, to define the function, we simply need to
indicate which neighbors of $d_{s}^{A}$ (resp. $d_{s}^{B}$) belong to $D_{A}$
and which to $V_{A}$ (resp. $D_{B}$ and $V_{B}$), and which node is
$d_{s}^{B}$ (resp. $d_{s}^{A}$). This can be encoded using $\mathcal{O}(1)$
bit per neighbor.

Observe that while the admissibility condition is verified, the clocks in the
nodes of $D_{A}\cup D_{B}$ continuously switch between $0$ and $1$. Suppose
that in the configuration on a given time-step $t$, there are nodes
$d_{1},d_{2}\in D_{A}\cup D_{B}$ such that the admissibility condition is
satisfied for $d_{1}$ but not for $d_{2}$. Then, in time-step $t$, we have
that $c(d_{1})=c(d_{2})$, but in $t+1$, $c(d_{1})\neq c(d_{2})$. This implies
that in time-step $t+1$, the admissibility condition (d1) is not satisfied by
any node in $D_{A}\cup D_{B}$, which results in every node in that set being
fixed in its state forever.

Local functions of nodes of the set gadgets. Let $i\in[n]$. The following
admissibility conditions are considered for node $v_{i}^{A}$:

  * v1)

The mark of $v_{i}^{A}$ is $1$.

  * v2)

Exactly one neighbor of $v_{i}^{A}$ in $V_{A}$ has mark $1$.

  * v3)

The mark of $d^{A}_{1},\dots,d^{A}_{\ell/2}$ or
$d^{A}_{\ell/2+1},\dots,d^{A}_{\ell}$ represents the binary representation of
$i$.

The local function of $v_{i}^{A}$ indicates that the mark of node $v^{A}_{i}$
is $1$ if the admissibility conditions are satisfied, and $0$ otherwise. The
clock of $v_{i}^{A}$ does not change under any circumstance.

The local function of $v_{i}^{A}$ is succinct for every $i\in[n]$. To define
the function, it is necessary to simply indicate which neighbors of
$v_{i}^{A}$ belong to $D_{A}$ and which to $V_{A}$. This can be encoded using
$\mathcal{O}(1)$ bit per neighbor. Additionally, specifying the index $i$
requires $\mathcal{O}(\log n)$ bits. Analogous admissibility conditions and
local functions are defined for node $v_{i}^{B}$ by switching the subindices
$A$ by $B$.

Independently of the initial configuration, the admissibility condition is
satisfied for at most two nodes in $V_{A}$, as the marks in $D_{A}$ can
represent at most two indices in $[n]$. Then, in the first time-step, the mark
of every node in $V_{A}$ is $0$, except for at most two nodes. The mark of the
remaining nodes, namely $v^{A}_{i}$ and $v_{j}^{A}$, is $1$ only if the
admissibility condition is satisfied for two nodes. In particular, condition
(v2) implies that $v_{i}^{A}$ is adjacent to $v_{j}^{A}$. Hence
$\\{i,j\\}\in{\bf A}$. In any case, the state of every node of $V_{A}\cup
V_{B}$ remains unchanged after the first time-step.

The reduction. We now show that $(G({\bf A,B}),F({\bf A,B}))$ converges in at
most two time-steps if and only if ${\bf A}\cap{\bf B}=\emptyset$. Let us
suppose that ${\bf A}\cap{\bf B}\neq\emptyset$, and let $\\{i,j\\}\in{\bf
A}\cap{\bf B}$. We define the following initial configuration $x$.

  * $\bullet$

For every $s\in[n]\setminus\\{i,j\\}$, nodes $v_{s}^{A}$ and $v_{s}^{B}$ have
initial configuration $(0,0)$.

  * $\bullet$

The initial configuration of $v_{i}^{A}$, $v_{j}^{A}$, $v_{i}^{B}$, and
$v_{j}^{B}$ is $(1,0)$.

  * $\bullet$

For each $s\in[\ell/2]$, the initial configuration of $d_{s}^{A}$ and
$d_{s}^{B}$ is $(b,0)$, where $b$ is the $s$-th bit in the binary
representation of $i$.

  * $\bullet$

For each $s\in[\ell/2+1,\ell]$, the initial configuration of $d_{s}^{A}$ and
$d_{s}^{B}$ is $(b,0)$, where $b$ is the $s$-th bit in the binary
representation of $j$.

Observe that in $x$ all the admissibility conditions are satisfied. Moreover,
in the next time-steps, the mark of every node in $G({\bf A,B})$ remains
unchanged, and the clocks of every node in $D_{A}\cup D_{B}$ switch between
$0$ and $1$ back and forth. Therefore, the dynamic $(G({\bf A,B}),F({\bf
A,B}))$ does not converge.

Now let us suppose that ${\bf A}\cap{\bf B}=\emptyset$. Let $x$ be any initial
configuration, and let $y$ be the configuration obtained in the first time-
step. Observe that the state of every node in $V_{A}\cup V_{B}$ is fixed in
the state of $y$ in the next time-steps. If fewer than two nodes in $V_{A}$
(respectively $V_{B}$) have mark $1$ in $y$, all nodes in $D_{A}$
(respectively $D_{B}$) are fixed in their state forever. Then, in the third
time-step, all nodes in $D_{B}$ (respectively $D_{A}$) are also fixed. Suppose
then that in $y$, exactly two nodes $v_{i}^{A},v_{j}^{A}\in V_{A}$ and two
nodes $v_{p}^{B},v_{q}^{B}\in V_{B}$ have mark $1$. By condition (v3), in $y$
the marks of the nodes in $D_{A}$ are the binary representation of $i$ and
$j$. By condition (v2), $v_{i}^{A}$ and $v_{j}^{A}$ are adjacent. Hence
$\\{i,j\\}\in{\bf A}$. Similarly, the marks on $D_{B}$ are the binary
representations of $p$ and $q$, and $v_{p}^{B}$ is adjacent to $v_{q}^{B}$.
Hence $\\{p,q\\}\in{\bf B}$. Since ${\bf A}\cap{\bf B}=\emptyset$, condition
(d3) is not satisfied in $y$, implying that $y$ is a fixed point.

We deduce that $(G,F({\bf A,B}))\in\textsc{Convergence}(2,4)$ if and only if
${\bf A}\cap{\bf B}=\emptyset$. Let $\pi$ be a PLS for
$\textsc{Convergence}(2,4)$. We define the following two-player protocol
$\mathcal{P}$ for Disjointness. On instance ${\bf A}$, Alice computes
nondeterministically the certificates that $\pi$ would give on all nodes in
$V_{A}\cup D_{A}\cup D_{B}$, and simulates the verification protocol of $\pi$
on all nodes in $V_{A}\cup D_{A}$. Alice communicates a single bit to Bob
indicating if every node in $V_{A}\cup D_{A}$ has accepted, as well as all the
certificates of $D_{A}\cup D_{B}$. Analogously, Bob computes the certificates
of $D_{A}\cup D_{B}\cup V_{B}$ and simulates the verification protocol of
$\pi$ on all nodes in $V_{B}\cup D_{B}$. Bob accepts if all nodes in $V_{B}$
accept and his certificates for $D_{A}\cup D_{B}$ are the same as those
generated by Alice. The correctness of $\mathcal{P}$ follows directly from the
soundness and completeness of $\pi$. Let $C(n)$ be the maximum size of a
certificate produced by $\pi$ on graphs of size $n$. According to Proposition
1, it follows that $C(2n+2\lceil\log n\rceil)\cdot\lceil\log
n\rceil=\Omega(n^{2})$, implying that $C(n)=\Omega(n^{2}/\log n)$. ∎

##  4 Finite-State Dynamics in Graphs of Bounded Degree

Given that the problem is hard in general graphs, we focus our study on
finite-state dynamics over graphs of bounded degree. For such graphs, all
local functions are succinct. Moreover, an analysis of the bound given by
Theorem 3.1 provides a non-trivial upper-bound for the certificate size.

###### Corollary 1

For each $q>1$ and for each $\Delta>2$, problem $\textsc{Convergence}(k,q)$
admits a Proof-Labeling Scheme with certificates of size at most

$\Delta((\Delta-1)^{k+1}-1)\cdot
q^{\Delta+1}\log(q)\cdot\log(\textsf{id}_{\max})$

on graphs of maximum degree $\Delta$ with assignments of identifiers in
$[\textsf{id}_{\max}]$.

###### Proof

Observe that in graphs of maximum degree $\Delta$, there are at most
$(\Delta-1)^{k+1}-1$ nodes at a distance of at most $k+1$ from $v$. Then, we
have that $b_{\max}(k+1)$ is $\Delta((\Delta-1)^{k+1}-1)$. Also, when
restricted to graphs of maximum degree $\Delta$, a local function on $q$
states of a node can be encoded in $q^{\Delta+1}\log q$ bits by writing up the
table of values of the function when the inputs are ordered increasingly by
identifier. We deduce the result by combining these bounds with Theorem 3.1. ∎

In the following result, we show that the exponential dependency on $k$ is
necessary even on graphs of bounded degree. To prove our result, we need to
introduce a _binary decoder_ , which is a specific type of Boolean circuit. A
_Boolean circuit_ is a directed acyclic graph $C$ where each node (called
_gate_) is assigned a Boolean function. The nodes of in-degree zero are called
_input gates_ and the nodes with out-degree zero are called _output gates_. A
truth assignment of the input gates induces a truth assignment of every other
gate in the circuit. Every node takes the value of its assigned Boolean
function, using the truth values of its incoming neighbors as arguments. The
number of gates in a Boolean circuit is known as its _size_ , while the
maximum distance between an input and an output gate is called its _depth_. A
Boolean circuit $C$ is called a _binary decoder_ if there exists a positive
integer $t$ such that $C$ has $t$ inputs and $2^{t}$ outputs, named
$\\{v_{1},\dots,v_{2^{t}}\\}$. This Boolean circuit satisfies that for each
$i\in[2^{t}]$, the output value of $v_{i}$ is True if and only if the truth
values of the inputs (mapped to $0/1$ values) correspond to the binary
representation of $i$.

###### Lemma 1

For each positive integer $t$, there exists a binary decoder $C_{t}$
satisfying the following conditions:

  * (1)

each gate of $C_{t}$ has a total degree (in-degree plus out-degree) at most
$3$;

  * (2)

each input gate of $C_{t}$ has out-degree at most $2$;

  * (3)

each output gate of $C_{t}$ has in-degree at most $2$;

  * (4)

the depth of $C_{t}$ is $3t$; and

  * (5)

the number of gates of $C_{t}$ is $(8t-3)2^{t-1}-t$.

###### Proof

In our construction, we use two types of gadgets, namely a _duplicator_ , and
an _expander_. A $2$-duplicator is a circuit with one input gate and two
output gates that simply replicate the value of the input gate. This can be
implemented with depth $1$ using one-input disjunctions in the output gates.
We can also implement a $2^{t}$-duplicator, which consists of a Boolean
circuit with one input gate and $2^{t}$ output gates, all replicating the
value of the input gate. The $2^{t}$-duplicator can be implemented by
arranging $2$-duplicators in a binary tree of depth $t$. A $2^{t}$-duplicator
satisfies conditions (1)-(3) and has $2^{t+1}-1$ gates.

The expander is similar to a $2$-duplicator, except that the first output gate
is a negation. More precisely, the expander has one input gate and two output
gates. The first output gate negates the value of the input, while the second
replicates the truth value of the input gate.

Our construction is done by induction. For each positive integer $t$, we
denote by $\textsf{in}_{t}(d_{1}),\dots,\textsf{in}_{t}(d_{t})$ the input
gates and $\textsf{out}_{t}(v_{1}),\dots,\textsf{out}_{t}(v_{2^{t}})$ the
output gates of $C_{t}$. The circuit $C_{1}$ simply consists of a gate
$\textsf{in}_{1}(d_{1})$ connected to an expander where one output is assigned
to $\textsf{out}_{1}(v_{1})$ and the other to $\textsf{out}_{1}(v_{2})$.
Clearly, $C_{1}$ is a binary decoder satisfying (1)-(5).

$\textrm{in}_{t+1}(d_{1})$$\cdots$$\textrm{in}_{t+1}(d_{t})$$\textrm{in}_{t+1}(d_{t+1})$$\textrm{in}^{1}\\!(d_{1})$$\cdots$$\textrm{in}^{1}\\!(d_{t})$$\textrm{in}^{2}\\!(d_{1})$$\cdots$$\textrm{in}^{2}\\!(d_{t})$$u^{1}_{1}$$\cdots$$u^{1}_{2^{t}}$$\textrm{out}^{1}\\!(v_{1})$$\cdots$$\textrm{out}^{1}\\!(v_{2^{t}})$$u^{2}_{1}$$\cdots$$u^{2}_{2^{t}}$$\textrm{out}^{2}\\!(v_{1})$$\cdots$$\textrm{out}^{2}\\!(v_{2^{t}})$$\textrm{out}_{t+1}\\!(v_{1})$$\cdots$$\textrm{out}_{t+1}\\!(v_{2^{t}})$$\textrm{out}_{t+1}\\!(v_{2^{t}+1})$$\textrm{out}_{t+1}\\!(v_{2^{t+1}})$$\cdots$$C_{t}$$C_{t}$
Figure 2: Schema of the construction of the binary decoder $C_{t+1}$.

Suppose we have a binary decoder construction $C_{t}$ satisfying conditions
(1)-(5) for a given value $t$. We now describe the construction of $C_{t+1}$
(see also Figure 2). First, for each $i\in[t]$, we create a copy of a
$2$-duplicator and identify the input of each duplicator with the input gate
$\textsf{in}_{t+1}(d_{i})$. Let $d_{i}^{1}$ and $d_{i}^{2}$ be the output
gates of the $i$-th duplicator. Then, we create two copies of $C_{t}$. For
$j\in\\{1,2\\}$, we denote
$\textsf{in}^{j}_{t}(d_{1}),\dots,\textsf{in}^{j}_{t}(d_{t})$ and
$\textsf{out}^{j}_{t}(v_{1}),\dots,\textsf{out}^{j}_{t}(v_{2^{t}})$ as the
input and output gates of the $j$-th copy of $C_{t}$. We identify gate
$d_{i}^{j}$ with $\textsf{in}^{j}_{t}(d_{i})$.

Then, we create a copy of an expander, and identify its input with
$\textsf{in}_{t+1}(v_{t+1})$. We name $d^{1}_{t+1}$ and $d^{2}_{t+1}$ as the
two outputs of the expander. We attach to each $d^{1}_{t+1}$ a
$2^{t}$-duplicator. For each $j\in\\{1,2\\}$, we denote
$u^{j}_{1},\dots,u^{j}_{2^{t}}$ as the outputs of the $2^{t}$-duplicator with
input $d^{j}_{t+1}$. The values of $u^{1}_{1},\dots,u^{1}_{2^{t}}$ are the
negation of $\textsf{in}_{t+1}(d_{t+1})$, while the values of
$u^{2}_{1},\dots,u^{2}_{2^{t}}$ are equal to the value of
$\textsf{in}_{t+1}(d_{t+1})$.

All output gates of $C_{t+1}$ are conjunctions. For each $i\in[2^{t}]$, the
output gate $\textsf{out}_{t+1}(v_{i})$ receives inputs from gates
$\textsf{out}_{t}^{1}(v_{i})$ and $u^{1}_{i}$, and the output gate
$\textsf{out}_{t+1}(v_{i+2^{t}})$ receives inputs from gates
$\textsf{out}_{t}^{2}(v_{i})$ and $u^{2}_{i}$. Finally, to maintain condition
(1) in the induction step, we ensure that the output gates have in-degree $1$.
This is achieved by duplicating all output gates and connecting each output
gate with its duplicate.

We now show that $C_{t+1}$ is a binary decoder. Consider a truth-assignment of
the input values, and let $a\in[2^{t+1}]$ be the integer represented in binary
by the inputs of $C_{t+1}$. Let $b\in[2^{t}]$ be the integer that their binary
truth values represent. Observe that $a=b$ when $\textsf{in}_{t+1}(d_{t+1})$
is $\sf False$ and $a=b+2^{t}$ when $\textsf{in}_{t+1}(d_{t+1})$ is $\sf
True$. According to our construction and the induction hypothesis, we have
that the truth value of $\textsf{out}^{1}_{t}(v_{i})$ and
$\textsf{out}^{2}_{t}(v_{i})$ is $\sf{False}$ for each $i\neq b$, and
$\sf{True}$ if $i=b$. We obtain that for each $i\in[2^{t}]\setminus\\{b\\}$,
the values of $\textsf{out}_{t+1}(v_{i})$ and
$\textsf{out}_{t+1}(v_{i+2^{t}})$ are $\sf False$, as each one of these gates
receives an input from node $\textsf{out}_{t}(v^{j}_{i})$ which are all $\sf
False$.

Assume that $\textsf{in}_{t+1}(d_{t+1})$ is $\sf False$ (hence $a=b$). Then
$u^{1}_{1},\dots,u^{1}_{2^{t}}$ are $\sf True$ and all
$u^{2}_{1},\dots,u^{2}_{2^{t}}$ are $\sf False$. The truth value of
$\textsf{out}_{t+1}(v_{2^{t}+b})$ is False because $u^{2}_{b}$ is $\sf False$,
and the truth value of $\textsf{out}_{t+1}(v_{b})$ is True as $u^{1}_{b}$ and
$\textsf{out}_{t}(v_{b}^{1})$ are $\sf True$. Similarly, when
$\textsf{in}_{t+1}(d_{t+1})$ is $\sf True$ (hence $a=b+2^{t}$),
$u^{1}_{1},\dots,u^{1}_{2^{t}}$ are $\sf False$ and all
$u^{2}_{1},\dots,u^{2}_{2^{t}}$ are $\sf True$. Then, the truth value of
$\textsf{out}_{t+1}(v_{b})$ is False as $u^{1}_{b}$ is $\sf False$, and the
truth value of $\textsf{out}_{t+1}(v_{2^{t}+b})$ is True as $u^{2}_{b}$ and
$\textsf{out}_{t}(v_{b}^{1})$ are $\sf True$. Only the output
$\textsf{out}_{t+1}(v_{a})$ is True, hence $C_{t+1}$ is a binary decoder.

By the induction hypothesis and the definition of duplicators and expanders,
our construction of $C_{t+1}$ satisfies conditions (1)-(3). The depth of
$C_{t+1}$ is the depth of $C_{t}$ plus $3$, satisfying condition (4). Finally,
the number of gates of $C_{t+1}$ is twice the number of gates of $C_{t}$ plus
$t+1$ input gates, two $2^{t}$-duplicators, $2^{t+1}$ output gates and their
duplicates, resulting in

$2((8t-3)2^{t-1}-t)+(t+1)+2(2^{t+1}-1)+2\cdot
2^{t+1}=(8(t+1)-3)2^{(t+1)-1}-(t+1)$

gates. This implies that $C_{t+1}$ satisfies condition (5), completing the
proof. ∎

###### Theorem 4.1

Let $k\geq 2$. Every PLS for $\textsc{Convergence}(k,3)$ requires certificates
of size at least $2^{k/6}\cdot 6/{k}$, even when the problem is restricted to
input graphs of degree at most $3$.

###### Proof

Our proof follows similar ideas to the proof of Theorem 3.2. We reduce problem
$\textsc{Convergence}(k,3)$ to Disjointness in two-player communication
complexity. Our construction considers three different gadgets: the _selector_
, _collector_ , and _binary decoder_. In this proof, we explain the lower
bound graph (see Figure 3) alongside the corresponding local functions.

$v^{A}_{1}$$v^{A}_{2}$$\vdots$$\vdots$$v^{A}_{16}$$d^{A}_{1}$$d^{A}_{2}$$d^{A}_{3}$$d^{A}_{4}$$s_{1}$$s_{2}$$s_{3}$$s_{4}$$d^{b}_{1}$$d^{b}_{2}$$d^{b}_{3}$$d^{b}_{4}$$v^{B}_{1}$$v^{B}_{2}$$\vdots$$\vdots$$v^{B}_{16}$$r$$D_{A}$$D_{B}$$S$
Figure 3: Lower-bound graph when $t=4$

The set of states is $Q=\\{{\sf True},{\sf False},\textsf{Error}\\}$. The
local rule of a node varies with each gadget. However, on every node, the
local rule states that when a neighbor is in state Error, the node also
switches to Error. Once in this state, it remains there forever.

Let $t>0$ be a constant that we will fix later. The _selector_ is simply a set
of vertices $S=\\{s_{1},\dots,s_{t}\\}$. Their local function states that they
never switch their initial state unless they have a neighbor in state Error.
The _collector_ $C$ is a complete binary tree rooted in a node $r$, and its
leaves are the elements of $S$. The local rule of the internal nodes of the
collector states that they never switch their initial state unless they have a
neighbor in state Error. The local rule of the root $r$ states that when the
state is different than Error, it negates its own value, switching from ${\sf
True}$ to ${\sf False}$ and vice-versa.

Observe that the selector and collector do converge to a fixed point in at
most $\lceil\log t\rceil$ time-steps if some node is in state Error. Every
configuration where no vertex is in state Error reaches a limit-cycle of
period two.

The _binary decoder gadget_ is constructed from a Boolean circuit as described
in Lemma 1. In the lower-bound graph, we create two copies, $D_{A}$ and
$D_{B}$, of the binary decoder. Each gate in the Boolean circuits is
represented by a node, with links between gates represented as undirected
edges. We denote the inputs and outputs of $D_{A}$ as
$d_{1}^{A},\dots,d_{t}^{A}$ and $v_{1}^{A},\dots,v_{2^{t}}^{A}$, respectively.
Similarly, the inputs and outputs of $D_{B}$ are denoted as
$d_{1}^{B},\dots,d_{t}^{B}$ and $v_{1}^{B},\dots,v_{2^{t}}^{B}$. The local
functions of the nodes in $D_{A}\cup D_{B}$ mirror the Boolean functions of
their corresponding gates. Each node has pointers to identify its incoming and
outgoing neighbors. More precisely, let $g$ be a gate in the binary decoder,
and $u$ be a node in $D_{A}$ or $D_{B}$ simulating $g$. If $g$ is a
disjunction (respectively, conjunction, negation), the local function of $u$
dictates that its state is the disjunction (respectively, conjunction,
negation) of its incoming neighbors. If this condition is not met, node $u$
switches to Error.

Then, we connect $D_{A}$ and $D_{B}$ to the selector. For each $i\in[t]$, we
add the edges $\\{d_{i}^{A},s_{i}\\}$ and $\\{d_{i}^{B},s_{i}\\}$. The local
function of $v_{i}^{A}$ and $v_{i}^{B}$ states that the state of the node
equals that of $s_{i}$. If this condition is not met, the node switches to
Error.

Finally, we modify the rules for nodes simulating the output gates. Let ${\bf
A},{\bf B}\subseteq[2^{t}]$. For each $i\notin{\bf A}$ (respectively,
$i\notin\bf B$), the local function of $v_{i}^{A}$ (respectively, $v_{i}^{B}$)
dictates that, in addition to simulating the Boolean function of the
corresponding output gate of the binary decoder, it switches to $\sf{Error}$
if its state is $\sf{True}$.

We denote the obtained lower-bound graph as $G$ and $F({\bf A,B})$ as the
finite-state dynamic defined over $G$. Observe that the maximum degree of $G$
is $3$. We claim that when ${\bf A}\cap{\bf B}=\emptyset$, the system
$(G,F({\bf A,B}))$ converges to a fixed point in at most $6t$ time-steps. When
${\bf A}\cap{\bf B}\neq\emptyset$, there exists a configuration that does not
converge. Suppose first that there is a value $i\in{\bf A}\cap{\bf B}$. Define
the following configuration over $G$:

  * $\bullet$

The nodes in the collector gadget have all state ${\sf False}$.

  * $\bullet$

For each $j\in[t]$, the value of $s_{j}$ is ${\sf True}$ if the $j$-th digit
in the binary representation of $i$ is $1$, and ${\sf False}$ otherwise.

  * $\bullet$

The gates simulating the inputs of $D_{A}$ and $D_{B}$ are assigned copies of
the truth values of the selector gadgets. The remaining nodes of $D_{A}$ and
$D_{B}$ take the Boolean value of their corresponding gate based on the
evaluation of the binary decoder with the input given by the selector gadget.

Observe that by the construction of the configuration, no vertex is initially
in state $\sf{Error}$. This implies that no node in the selector or the
collector will switch to $\sf{Error}$ unless triggered by another node. Also,
according to the configuration, nodes simulating internal nodes or inputs of
the binary decoder do not switch to $\sf{Error}$. In fact, by the definition
of the binary decoder, only $v_{i}^{A}$ and $v_{i}^{B}$ are in state
$\sf{True}$. Since $i\in{\bf A}\cap{\bf B}$, both nodes remain in their state.
Consequently, no vertex of the graph switches to $\sf{Error}$. As the
collector creates a cycle of period two, we conclude that the system does not
converge.

Now let us suppose that ${\bf A}\cap{\bf B}=\emptyset$, and let $x$ be any
configuration of $G$. If any node in $G$ is in state ${\sf Error}$, that state
spreads through the network, reaching a fixed point where every node is in
state ${\sf Error}$ within at most twice the depth of the binary decoder,
corresponding to $6t$ time-steps. Therefore, let us assume that no vertex is
in state Error in $x$. Let $i\in[2^{t}]$ be the index whose binary
representation is encoded in the selector gadget. If the truth value of any
node in $D_{A}\cup D_{B}$ given by $x$ does not match the truth value of the
corresponding gate in the binary decoder, then that node switches to Error. We
then assume that the truth values of all the nodes in $D_{A}\cup D_{B}$ align
with those of the binary decoder. In particular, nodes $v_{i}^{A}$ and
$v_{i}^{B}$ are True in $x$. Since $i\notin{\bf A}\cap{\bf B}$, either
$v_{i}^{A}$ or $v_{i}^{B}$ switches to Error in the next time-step. In any
case, we obtain that the dynamic reaches a fixed point in at most $6t$ time-
steps for every initial configuration.

We deduce that $(G,F({\bf A,B}))\in\textsc{Convergence}(6t,3)$ if and only if
${\bf A}$ and ${\bf B}$ are yes-instances of Disjointness. Let $\pi$ be a PLS
for $\textsc{Convergence}(6t,3)$. We define the following two-player protocol
$\mathcal{P}$ for Disjointness. Given the instance ${\bf A}$, Alice
nondeterministically computes the certificates that $\pi$ would assign to all
nodes in $D_{A}\cup S$, and simulates the verification protocol of $\pi$ on
all nodes in $D_{A}$. If every node in $D_{A}$ accepts, then Alice
communicates to Bob all the certificates of
$S\cup\\{d_{1}^{A},\dots,d_{t}^{A}\\}$. Otherwise, she communicates one bit
indicating a rejection. Bob computes the certificates of $D_{B}\cup C$ and
simulates the verification protocol of $\pi$ on all nodes in $D_{B}\cup S\cup
C$ using the certificates for $D_{B},C$, and those for $S$ and
$d_{1}^{A},\dots,d_{t}^{A}$ provided by Alice. Bob accepts if the nodes on the
side of Alice accepted, and also ensures that the nodes in $D_{B}\cup S\cup C$
accept. The correctness of $\mathcal{P}$ follows directly from the soundness
and completeness of $\pi$. Alice has communicated $2t$ certificates to Bob.
From Proposition 1, we have that each certificate must be of size at least
$2^{t}/2t$. Defining $k=6t$, we conclude that for graphs of degree at most $3$
and for a $3$-state dynamic, $\textsc{Convergence}(k,3)$ requires certificates
of size $2^{k/6}\cdot 6/k$. ∎

Let $k(n):\mathbb{N}\rightarrow\mathbb{N}$ be a function. For each $q>1$, we
call $\textsc{Convergence}(k(n),q)$ the problem of deciding if a given finite-
state dynamic converges in at most $k(n)$ time-steps on $n$-node graphs.
Observe that the lower-bound graph defined in the proof of Theorem 4.1 has
$(2^{\mathcal{O}(k(n))})$ vertices. Then, by taking $k(n)=\Theta(\log n)$, we
can obtain a linear lower-bound (up to logarithmic factors) for the
certification in graphs of maximum degree at most $3$. More precisely, we
deduce the following corollary.

###### Corollary 2

There exists $k(n)=\Theta(\log n)$ such that every Proof-Labeling Scheme for
the problem $\textsc{Convergence}(k(n),3)$ requires certificates of size
$\tilde{\Omega}(n)$, even when the problem is restricted to input graphs of
degree at most $3$.

##  5 Discussion

In this paper, we study local certification of the problem
$\textsc{Convergence}(t,q)$ which asks whether a finite-state dynamics with
$q$ states converges in at most $t$ time steps. We show that in general there
is an upper bound of
$b_{\text{max}}\cdot\log(\text{id}_{\text{max}})\cdot|f_{\text{max}}|$, and we
show as a lower bound that certificates of size $\Omega(n^{2}/\log n)$ are
required even for $t=2$ and $q=4$. In both cases, the size of the
representation of the function $F$ plays an important role. We present the
following open questions:

  1. 1.

Which specific families of functions might exhibit a succinct representation?
An interesting case study might be studying if the lower bound construction is
still valid in the context of set-valued functions, such as neural networks,
which depend only on the subset of states in the neighborhood.

  2. 2.

How does the difficulty of solving Convergence compare to other decision
problems commonly studied for finite-state dynamics, such as the _reachability
problem_ (determining whether a configuration $y$ is reachable from a starting
configuration $x$ under the dynamics) and the _prediction problem_
(determining if the state of a node will change after $T$ time steps, given a
node, time $T$, and an initial configuration)?

  3. 3.

What is the certification cost for other global properties of $F$, such as
reversibility, injectivity, or nilpotency (where a function is nilpotent if
there is only one possible fixed point)? How are these problems related to
Convergence and at which point are they comparable? Do they require
certificates of bigger size compared to Convergence?

## References

  * [1] Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distributed computing 26(4), 195–208 (2013)
  * [2] Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. science 331(6014), 183–185 (2011)
  * [3] Atlan, H.: Self-organizing networks: weak, strong and intentional, the role of their underdetermination. In: Functional models of cognition: Self-organizing dynamics and semantic structures in cognitive systems, pp. 127–142. Springer (2000)
  * [4] Balliu, A., D’Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? J. Comput. Syst. Sci. 97, 106–120 (2018)
  * [5] Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of reachability problems for finite discrete dynamical systems. Journal of Computer and System Sciences 72(8), 1317–1345 (2006)
  * [6] Bick, A., Kol, G., Oshman, R.: Distributed zero-knowledge proofs over networks. In: 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2426–2458 (2022)
  * [7] Bousquet, N., Feuilloley, L., Pierron, T.: Local certification of graph decompositions and applications to minor-free classes. In: 25th International Conference on Principles of Distributed Systems (OPODIS). LIPIcs, vol. 217, pp. 22:1–22:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
  * [8] Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: International Symposium on Distributed Computing. pp. 148–162. Springer (2010)
  * [9] Costa, F.X., Rozum, J.C., Marcus, A.M., Rocha, L.M.: Effective connectivity and bias entropy improve prediction of dynamical regime in automata networks. Entropy 25(2), 374 (2023)
  * [10] Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In: 33rd International Symposium on Distributed Computing (DISC). LIPIcs, vol. 146, pp. 13:1–13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
  * [11] Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: Proceedings of the 2013 ACM symposium on Principles of distributed computing. pp. 137–146 (2013)
  * [12] Esperet, L., Lévêque, B.: Local certification of graphs on surfaces. Theor. Comput. Sci. 909, 68–75 (2022)
  * [13] Feuilloley, L., Bousquet, N., Pierron, T.: What can be certified compactly? compact local certification of mso properties in tree-like graphs. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. pp. 131–140 (2022)
  * [14] Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. Theor. Comput. Sci. 856, 51–67 (2021)
  * [15] Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. Distributed Computing 34(2), 113–132 (2021)
  * [16] Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Rémila, É., Todinca, I.: Compact distributed certification of planar graphs. Algorithmica pp. 1–30 (2021)
  * [17] Feuilloley, L., Hirvonen, J.: Local verification of global proofs. In: 32nd International Symposium on Distributed Computing. LIPIcs, vol. 121, pp. 25:1–25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
  * [18] Flury, R., Wattenhofer, R.: Slotted programming for sensor networks. In: Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. pp. 24–34 (2010)
  * [19] Fraigniaud, P., Gall, F.L., Nishimura, H., Paz, A.: Distributed quantum proofs for replicated data. In: 12th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 185, pp. 28:1–28:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
  * [20] Fraigniaud, P., Montealegre, P., Rapaport, I., Todinca, I.: A meta-theorem for distributed certification. In: 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 13298, pp. 116–134. Springer (2022)
  * [21] Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distributed Computing 32(3), 217–234 (2019)
  * [22] Frischknecht, S., Keller, B., Wattenhofer, R.: Convergence in (social) influence networks. In: Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings 27. pp. 433–446. Springer (2013)
  * [23] Gadouleau, M.: On the stability and instability of finite dynamical systems with prescribed interaction graphs. The Electronic Journal of Combinatorics pp. P3–32 (2019)
  * [24] Gadouleau, M.: On the influence of the interaction graph on a finite dynamical system. Natural Computing 19(1), 15–28 (2020)
  * [25] Gadouleau, M., Richard, A.: Simple dynamics on graphs. Theoretical Computer Science 628, 62–77 (2016)
  * [26] Goles, E., Montealegre, P.: Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science 559, 3–19 (2014)
  * [27] Göös, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory of Computing 12(1), 1–33 (2016)
  * [28] Guseo, R., Guidolin, M.: Modelling a dynamic market potential: A class of automata networks for diffusion of innovations. Technological Forecasting and Social Change 76(6), 806–820 (2009)
  * [29] Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: ACM Symposium on Principles of Distributed Computing. pp. 255–264. ACM (2018)
  * [30] Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distributed Comput. 22(4), 215–233 (2010)
  * [31] Kushilevitz, E.: Communication complexity. In: Advances in Computers, vol. 44. Elsevier (1997)
  * [32] Maldonado, D., Montealegre, P., Ríos-Wilson, M., Theyssier, G.: Local certification of majority dynamics. arXiv preprint arXiv:2309.01852 (2023)
  * [33] Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1096–115. SIAM (2020)
  * [34] Ríos-Wilson, M., Theyssier, G.: Intrinsic Simulations and Universality in Automata Networks (Sep 2022), https://hal.science/hal-03779748, preprint