Causal rewrite systems reframe graph dynamics with missing information
From Border-Agnosticism to Causal Rewrite Systems
Discrete MathematicsDistributed, Parallel, and Cluster Computing
Summary
Graphs can change over time, but sometimes parts are missing or unclear, called borders. The authors look at these borders as bits of missing information instead of problems. This new view lets them treat graph changes more like step-by-step rewriting rules, making it easier to understand how to reverse changes. Their work reshapes how complex graph systems with asynchronous updates can be handled more precisely.
What this means in practice
- •For distributed systems engineers: Model and manage asynchronous graph updates with clearer structure to support reversible operations in networked systems.
- •For programming language designers: Design languages or tools that incorporate controlled graph rewriting with reversible behaviors guided by explicit border interpretations.
A theory result. No direct application yet.
Authors
Pablo Arrighi, Marin Costes, Luidnel Maignan
Abstract
Causal Graph Rewriting was recently introduced as an evolution of Causal Graph Dynamics to allow for a controlled form of asynchronism in these dynamical systems with dynamical graphs. In this context, the notion of borders---akin to dangling edges---has gained increasing importance. In this paper, we re-examine these borders, interpreting them as missing information. This perspective adds structural rigor to the framework, allowing border-agnostic causal graph rewriting to be reformulated as a rewriting system rather than a dynamical system. This shift represents a crucial step toward facilitating the treatment of reversibility.