💻 computer science

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

Dit artikel introduceert het Concurrent Paths (CP) algoritme, dat de detectie van gelijktijdigheid in acyclische sound free-choice workflow nets verbetert naar een worst-case complexiteit van $O(P^2 + T^2)$ , wat aanzienlijke prestatievoordelen biedt ten opzichte van bestaande methoden wanneer nets veel gelijktijdige knopen bevatten.

Oorspronkelijke auteurs: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Gepubliceerd 2026-02-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, complexe fabriek beheert. In deze fabriek zijn er veel verschillende stations (genaamd plaatsen) en machines (genaamd transities) die producten langs een lopend band systeem bewegen. Soms is de fabriek zo ontworpen dat twee verschillende machines tegelijkertijd kunnen werken zonder elkaar in de weg te zitten. Dit wordt concurrency (gelijktijdigheid) genoemd.

Weten welke machines parallel kunnen draaien is cruciaal. Het helpt je te begrijpen hoe de fabriek werkt, knelpunten te vinden en te zorgen dat het systeem niet vastloopt. Echter, het uitzoeken van precies welke paren machines samen kunnen draaien in een enorme, verstrengelde fabriek is een massaal wiskundig probleem.

De Oude Manier: De Langzame Detective

Lamaag was de beste manier om dit op te lossen een methode ontwikkeld door Kovalyov en Esparza (laten we ze de "Oude Detectives" noemen). Hun methode werkt goed, maar heeft een gebrek: als de fabriek veel machines heeft die parallel draaien, explodeert de tijd die nodig is om alles uit te zoeken.

Stel je voor dat de Oude Detectives proberen elk enkel paar machines te controleren om te zien of ze samen kunnen werken. Als je 1.000 machines hebt, moeten ze misschien wel miljoenen paren controleren. Als de fabriek vol zit met parallelle activiteit, wordt hun notitieboekje zo groot dat de berekening eeuwig duurt.

De Nieuwe Manier: Het "Concurrent Paths" (CP) Algoritme

Dit artikel introduceert een nieuwe, slimmere detectivemethode genaamd het Concurrent Paths (CP) algoritme. Het is specifief ontworpen voor fabrieken die een aantal specifieke regels volgen ("sound free-choice workflow nets").

Zo werkt de nieuwe methode, met behulp van eenvoudige analogieën:

1. De "Geen-Pad"-regel (Voor eenvoudige fabrieken)
Eerst keken de auteurs naar fabrieken die geen lussen hebben (geen lopende banden die weer terug naar het begin cirkelen). Ze realiseerden zich een simpele waarheid: Als Machine A en Machine B tegelijkertijd kunnen werken, is er geen directe weg die hen verbindt. Als er een weg van A naar B is, moet A eerst klaar zijn voordat B kan beginnen, dus kunnen ze niet gelijktijdig zijn.

De nieuwe methove gebruikt deze regel. In plaats van elk paar machines één voor één te controleren, brengt het algoritme alle wegen (paden) in de fabriek in kaart.

De Analogie: Stel je voor dat je een kaart van de fabriek hebt. In plaats van voor elk paar te vragen: "Kunnen A en B samenwerken?", kijk je gewoon op de kaart. Als je een weg van A naar B ziet, weet je direct dat ze niet gelijktijdig kunnen zijn. Als er geen weg is, en ze bevinden zich in het juiste deel van de fabriek, dan kunnen ze dat wel.
Het Resultaat: Dit verandert een trage, zware berekening in een veel snellere eenheid. Voor eenvoudige, niet-lusvormige fabrieken is de nieuwe methode kwadratisch (het schaalt veel beter). Als de grootte van de fabriek verdubbelt, explodeert de tijd niet; het groeit slechts gestaag.

2. De "Loop"-truc (Voor fabrieken met cirkels)
Veel echte fabrieken hebben lussen (machines die een proces herhalen). De oude methode gaat goed om met lussen, maar de nieuwe "Geen-Pad"-regel wordt daar lastig.

Om dit op te lossen, gebruikt het CP-algoritme een techniek genaamd Loop Decomposition.

De Analogie: Stel je een fabriek voor met een enorme cirkelvormige baan. De nieuwe methode pakt een schaar en knipt de cirkel door, waardoor het even een rechte lijn wordt. Het analyseert de rechte lijn (wat makkelijk en snel is) en "plakt" de cirkel vervolgens in gedachten weer aan elkaar.
Het Resultaat: Hoewel dit "knippen en plakken" wat extra tijd kost, stelt het het algoritme in staat om de snelle "Geen-Pad"-regel toe te passen op de losse stukken.

De Grote Test: Werkt het echt?

De auteurs hebben hun nieuwe algoritme getest tegenover de "Oude Detectives" met behulp van een echte dataset van 6ak 644 fabriekmodellen (van IBM).

De Winnaar: Het nieuwe CP-algoritme was ongeveer 50 keer sneller in totaal.
Het Optimale Punt: De nieuwe methode blinkt uit wanneer de fabriek erg druk is met veel zaken die tegelijkertijd gebeuren. In één specifieke testcasus met 42.000 paren concurrente machines, deed de oude methode er meer dan 10 seconden over, terwijl de nieuwe methode minder dan een halve seconde nodig had.
De Kanttekening: Als de fabriek heel eenvoudig is en er heel weinig dingen tegelijkertijd gebeuren, is de nieuwe methode iets langzamer omdat hij eerst wat tijd besteedt aan het tekenen van de kaart. Maar voor complexe, drukke systemen is het een enorme verbetering.

Samenvatting

Beschouw de oude methode als iemand die door een doolhof loopt en elke muur controleert om te zien of het een doodlopende weg is. De nieuwe methode is als iemand met een drone die over het doolhof vliegt, de hele kaart in één oogopslag ziet en direct weet welke paden open zijn.

Dit artikel beweert dat voor een specifiek type systeem (sound free-choice workflow nets), deze nieuwe "drone"-aanpak (het CP-algoritme) een veel efficiëntere manier is om te vinden wat er parallel kan gebeuren, vooral wanneer het systeem groot en complex is. Het claimt niet elk type systeem op te lossen, maar voor de systemen die het target, verlegt het de grenzen van snelheid aanzienlijk.

Technische Samenvatting: De grenzen verleggen: Concurrency detectie in acyclische sound free-choice workflow nets in O(P² + T²)

Probleemstelling
Concurrency detectie in Petri-netten is een fundamentele voorwaarde voor het analyseren van complexe systeemgedragingen, met name in business process management. Het identificeren van welke plaatsen (places) en transities parallel kunnen worden uitgevoerd, maakt de afleiding van andere gedragsrelaties mogelijk (bijv. causaliteit, exclusiviteit) en vergemakkelijkt dimensionaliteitsmetingen. Bestaande algoritmen, specifiek die van Kovalyov en Esparza (KovEs), bieden oplossingen voor live en bounded free-choice nets, maar hun computationele complexiteit kan prohibitief worden voor grote netwerken met een hoge graad van concurrency. Het KovEs-algoritme werkt met een tijdscomplexiteit van $O((P + T)TP^2)$ voor algemene live en bounded nets en $O(P(P + T)^2)$ voor live en bounded free-choice nets. In de praktijk, wanneer netwerken veel concurrente node-paren bevatten, lijden deze algoritmen onder aanzienlijke rekentijden. Bovendien falen bestaande decompositie-benaderingen (bijv. SESE-fragmenten) vaak wanneer netwerken ongestructureerde fragmenten (rigids) bevatten, wat het gebruik van algemene, hogere-complexiteit technieken noodzakelijk maakt.

Methodologie
Het artikel introduceert het Concurrent Paths (CP) algoritme, ontworpen specifiek voor sound free-choice workflow nets (FW-nets). De methodologie steunt op twee primaire theoretische pijlers:

Path-to-End Theorem: In sound FW-nets bevat geen bereikbare markering meer dan één token op enig acyclisch pad naar de sink. Dit impliceert dat als twee nodes concurrent zijn, er geen pad tussen hen kan bestaan.
Revised Concurrency Logic: De auteurs herzien de observaties die worden gebruikt in het KovEs-algoritme. Zij stellen vast dat voor sound acyclische free-choice workflow nets (AFW-nets), twee nodes $x$ en $s$ concurrent zijn dan en slechts dan als er geen pad van $x$ naar $s$ is (en vice versa), mits ze al verbonden zijn via een bekende concurrente pair.

Het CP-algoritme verloopt in twee fasen:

Voor Acyclische Netwerken (AFW-nets): Het algoritme berekent een HasPath relatie (het bepalen van bereikbaarheid) voor alle nodes. Vervolgens iterereert het door initiële concurrente paren (afgeleid van transities met meerdere output places of initiële tokens). Voor elk paar $(x, y)$ berekent het de verzameling nodes die bereikbaar zijn vanuit $x$ maar niet vanuit $y$ ( $\bar{R}^y_x$ ), en de verzameling nodes die bereikbaar zijn vanuit $y$ maar niet vanuit $x$ . Op basis van de herziene logica voegt het direct concurrency-relaties toe tussen deze disjuncte verzamelingen, waardoor de iteratieve pair-by-pair expansie die in KovEs wordt gebruikt, wordt vermeden.
Voor Cyclische Netwerken: Het algoritme maakt gebruik van loop decomposition. Het identificeert loops (strongly connected components) en vervangt deze door een enkele "loop place", waardoor het cyclische net effectief wordt gedecomponeerd in een reeks acyclische nets. Het CP-algoritme wordt vervolgens toegepast op elk van de resulterende acyclische nets. Ten slotte worden de concurrency-relaties gecombineerd door de concurrency van de virtuele loop places terug te mappen naar de werkelijke nodes binnen de oorspronkelijke loops.

Belangrijkste Bijdragen

Nieuw Algoritme (CP): Een nieuw algoritme voor concurrency detectie in sound free-choice workflow nets dat gebruikmaakt van pad-analyse in plaats van iteratieve state exploratie.
Verbeterde Complexiteit voor Acyclische Nets: Het CP-algoritme bereikt een worst-case tijdcomplexiteit van $O(P^2 + T^2)$ voor acyclische nets. Dit vertegenwoordigt een significante verbetering ten opzichte van de $O(P(P + T)^2)$ complexiteit van het KovEs-algoritme voor deze specifieke klasse van netwerken.
Afhandeling van Cyclische Nets: Het artikel breidt de benadering uit naar cyclische nets via loop decomposition. Hoewel de worst-case complexiteit voor cyclische nets cubic blijft op $O(P^3 + PT^2)$ (overeenkomend met KovEs), stellen de auteurs dat het worst-case scenario (veel geneste loops) zeldzaam is.
Paralleliseerbaarheid: Het CP-algoritme is inherent goed geschikt voor parallelisatie. De decompositie in acyclische nets maakt parallelle verwerking van sub-nets mogelijk, en de berekening van HasPath en de daaropvolgende relatie-updates kunnen geparalleliseerd worden.

Resultaten en Evaluatie
De auteurs hebben het CP-algoritme geëvalueerd tegen het KovEs-algoritme met behulp van de IBM Websphere Business Modeler dataset (644 sound FW-nets).

Prestaties bij Hoge Concurrency: Het CP-algoritme vertoonde substantiële versnellingen op nets met een hoge graad van concurrency. In één specifiek geval met ongeveer 42.000 concurrente paren, had CP 45 ms nodig vergeleken met 10.500 ms voor KovEs. Over 87 nets met hoge concurrency was CP ongeveer 82 keer sneller.
Prestaties bij Lage Concurrency: Voor nets met lage concurrency (de meerderheid van de dataset) presteerde het KovEs-algoritme iets beter vanwege de "startup cost" van het CP-algoritme (het berekenen van paden en het decomponeren van loops). Echter, de overhead was minimaal.
Schaalbaarheid: De evaluatie gaf aan dat de computationele last van KovEs kwadratisch toeneemt met het aantal concurrente paren, terwijl de last voor CP lineair toeneemt.
Cyclische Nets: Op de 40 cyclische nets was KovEs sneller (16 ms vs. 43 ms), wat wordt toegeschreven aan de overhead van loop decomposition en de lage ratio van concurrente nodes in die specifieke nets. De auteurs merken echter op dat wanneer een cyclisch net met hoge concurrency werd getest, CP competitief bleef.

Betekenis en Claims
Het artikel claimt dat het CP-algoritme het bestaande palet van concurrency detectie-instrumenten aanvult, specifiek door de prestaties te optimaliseren voor sound free-choice workflow nets.

Efficiëntie: De primaire betekenis ligt in het vermogen om netwerken met veel concurrente nodes efficiënt te verwerken, waardoor de rekentijd wordt teruggebracht van een kwadratische/cubische afhankelijkheid van het aantal nodes naar een meer beheersbare kwadratische afhankelijkheid van het aantal nodes voor acyclische gevallen.
Praktische Bruikbaarheid: De auteurs benadrukken dat hoewel de worst-case complexiteit voor cyclische nets niet is verbeterd, het worst-case scenario (hoogst geneste loops) in de praktijk zeldzaam is. Daarom wordt verwacht dat de average-case prestaties superieur zullen zijn, met name voor grootschalige process mining of indexing taken waarbij nets in bulk worden geanalyseerd.
Toekomstig Nut: De auteurs suggereren dat deze efficiëntie een effectievere indexing van nets in query-talen mogelijk maakt en de afleiding van andere gedragsrelaties (causaliteit, exclusiviteit) in business process management en informatie-systemen onderzoek vergemakkelijkt.

Het artikel hanteert een bescheiden houding door te erkennen dat voor nets met lage concurrency of specifieke cyclische structuren, het traditionele KovEs-algoritme nog steeds de voorkeur kan genieten, maar stelt dat CP een robuust alternatief biedt voor de groeiende klasse van complexe, hoog-concurrente workflow modellen.

De Oude Manier: De Langzame Detective

De Nieuwe Manier: Het "Concurrent Paths" (CP) Algoritme

De Grote Test: Werkt het echt?

Samenvatting

Meer zoals dit