🌀 nonlinear sciences

Causal graph rewriting

This paper introduces causal graph rewriting, an asynchronous computational model on directed acyclic graphs where oriented edges serve as both dependencies and mutable locality constraints, establishing that local rules preserve structural context and can simulate any one-dimensional cellular automaton.

Original authors: Pablo Arrighi, Marin Costes, Luidnel Maignan

Published 2026-09-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pablo Arrighi, Marin Costes, Luidnel Maignan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the study of how things change over time, scientists often rely on a simple, rhythmic idea: that the entire universe updates itself all at once, like a flipbook where every page turns in perfect unison. This concept, known as a global clock, works well for describing grid-like systems, such as the pixels on a screen or the cells in a biological simulation, where every part moves forward together. However, this synchronized view clashes with our deepest understanding of the physical world. In the real universe, there is no master clock ticking for everyone; events happen at different times depending on where you are and how fast you are moving. This is the realm of relativity, where time is flexible and local. For decades, computer scientists have struggled to build models of computation that respect this reality, creating systems where different parts of a network can evolve at their own pace without needing a central coordinator. The challenge has been to ensure that even when updates happen in a chaotic, non-synchronized order, the final result remains logical and consistent, rather than descending into confusion.

A team of researchers has now introduced a new framework called causal graph rewriting, a method that allows complex systems to evolve asynchronously while maintaining a strict order of cause and effect. Instead of forcing every part of a system to wait for a global signal, this approach treats the system as a collection of events connected by dependencies. Imagine a network of tasks where one task cannot begin until the tasks it relies on are finished. In this new model, the system is represented as a map of these tasks, where the connections between them act as both the rules for how information flows and the constraints that prevent chaos. The researchers showed that by applying simple, local rules to this map, the system can update itself piece by piece. Crucially, these rules are designed so that they only change the immediate area around an event, leaving the rest of the system untouched until it is ready. This ensures that even though the system is updating in a scattered, unpredictable way, the overall structure remains coherent and the history of the system is preserved.

The power of this approach lies in its ability to handle two very different kinds of behavior. First, the researchers demonstrated that their system can perfectly mimic traditional, synchronized computers. By carefully arranging the dependencies between events, they showed that any standard computer program running on a fixed grid could be simulated within this asynchronous framework. This proves that the new method is powerful enough to do everything old methods can do, but with the added flexibility of not needing a global clock. Second, and perhaps more significantly, the model can describe phenomena that are impossible to capture with a synchronized clock. The team illustrated this with a scenario resembling time dilation, a concept from physics where time passes at different rates in different places. In their simulation, they created a system where a specific region of the network slowed down the flow of time for everything passing through it, simply by changing the local connections. This happened naturally, without any external force telling the system to slow down, showing that the geometry of the system itself can dictate the speed of time.

The researchers proved that this system is robust, meaning that the local rules they designed do not break down when applied one after another. They showed that if a single rule respects the boundaries of its neighborhood, then a long sequence of rules will also respect those boundaries, no matter how complex the chain of events becomes. This is a vital finding because it guarantees that the system remains predictable and well-behaved even as it grows. The team also noted that while the system is designed to be deterministic in a specific sense—meaning the final state of any specific event is expected to be the same regardless of the path taken to get there—the complete proofs establishing that any two update schedules will always agree on the state of every event are left for future research. A separate article is planned to unravel the additional properties needed for this "space-time determinism" and provide a self-contained presentation of the proof material.

This work offers a new way to think about how complex systems evolve, from computer networks to physical theories of space and time. By moving away from the idea of a universal clock and embracing a model where time is local and dependent on connections, the researchers have created a tool that is both mathematically rigorous and physically intuitive. Their findings suggest that it is possible to build computational models that are as flexible as the universe itself, capable of handling the irregular, asynchronous nature of real-world processes without losing the ability to predict outcomes. This opens the door to more efficient simulations of distributed systems and provides a fresh perspective on how to model the dynamic geometry of space-time, bridging the gap between the rigid logic of computer science and the fluid reality of physics.

Technical Summary: Causal Graph Rewriting

Problem Statement
Traditional models of dynamical systems, such as cellular automata (CA) and causal graph dynamics (CGD), rely on a global clock to synchronize updates across a spatial structure (grid or graph). While effective, this synchronism is often criticized as an artificial constraint that hinders parallelism in distributed computing and fails to capture the asynchronous nature of physical phenomena, particularly in relativistic contexts where no universal time exists. Existing asynchronous rewriting theories often lack a rigorous framework for "space-time determinism"—the guarantee that the final state of a system is independent of the specific order in which asynchronous updates occur. The paper addresses the need for a model that allows local rules to act asynchronously on directed acyclic graphs (DAGs) while maintaining a well-defined causal structure and preserving locality properties under sequential composition.

Methodology
The authors introduce Causal Graph Rewriting (CGR), a computational model where configurations are represented as port-labelled directed acyclic graphs (DAGs).

Graph Formalism: Vertices represent events (computational processes) named $t.x$ (time tag $t$ , position $x$ ). Edges encode dependencies (computational causality) and locality constraints. The graphs include "border" vertices to handle partial views and "dangling" edges, allowing for the composition of subgraphs.
Neighbourhood Schemes: A local rule operates on a "cone" of the graph (a connected subgraph reachable from a past vertex). The authors define a neighbourhood scheme $N$ that selects a specific cone $G_{N_x}$ around a position $x$ . Crucially, this scheme must satisfy extensivity: the neighbourhood selected for a graph must be identical to that selected for any of its subgraphs containing the necessary information, ensuring the rule does not depend on global properties.
Local Rules: A local rule $A_x$ acts on the induced subgraph $G_{N_x}$ . It consumes the current vertex $t.x$ , updates its internal state and dependencies, and creates a new vertex $(t+1).x$ . The rule must preserve the graph's border (dangling edges) and acyclicity.
Sequential Dynamics: Computation proceeds via valid sequences of positions $\omega = x_n \dots x_1$ , where each step is applied only if the position is "past" (ready to fire) in the current graph. The collection of all possible graphs generated by all valid sequences forms the space-time diagram.

Key Contributions

Structural Properties of Local Rules: The paper formalizes the conditions under which local rules are well-defined. It proves that valid local rules inherently preserve positions (no new positions are created, only time tags are updated) and boundaries (vertices and edges at the interface between the modified region and the context are preserved).
Simulation of Cellular Automata: The authors demonstrate the expressivity of the model by formally proving that any one-dimensional cellular automaton can be simulated within CGR. This is achieved using a "marching soldiers" encoding where the DAG of dependencies tracks the relative advancement of computations, effectively simulating synchronous behavior through asynchronous scheduling.
Time-Dilation Example: A novel example is provided where the local rule modifies the graph's topology (reversing edges) based on internal states (green/red "dilation" particles). This results in different regions of the graph advancing at different rates, mimicking time dilation in general relativity without a global clock.
$\ast$ -Locality and $\ast$ -Extensivity (Main Result): The paper's primary technical contribution is the proof that locality is preserved under sequential composition.
- $\ast$ -Extensivity: The neighbourhood of a sequence of updates depends only on the initial graph's relevant subgraph.
- $\ast$ -Locality: The effect of applying a sequence of rules $A_\omega$ to a graph $G$ is identical to applying it to the induced subgraph $G_{N_\omega}$ and then recomposing it with the unchanged context.
- This is proven via an inductive bootstrapping argument (Lemmas 5.2 and 5.4) showing that if a rule is local for single steps, it remains local for arbitrary valid sequences.

Results

Theorem 4.1: Establishes a rigorous correspondence between the space-time diagram of a CGR simulation and the evolution of a radius-one-half cellular automaton, proving that the asynchronous model can reproduce synchronous dynamics.
Theorem 5.1: Proves that any local rule in the CGR framework is automatically $\ast$ -local and $\ast$ -extensive. This ensures that the structural properties (position preservation, boundary preservation) derived for single steps extend canonically to arbitrary finite sequences of rule applications.
Corollary 5.1: Confirms that even for sequences, the action of the rule is confined to the interior of the computed neighbourhood, leaving the boundary and context untouched.

Significance and Claims
The paper claims that Causal Graph Rewriting provides a principled framework for lightweight synchronization in distributed computation. By encoding dependencies directly into the graph structure, it allows different regions to advance at their own pace without global coordination, while the causal order ensures no event is processed before its inputs are ready.

The authors position CGR as the asynchronous counterpart to Causal Graph Dynamics, filling a gap in the trajectory from classical to reversible to quantum dynamical systems (as illustrated in Figure 1). The model is presented as a step toward discrete models of general relativity, where space-time geometry is dynamic and state-dependent.

The paper explicitly states that while it establishes the structural robustness of the model (via $\ast$ -locality), the full space-time determinism theorem (guaranteeing that all schedulings agree on event states) is the subject of a companion paper [1]. The current work provides the necessary prerequisites (specifically the locality of sequences) to support that determinism proof. The authors do not claim to model physical gravity directly but rather to explore how local computational rules can give rise to dynamic, state-dependent topologies reminiscent of relativistic effects.

Technical Summary: Causal Graph Rewriting

More like this