💻 computer science

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

Dieses Paper führt den Concurrent Paths (CP) Algorithmus ein, der die Konkurenzerkennung in azyklischen, sounden Free-Choice Workflow Nets auf eine Worst-Case-Komplexität von $O(P^2 + T^2)$ verbessert und damit signifikante Leistungsvorteile gegenüber bestehenden Methoden bietet, wenn die Netze viele konkurrente Knoten enthalten.

Ursprüngliche Autoren: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Veröffentlicht 2026-02-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie leiten eine riesige, komplexe Fabrik. In dieser Fabrik gibt es viele verschiedene Stationen (genannt Orte) und Maschinen (genannt Transitionen), die Produkte entlang eines Förderbandsystems bewegen. Manchmal ist die Fabrik so konzipiert, dass zwei verschiedene Maschinen zur gleichen Zeit arbeiten können, ohne sich gegenseitig im Weg zu stehen. Dies wird als Nebenläufigkeit (Concurrency) bezeichnet.

Zu wissen, welche Maschinen parallel laufen können, ist entscheidend. Es hilft Ihnen zu verstehen, wie die Fabrik funktioniert, Engpässe zu finden und sicherzustellen, dass das System nicht abstürzt. Allerdings ist es ein massives mathematisches Problem, genau zu bestimmen, welche Paare von Maschinen in einer riesigen, verworrenen Fabrik zusammenarbeiten können.

Die alte Methode: Der langsame Detektiv

Lange Zeit war die beste Methode zur Lösung dieses Problems ein Verfahren, das von Kovalyov und Esparza entwickelt wurde (nennen wir sie die „alten Detektive“). Ihre Methode funktioniert gut, hat aber einen Makel: Wenn eine Fabrik viele Maschinen hat, die parallel laufen, explodiert die Zeit, die benötigt wird, um alles herauszufinden.

Stellen Sie sich vor, die alten Detektive versuchen, jedes einzelne Paar von Maschinen zu prüfen, um zu sehen, ob sie zusammenarbeiten können. Wenn Sie 1.000 Maschinen haben, müssen sie vielleicht Millionen von Paaren prüfen. Wenn die Fabrik voll mit paralleler Aktivität ist, wird ihr Notizbuch so groß, dass die Berechnung ewig dauert.

Die neue Methode: Der „Concurrent Paths“ (CP) Algorithmus

Dieses Paper stellt eine neue, intelligentere Detektivmethode namens Concurrent Paths (CP) Algorithmus vor. Er ist speziell für Fabriken entwickelt, die ein paar spezifische Regeln befolgen (sogenannte „sound free-choice workflow nets“).

So funktioniert die neue Methode unter Verwendung einfacher Analogien:

1. Die „Kein-Pfad“-Regel (Für einfache Fabriken)
Zuerst untersuchten die Autoren Fabriken, die keine Schleifen besitzen (keine Förderbänder, die sich im Kreis drehen). Sie erkannten eine einfache Wahrheit: Wenn Maschine A und Maschine B gleichzeitig arbeiten können, gibt es keine direkte Straße, die sie verbindet. Wenn eine Straße von A nach B führt, muss A fertig sein, bevor B beginnt, also können sie nicht nebenläufig sein.

Die neue Methode nutzt diese Regel. Anstatt jedes Paar von Maschinen einzeln zu prüfen, bildet sie alle Straßen (Pfade) in der Fabrik ab.

Die Analogie: Stellen Sie sich vor, Sie haben eine Karte der Fabrik. Anstatt für jedes Paar zu fragen: „Können A und B zusammenarbeiten?“, schauen Sie einfach auf die Karte. Wenn Sie eine Straße von A nach B sehen, wissen Sie sofort, dass sie nicht nebenläufig sein können. Wenn es keine Straße gibt und sie sich im richtigen Teil der Fabrik befinden, können sie das.
Das Ergebnis: Dies verwandelt eine langsame, schwere Berechnung in eine viel schnellere. Für einfache, nicht-schleifende Fabriken ist die neue Methode quadratisch (sie skaliert viel besser). Wenn sich die Größe der Fabrik verdoppelt, explodiert die Zeit nicht; sie wächst lediglich stetig an.

2. Der „Schleifen“-Trick (Für Fabriken mit Kreisläufen)
Viele echte Fabriken haben Schleifen (Maschinen, die einen Prozess wiederholen). Die alte Methode bewältigt Schleifen, aber die neue „Kein-Pfad“-Regel wird dort schwierig.

Um dies zu lösen, nutzt der CP-Algorithmus eine Technik namens Schleifen-Dekomposition (Loop Decomposition).

Die Analogie: Stellen Sie sich eine Fabrik mit einer riesigen Kreisbahn vor. Die neue Methode nimmt eine Schere und schneidet den Kreis auf, wodurch er für einen Moment in eine gerade Linie verwandelt wird. Sie analysiert die gerade Linie (die einfach und schnell ist) und „klebt“ den Kreis dann in ihrem Geist wieder zusammen.
Das Ergebnis: Auch wenn dieses „Schneiden und Kleben“ etwas zusätzliche Zeit kostet, ermöglicht es der Methode, die schnelle „Kein-Pfad“-Regel auf die einzelnen Stücke anzuwenden.

Der große Test: Funktioniert es wirklich?

Die Autoren haben ihren neuen Algorithmus gegen die „alten Detektive“ mit einem realen Datensatz von 644 Fabrikmodellen (von IBM) getestet.

Der Gewinner: Der neue CP-Algorithmus war insgesamt etwa 50 Mal schneller.
Der „Sweet Spot“: Die neue Methode glänzt, wenn die Fabrik sehr geschäftig ist und viele Dinge gleichzeitig passieren. In einem speziellen Testfall mit 42.000 Paaren von nebenläufigen Maschinen dauerte die alte Methode über 10 Sekunden, während die neue Methode weniger als eine halbe Sekunde benötigte.
Die Einschränkung: Wenn die Fabrik sehr einfach ist und nur sehr wenige Dinge gleichzeitig passieren, ist die neue Methode etwas langsamer, weil sie erst ein wenig Zeit damit verbringt, die Karte zu zeichnen. Aber für komplexe, geschäftige Systeme ist sie eine massive Verbesserung.

Zusammenfassung

Betrachten Sie die alte Methode als eine Person, die durch ein Labyrinth läuft und jede Wand abtastet, um zu sehen, ob es eine Sackgasse ist. Die neue Methode ist wie eine Person mit einer Drohne, die über das Labyrinth fliegt, die gesamte Karte auf einmal sieht und sofort weiß, welche Pfade offen sind.

Dieses Paper behauptet, dass für einen bestimmten Typ von Systemen (sound free-choice workflow nets) dieser neue „Drohnen“-Ansatz (der CP-Algorithmus) ein wesentlich effizienterer Weg ist, um herauszufinden, was parallel ablaufen kann – insbesondere, wenn das System groß und komplex ist. Es wird nicht behauptet, dass es jedes System behebt, aber für die Zielsysteme treibt es die Geschwindigkeit signifikant voran.

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

Problemstellung
Die Erkennung von Nebenläufigkeit (Concurrency Detection) in Petri-Netzen ist eine grundlegende Voraussetzung für die Analyse komplexer Systemverhalten, insbesondere im Bereich des Business Process Management. Die Identifizierung der Knoten (Places) und Transitionen, die parallel ausgeführt werden können, ermöglicht die Ableitung anderer Verhaltensrelationen (z. B. Kausalität, Exklusivität) und erleichtert Ähnlichkeitsmessungen. Bestehende Algorithmen, speziell jene von Kovalyov und Esparza (KovEs), bieten Lösungen für lebende (live) und beschränkte (bounded) Free-Choice-Netze, doch ihre Rechenkomplexität kann bei großen Netzen mit hohem Grad an Nebenläufigkeit prohibitiv hoch werden. Der KovEs-Algorithmus operiert mit einer Zeitkomplexität von $O((P + T)TP^2)$ für allgemeine lebende und beschränkte Netze und $O(P(P + T)^2)$ für lebende und beschränkte Free-Choice-Netze. In der Praxis führen Netze, die zahlreiche nebenläufige Knotenpaare enthalten, zu erheblichen Rechenzeiten. Darüber hinaus scheitern bestehende Dekompositionsansätze (z. B. SESE-Fragmente) oft, wenn Netze unstrukturierte Fragmente (Rigidities) enthalten, was den Einsatz allgemeinerer, komplexerer Techniken erforderlich macht.

Methodik
Das Paper führt den Concurrent Paths (CP) Algorithmus ein, der speziell für sound free-choice Workflow-Netze (FW-Netze) entwickelt wurde. Die Methodik stützt sich auf zwei primäre theoretische Säulen:

Path-to-End Theorem: In sound FW-Netzen enthält keine erreichbare Markierung mehr als einen Token auf einem azyklischen Pfad zum Sink-Knoten. Dies impliziert, dass, wenn zwei Knoten nebenläufig sind, kein Pfad zwischen ihnen existieren kann.
Revidierte Nebenläufigkeitslogik: Die Autoren revidieren die Beobachtungen, die im KovEs-Algorithmus verwendet werden. Sie stellen fest, dass für sound azyklische Free-Choice-Workflow-Netze (AFW-Netze) zwei Knoten $x$ und $s$ genau dann nebenläufig sind, wenn kein Pfad von $x$ nach $s$ existiert (und umgekehrt), vorausgesetzt, sie sind bereits über ein bekanntes nebenläufiges Paar verknüpft.

Der CP-Algorithmus erfolgt in zwei Stufen:

Für azyklische Netze (AFW-Netze): Der Algorithmus berechnet eine HasPath-Relation (Bestimmung der Erreichbarkeit) für alle Knoten. Anschließend iteriert er durch initiale nebenläufige Paare (abgeleitet von Transitionen mit mehreren Ausgangsplätzen oder initialen Tokens). Für jedes Paar $(x, y)$ berechnet er die Menge der Knoten, die von $x$ aus erreichbar sind, aber nicht von $y$ ( $\bar{R}^y_x$ ), sowie die Menge der Knoten, die von $y$ aus erreichbar sind, aber nicht von $x$ . Basierend auf der revidierten Logik fügt der Algorithmus direkt Nebenläufigkeitsrelationen zwischen diesen disjunkten Mengen hinzu, wodurch die iterative Paar-für-Paar-Expansion verwendet wird, die in KovEs zum Einsatz kommt.
Für zyklische Netze: Der Algorithmus nutzt die Schleifendekomposition (Loop Decomposition). Er identifiziert Schleifen (Strongly Connected Components) und ersetzt diese durch einzelne „Loop-Places“, wodurch das zyklische Netz effektiv in eine Menge azyklischer Netze zerlegt wird. Der CP-Algorithmus wird dann auf jedes dieser resultierenden azyklischen Netze angewendet. Schließlich werden die Nebenläufigkeitsrelationen rekombiniert, indem die Nebenläufigkeit der virtuellen Loop-Places auf die tatsächlichen Knoten innerhalb der ursprünglichen Schleifen zurückgemappt wird.

Wesentliche Beiträge

Neuer Algorithmus (CP): Ein neuartiger Algorithmus zur Erkennung von Nebenläufigkeit in sound free-choice Workflow-Netzen, der Pfadanalyse anstelle von iterativer Zustandsexploration nutzt.
Verbesserte Komplexität für azyklische Netze: Der CP-Algorithmus erreicht eine Worst-Case-Zeitkomplexität von $O(P^2 + T^2)$ für azyklische Netze. Dies stellt eine signifikante Verbesserung gegenüber der $O(P(P + T)^2)$ Komplexität des KovEs-Algorithmus für diese spezifische Klasse von Netzen dar.
Umgang mit zyklischen Netzen: Das Paper erweitert den Ansatz auf zyklische Netze mittels Schleifendekomposition. Während die Worst-Case-Komplexität für zyklische Netze mit $O(P^3 + PT^2)$ kubisch bleibt (was mit KovEs übereinstimmt), argumentieren die Autoren, dass das Worst-Case-Szenario (viele verschachtelte Schleifen) selten ist.
Parallelisierbarkeit: Der CP-Algorithmus ist von Natur aus gut für die Parallelisierung geeignet. Die Dekomposition in azyklische Netze ermöglicht die parallele Verarbeitung von Teilnetzen, und auch die Berechnung von HasPath sowie die anschließenden Relations-Updates können parallelisiert werden.

Ergebnisse und Evaluierung
Die Autoren evaluierten den CP-Algorithmus im Vergleich zum KovEs-Algorithmus unter Verwendung des IBM Websphere Business Modeler Datensatzes (644 sound FW-Netze).

Performance bei hoher Nebenläufigkeit: Der CP-Algorithmus zeigte erhebliche Beschleunigungen bei Netzen mit einem hohen Grad an Nebenläufigkeit. In einem spezifischen Fall mit etwa 42.000 nebenläufigen Paaren benötigte CP 45 ms, während KovEs 10.500 ms benötigte. Über 87 Netze mit hoher Nebenläufigkeit hinweg war CP etwa 82 Mal schneller.
Performance bei geringer Nebenläufigkeit: Für Netze mit geringer Nebenläufigkeit (der Großteil des Datensatzes) schnitt der KovEs-Algorithmus etwas besser ab, was auf die „Startup-Kosten“ des CP-Algorithmus (Berechnung von Pfaden und Dekomposition von Schleifen) zurückzuführen ist. Der Overhead war jedoch minimal.
Skalierbarkeit: Die Evaluierung ergab, dass die Rechenlast von KovEs quadratisch mit der Anzahl der nebenläufigen Paare steigt, während die Last für CP linear mit der Anzahl der Knoten steigt.
Zyklische Netze: Bei den 40 zyklischen Netzen war KovEs schneller (16 ms vs. 43 ms), was auf den Overhead der Schleifendekomposition und das geringe Verhältnis von nebenläufigen Knoten in diesen spezifischen Netzen zurückzuführen ist. Die Autoren merken jedoch an, dass CP bei Tests mit einem zyklischen Netz mit hoher Nebenläufigkeit wettbewerbsfähig blieb.

Bedeutung und Ansprüche
Das Paper behauptet, dass der CP-Algorithmus das bestehende Spektrum an Werkzeugen zur Erkennung von Nebenläufigkeit ergänzt, indem er die Performance speziell für sound free-choice Workflow-Netze optimiert.

Effizienz: Die primäre Bedeutung liegt in der Fähigkeit, Netze mit vielen nebenläufigen Knoten effizient zu handhaben, wodurch die Rechenzeit von einer quadratischen/kubischen Abhängigkeit von der Knotenanzahl auf eine handhabbarere quadratische Abhängigkeit der Knotenanzahl für azyklische Fälle reduziert wird.
Praktikabilität: Die Autoren betonen, dass obwohl die Worst-Case-Komplexität für zyklische Netze nicht verbessert wurde, das Worst-Case-Szenario (hochgradig verschachtelte Schleifen) in der Praxis selten vorkommt. Daher wird erwartet, dass die Average-Case-Performance besonders bei der Analyse großer Netze im Rahmen von Process Mining oder Indexing-Aufgaben überlegen ist.
Zukünftiger Nutzen: Die Autoren legen nahe, dass diese Effizienz eine effektivere Indizierung von Netzen in Abfragesprachen ermöglicht und die Ableitung anderer Verhaltensrelationen (Kausalität, Exklusivität) in der Business Process Management und Information Systems Forschung erleichtert.

Das Paper wahrt eine moderate Haltung und räumt ein, dass für Netze mit geringer Nebenläufigkeit oder spezifischen zyklischen Strukturen der traditionelle KovEs-Algorithmus weiterhin bevorzugt werden kann, behauptet jedoch, dass CP eine robuste Alternative für die wachsende Klasse komplexer, hochgradig nebenläufiger Workflow-Modelle bietet.

Die alte Methode: Der langsame Detektiv

Die neue Methode: Der „Concurrent Paths“ (CP) Algorithmus

Der große Test: Funktioniert es wirklich?

Zusammenfassung

Mehr davon