Distributed multiset reaction systems

We develop a process-algebraic framework for multiset reaction systems (MRSs), in which both reactions and system states are represented as multisets rather than sets. This representation enables quantitative reasoning about resources and naturally supports nondeterministic behaviour: unlike standard reaction systems, unconsumed resources persist into the next state, and several maximally enabled multisets of reactions may coexist at the same state. We equip the framework with a compositional operational semantics defined by structural operational semantics (SOS) rules, introduce a process representation for MRSs and the notion of maximal interactive processes, and prove that the induced labelled transition system faithfully corresponds to the rewriting dynamics of MRSs (Theorem 1). Building on this foundation, we extend the framework to distributed multiset reaction systems (DMRSs), in which processes are located at nodes of a network and communicate asynchronously by sending products to neighbouring locations. A distinguishing feature of the model is that reactions may dynamically modify the network topology through controlled division mechanisms, thereby integrating locality, asynchronous communication, and structural evolution within a single operational semantics. Finally, we investigate the computational power of DMRSs by studying their ability to solve the NP-complete Subset Sum problem. We present two constructions: a semi-uniform one, in which a dedicated DMRS is built for each problem instance, and a uniform one, in which a single DMRS handles all instances of a fixed size while the instance parameters are supplied as contextual resources. In both cases the system solves Subset Sum in at most $$2n+3$$ 2 n + 3 computation steps, where n is the number of input integers, by exploiting nondeterminism and large-scale parallelism: division generates all 2ⁿ 2 n candidate subsets in parallel, and resource-based cancellation detects valid solutions. These results demonstrate that DMRSs constitute a powerful and flexible formal framework for distributed, resource-driven computation.