Supporting Modularity by (De-)Composition of Distributed P/T Nets Based on Karger’s Algorithm for Distributed Execution
摘要
Systems grow in complexity, inflating model size and structural density. Place/Transition (P/T) nets are a standard formalism, but large instances strain editing, simulation, and verification. A modular perspective treats distributed P/T nets as composable units with a module interface. The research question is how to define and operationalize a concept of interface-guided modularity via Decomposition and Composition so that large P/T net models become more tractable while preserving interface compatibility. Decomposition and composition are defined over interfaces via distributed synchronous channels and realized as a proof of concept (PoC) in Renew using constructivist prototyping. Decomposition applies Karger’s randomized contraction algorithm to an undirected graph derived from the net, yielding a cut that induces subnet boundaries and interfaces. The PoC selects the minimum cut to minimize cross-partition coupling and distributed communication. Composition reconciles interfaces by aligning and merging required interface elements. Runtime is analyzed with respect to the interface-based definitions, and benchmarks are evaluated by wall-clock time, the throughput, and the runtime-to-net-size ratio. Asymptotic bounds are derived for both operations. NetSplit scales as \(\mathcal {O}(n^{2}+n\cdot t)\) , where \(n\) is the number of nodes and \(t\) the number of transitions. NetJoin is bounded by \(\mathcal {O}\left( \sum _{i=1}^{n} m_i\cdot l\right) \) , where \(m_i\) is the number of net elements in the \(i\) -th net and \(l\) the number of distributed synchronous channels to be reconciled during composition. Interface-guided modularization improves operational efficiency for complex Petri net models, makes larger nets more tractable, and supports dynamic repartitioning in distributed simulation and verification.