Parallel independence

[kris-brown]

Given a set of (DPO) rewrite rules with matches, we can easily check if they only overlap in preserved parts of their patterns (no rule deletes something that is referenced by any other rule).

In this scenario, we can combine the rules to form one big rule that is executed concurrently.

[slwu89]

@kris-brown naively, it seems like tools that can identify parallel independence could also analyze conflict sets in matches. I can't recall the details on how it works with general graph grammars but I'm reminded of work on this for petri nets in discrete time (or for continuous time simulations with stuff that can happen simultaneously as you remark in AlgebraicJulia/AlgebraicABMs.jl#10).

The idea for discrete time PNs was given in this paper by Molloy Discrete time stochastic petri nets (1985) although the part about computing the actual conflict sets and "legal firing sets" (sets that describe one or more rule applications that do not conflict) is unfortunately more of a sketch than an algorithm; the paper is concerned with describing how to compute the probabilities of each of those firing sets, via Gaussian elimination. But I'll paraphrase the relevant bits and ask: is there anything in the graph grammar literature that could let us easily do this? Does anything in the follow description seem related to problems you have worked on? Clearly if it could be done for PNs, it could work for general rewriting systems, but this is the angle I'm familiar with so here goes.

Define a set of transitions $T_c \subset T$ to be a conflict set if the firing of any subset ${ t_i } \subset T_c$ results in a marking such that some other transition $t_j \in T_c, j \notin { t_i }$ is disabled. A set $T_e \subset T$ is mutually exclusive if it is a conflict set and if the firing of any individual transition in it disables all others.

Each element of the set of legal firings is a set of transitions (not multiset; this tacitly assumes that on a "time step" each transition can fire at most once), that can be executed in parallel. Each element is associated with a probability, and the sum of all of them is 1, the rest of the paper is about how to compute these composite probabilities from the basic probability given to each transition independently. Updating state means picking one element from the set of legal firings according to these probabilities and applying that big composite update.

To build this set, Molloy says we take all the transitions that are not in conflict with anyone else, and each of them to their own "class". Then, we somehow find all the conflict sets, and send each transition to its conflict set. Then we get a partition over the enabled transitions. The state changes caused by each class in the partition are independent from the standpoint of disabling transitions in other classes, by construction.

He then says that any legal firing (an element in the set of legal firings) "will be made up of subsets, possibly empty, form each class in the partition. In cases where the class size is greater than 1, there will be some transitions which can fire, but not all. In particular, if the class is a mutually exclusive set of transitions, then the maximal subset size is 1. Therefore, the set of all legal firings will be the set of all possible unions of each legal subset in each class."

The below example is given where the 3 transitions form a conflict set. The set of legal firings contains the empty set (everything is enabled, but nothing happens), as well as 3 sets each containing each individual transition, and 3 sets containing each possible pair of transitions.