💻 computer science

Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$

This paper introduces the Concurrent Paths (CP) algorithm, which improves concurrency detection in acyclic sound free-choice workflow nets to a worst-case complexity of $O(P^2 + T^2)$ , offering significant performance benefits over existing methods when nets contain many concurrent nodes.

Original authors: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are managing a massive, complex factory. In this factory, there are many different stations (called places) and machines (called transitions) that move products along a conveyor belt system. Sometimes, the factory is designed so that two different machines can work at the exact same time without getting in each other's way. This is called concurrency.

Knowing which machines can run in parallel is crucial. It helps you understand how the factory works, find bottlenecks, and ensure the system doesn't crash. However, figuring out exactly which pairs of machines can run together in a huge, tangled factory is a massive math problem.

The Old Way: The Slow Detective

For a long time, the best way to solve this was a method developed by Kovalyov and Esparza (let's call them the "Old Detectives"). Their method works well, but it has a flaw: if the factory has a lot of machines running in parallel, the time it takes to figure everything out explodes.

Imagine the Old Detectives are trying to check every single pair of machines to see if they can work together. If you have 1,000 machines, they might have to check millions of pairs. If the factory is full of parallel activity, their notebook gets so big that the calculation takes forever.

The New Way: The "Concurrent Paths" (CP) Algorithm

This paper introduces a new, smarter detective method called the Concurrent Paths (CP) algorithm. It is designed specifically for factories that follow a few specific rules (called "sound free-choice workflow nets").

Here is how the new method works, using simple analogies:

1. The "No-Path" Rule (For Simple Factories)
First, the authors looked at factories that don't have any loops (no conveyor belts that circle back on themselves). They realized a simple truth: If Machine A and Machine B can work at the same time, there is no direct road connecting them. If there is a road from A to B, A must finish before B starts, so they can't be concurrent.

The new algorithm uses this rule. Instead of checking every single pair of machines one by one, it maps out all the roads (paths) in the factory.

The Analogy: Imagine you have a map of the factory. Instead of asking "Can A and B work together?" for every pair, you just look at the map. If you see a road from A to B, you instantly know they can't be concurrent. If there is no road, and they are in the right part of the factory, they can be.
The Result: This turns a slow, heavy calculation into a much faster one. For simple, non-looping factories, the new method is quadratic (it scales much better). If the factory size doubles, the time doesn't explode; it just grows steadily.

2. The "Loop" Trick (For Factories with Circles)
Many real factories have loops (machines that repeat a process). The old method handles loops, but the new "No-Path" rule gets tricky there.

To fix this, the CP algorithm uses a technique called Loop Decomposition.

The Analogy: Imagine a factory with a giant circular track. The new method takes a pair of scissors and cuts the circle, turning it into a straight line for a moment. It analyzes the straight line (which is easy and fast), and then "glues" the circle back together in its mind.
The Result: Even though this "cutting and gluing" takes some extra time, it allows the algorithm to use the fast "No-Path" rule on the pieces.

The Big Test: Does it actually work?

The authors tested their new algorithm against the old "Old Detectives" using a real-world dataset of 644 factory models (from IBM).

The Winner: The new CP algorithm was about 50 times faster overall.
The Sweet Spot: The new method shines when the factory is very busy with lots of things happening at once. In one specific test case with 42,000 pairs of concurrent machines, the old method took over 10 seconds, while the new method took less than half a second.
The Caveat: If the factory is very simple and has very few things happening at once, the new method is slightly slower because it spends a little time drawing the map first. But for complex, busy systems, it is a massive improvement.

Summary

Think of the old method as a person walking through a maze checking every single wall to see if it's a dead end. The new method is like a person with a drone that flies over the maze, sees the whole map at once, and instantly knows which paths are open.

This paper claims that for a specific type of system (sound free-choice workflow nets), this new "drone" approach (the CP algorithm) is a much more efficient way to find out what can happen in parallel, especially when the system is large and complex. It doesn't claim to fix every type of system, but for the ones it targets, it pushes the limits of speed significantly.

Technical Summary: Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in O(P² + T²)

Problem Statement
Concurrency detection in Petri nets is a fundamental prerequisite for analyzing complex system behaviors, particularly in business process management. Identifying which places and transitions can execute in parallel enables the derivation of other behavioral relations (e.g., causality, exclusivity) and facilitates similarity measurements. While existing algorithms, specifically those by Kovalyov and Esparza (KovEs), provide solutions for live and bounded free-choice nets, their computational complexity can become prohibitive for large nets with high degrees of concurrency. The KovEs algorithm operates with a time complexity of $O((P + T)TP^2)$ for general live and bounded nets and $O(P(P + T)^2)$ for live and bounded free-choice nets. In practice, when nets contain numerous concurrent node pairs, these algorithms suffer from significant computation times. Furthermore, existing decomposition approaches (e.g., SESE fragments) often fail when nets contain unstructured fragments (rigids), necessitating the use of general, higher-complexity techniques.

Methodology
The paper introduces the Concurrent Paths (CP) algorithm, designed specifically for sound free-choice workflow nets (FW-nets). The methodology relies on two primary theoretical pillars:

Path-to-End Theorem: In sound FW-nets, no reachable marking contains more than one token on any acyclic path to the sink. This implies that if two nodes are concurrent, there can be no path between them.
Revised Concurrency Logic: The authors revise the observations used in the KovEs algorithm. They establish that for sound acyclic free-choice workflow nets (AFW-nets), two nodes $x$ and $s$ are concurrent if and only if there is no path from $x$ to $s$ (and vice versa), provided they are already linked via a known concurrent pair.

The CP algorithm proceeds in two stages:

For Acyclic Nets (AFW-nets): The algorithm computes a HasPath relation (determining reachability) for all nodes. It then iterates through initial concurrent pairs (derived from transitions with multiple output places or initial tokens). For each pair $(x, y)$ , it calculates the set of nodes reachable from $x$ but not $y$ ( $\bar{R}^y_x$ ) and the set of nodes reachable from $y$ but not $x$ . Based on the revised logic, it directly adds concurrency relations between these disjoint sets, avoiding the iterative pair-by-pair expansion used in KovEs.
For Cyclic Nets: The algorithm employs loop decomposition. It identifies loops (strongly connected components) and replaces them with single "loop places," effectively decomposing the cyclic net into a set of acyclic nets. The CP algorithm is applied to each resulting acyclic net. Finally, the concurrency relations are recombined by mapping the concurrency of the virtual loop places back to the actual nodes within the original loops.

Key Contributions

New Algorithm (CP): A novel algorithm for concurrency detection in sound free-choice workflow nets that leverages path analysis rather than iterative state exploration.
Improved Complexity for Acyclic Nets: The CP algorithm achieves a worst-case time complexity of $O(P^2 + T^2)$ for acyclic nets. This represents a significant improvement over the $O(P(P + T)^2)$ complexity of the KovEs algorithm for this specific class of nets.
Handling Cyclic Nets: The paper extends the approach to cyclic nets via loop decomposition. While the worst-case complexity for cyclic nets remains cubic at $O(P^3 + PT^2)$ (matching KovEs), the authors argue that the worst-case scenario (many nested loops) is rare.
Parallelizability: The CP algorithm is inherently well-suited for parallelization. The decomposition into acyclic nets allows for parallel processing of sub-nets, and the computation of HasPath and subsequent relation updates can be parallelized.

Results and Evaluation
The authors evaluated the CP algorithm against the KovEs algorithm using the IBM Websphere Business Modeler dataset (644 sound FW-nets).

Performance on High Concurrency: The CP algorithm demonstrated substantial speedups on nets with a high degree of concurrency. In one specific case involving approximately 42,000 concurrent pairs, CP required 45 ms compared to 10,500 ms for KovEs. Across 87 nets with high concurrency, CP was approximately 82 times faster.
Performance on Low Concurrency: For nets with low concurrency (the majority of the dataset), the KovEs algorithm performed slightly better due to the "startup cost" of the CP algorithm (computing paths and decomposing loops). However, the overhead was minimal.
Scalability: The evaluation indicated that the computational load of KovEs increases quadratically with the number of concurrent pairs, whereas the load for CP increases linearly.
Cyclic Nets: On the 40 cyclic nets in the dataset, KovEs was faster (16 ms vs. 43 ms), attributed to the overhead of loop decomposition and the low ratio of concurrent nodes in those specific nets. However, the authors note that when a cyclic net with high concurrency was tested, CP remained competitive.

Significance and Claims
The paper claims that the CP algorithm complements the existing palette of concurrency detection tools, specifically optimizing performance for sound free-choice workflow nets.

Efficiency: The primary significance lies in the ability to handle nets with many concurrent nodes efficiently, reducing computation time from quadratic/cubic dependencies on node counts to a more manageable quadratic dependency on the number of nodes for acyclic cases.
Practicality: The authors emphasize that while the worst-case complexity for cyclic nets is not improved, the worst-case scenario (highly nested loops) is infrequent in practice. Therefore, the average-case performance is expected to be superior, particularly for large-scale process mining or indexing tasks where nets are analyzed in bulk.
Future Utility: The authors suggest that this efficiency enables more effective indexing of nets in querying languages and facilitates the derivation of other behavioral relations (causality, exclusivity) in business process management and information systems research.

The paper maintains a modest stance, acknowledging that for nets with low concurrency or specific cyclic structures, the traditional KovEs algorithm may still be preferable, but asserts that CP offers a robust alternative for the growing class of complex, highly concurrent workflow models.

The Old Way: The Slow Detective

The New Way: The "Concurrent Paths" (CP) Algorithm

The Big Test: Does it actually work?

Summary

More like this