On the Complexity of Concurrent Multiset Rewriting

Marin Bertier (1) , Matthieu Perrin (2) , Cédric Tedeschi (3)

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
2 LINA - Laboratoire d'Informatique de Nantes Atlantique
3 MYRIADS - Design and Implementation of Autonomous Distributed Systems

While the complexity of the digital infrastructures surrounding us seems to increase continuously, autonomic computing appears as a promising paradigm to be explored. The quest for adequate high-level abstractions to program autonomic systems led to the reemergence of rule-based programming as a promising paradigm. Also, nature appears to be a great source of inspiration. The chemical analogy was at the origin of the so-called chemical programming model, a rule-based programming model enhanced with a chemically-inspired execution model, making it a promising candidate to develop autonomic systems. The metaphor envisions a computation as a set of concurrent reactions between molecules of data arising non-deterministically, until no more reactions can take place, in which case, the solution contains the final outcome of the computation. More formally, such models strongly rely on concurrent multiset rewriting: the data are a multiset of molecules, and reactions are the application of a set of conditioned rewrite rules. At run time, these rewritings are applied concurrently, until no rule can be applied anymore (the elements they need do not exist anymore in the multiset). One of the main barriers towards the actual adoption of such models come from their complexity at run time: each computation step may require a complexity in O(n^k) where n denotes the number of elements in the multiset, and k the size of the subset of elements needed to trigger one rule. In this paper, we explore the possibility of improving the complexity of searching elements (or "reactants") through a static analysis of the reaction condition. In particular, through the modeling of the problem with graphs, we give a characterisation of this complexity, based on the results of the well-known subgraph isomorphism problem. This allows us then to give an algorithm for searching reactants, that can be easily parallelised, and whose complexity is lower than the basic case, most of the time.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Marin Bertier, Matthieu Perrin, Cédric Tedeschi. On the Complexity of Concurrent Multiset Rewriting. [Research Report] RR-8408, INRIA. 2013, pp.17. ⟨hal-00912554⟩