Search

Among the fundamental questions in computer science is that of the impact of synchronism/asynchronism on computations, which has been addressed in various fields of the discipline: in programming, in networking, in concurrence theory, in artificial learning, etc. In this paper, we tackle this question from a standpoint which mixes discrete dynamical system theory and computational complexity, by highlighting that the chosen way of making local computations can have a drastic influence on the performed global computation itself. To do so, we study how distinct update schedules may fundamentally change the asymptotic behaviors of finite dynamical systems, by analyzing in particular their limit cycle maximal period. For the message itself to be general and impacting enough, we choose to focus on a ``simple'' computational model which prevents underlying systems from having too many intrinsic degrees of freedom, namely elementary cellular automata. More precisely, for elementary cellular automata rules which are neither too simple nor too complex (the problem should be meaningless for both), we show that update schedule changes can lead to significant computational complexity jumps (from constant to superpolynomial ones) in terms of their temporal asymptotes.

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 $\text{convergence}$ from the perspective of distributed certification, with a focus on the model of proof-labeling schemes (PLS). First, we study the problem $\text{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.

In this paper, we explore the dynamic behavior of threshold networks on undirected signed graphs. Much attention has been dedicated to understand the convergence and long-term behavior of this model. Yet, an open question persists: How does the underlying graph structure impact network dynamics? Similar studies have been carried out for threshold networks and other types of networks, but these primarily focus on unsigned networks. Here, we address the question on signed threshold networks. We introduce the stability index of a graph, related to the concepts of frustration and balance in signed graphs, to establish a connection between the structure and the dynamics of such networks. We show that graphs which present a negative stability index exhibit stable dynamics, i.e., the dynamics converges to fixed points regardless of its threshold parameters. Conversely, if at least one subgraph has a positive stability index, oscillations in long term behavior may appear. Furthermore, we generalize the analysis to network dynamics under periodic update modes and explore the case of the existence of some subgraph with a positive stability index, for which we find that attractors of super-polynomial period in the size of the network may appear.

In majority voting dynamics, a group of $n$ agents in a social network are asked for their preferred candidate in a future election between two possible choices. At each time step, a new poll is taken, and each agent adjusts their vote according to the majority opinion of their network neighbors. After $T$ time steps, the candidate with the majority of votes is the leading contender in the election. In general, it is very hard to predict who will be the leading candidate after a large number of time-steps. We study, from the perspective of local certification, the problem of predicting the leading candidate after a certain number of time-steps, which we call Election-Prediction. We show that in graphs with sub-exponential growth Election-Prediction admits a proof labeling scheme of size $\mathcal{O}(\log n)$. We also find non-trivial upper bounds for graphs with a bounded degree, in which the size of the certificates are sub-linear in $n$. Furthermore, we explore lower bounds for the unrestricted case, showing that locally checkable proofs for Election-Prediction on arbitrary $n$-node graphs have certificates on $\Omega(n)$ bits. Finally, we show that our upper bounds are tight even for graphs of constant growth.

Cells in a fungal hyphae are separated by internal walls (septa). The septa have tiny pores that allow cytoplasm flowing between cells. Cells can close their septa blocking the flow if they are injured, preventing fluid loss from the rest of filament. This action is achieved by special organelles called Woronin bodies. Using the controllable pores as an inspiration we advance one and two-dimensional cellular automata into Elementary fungal cellular automata (EFCA) and Majority fungal automata (MFA) by adding a concept of Woronin bodies to the cell state transition rules. EFCA is a cellular automaton where the communications between neighboring cells can be blocked by the activation of the Woronin bodies (Wb), allowing or blocking the flow of information (represented by a cytoplasm and chemical elements it carries) between them. We explore a novel version of the fungal automata where the evolution of the system is only affected by the activation of the Wb. We explore two case studies: the Elementary Fungal Cellular Automata (EFCA), which is a direct application of this variant for elementary cellular automata rules, and the Majority Fungal Automata (MFA), which correspond to an application of the Wb to two dimensional automaton with majority rule with Von Neumann neighborhood. By studying the EFCA model, we analyze how the 256 elementary cellular automata rules are affected by the activation of Wb in different modes, increasing the complexity on applied rule in some cases. Also we explore how a consensus over MFA is affected when the continuous flow of information is interrupted due to the activation of Woronin bodies., Comment: 31 pages, 30 figures

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. As a complement, we develop a proof technique to establish intrinsic simulation and universality results which is suitable to deal with families of symmetric networks were connections are non-oriented. It is based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks. As an illustration, we give a short proof that the family of networks were each node obeys the rule of the 'game of life' cellular automaton is strongly universal. This formalism and proof technique is also applied in a companion paper devoted to studying the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks., Comment: arXiv admin note: substantial text overlap with arXiv:2105.08356

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $\Omega(n)$ bits.

We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is \textbf{P}-Hard.

We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.

An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network's graph. It is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. In this paper we establish how treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general model checking formalism that captures many classical decision problems: prediction, nilpotency, predecessor, asynchronous reachability. Then, on one hand, we present an efficient parallel algorithm that solves the general model checking problem in NC for any graph with bounded degree and bounded treewidth. On the other hand, we show that these problems are hard in their respective classes when restricted to families of graph with polynomially growing treewidth. For prediction, predecessor and asynchronous reachability, we establish the hardness result with a fixed set-defiend update rule that is universally hard on any input graph of such families.

In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each time-step only one cell is updated. Given configuration, we say that a cell is unstable if there exists a sequential updating scheme that changes its state. In this context, we define the problem AsyncUnstability, which consists in deciding if a cell is unstable or not. In general AsyncUnstability is in NP, and we study in which cases we can solve the problem by a more efficient algorithm. We begin showing that AsyncUnstability is in NL for any one-dimensional FCA. Then we focus on the family of life-like freezing CA (LFCA), which is a family of two-dimensional two-state FCA that generalize the freezing version of the game of life, known as life without death. We study the complexity of AsyncUnstability for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NP-complete.