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

テクニカル・サマリー：限界を押し広げる：非循環型サウンド・フリーチョイス・ワークフローネットにおける並行性検出における $O(P^2 + T^2)$

問題提起
ペトリネットにおける並行性検出は、複雑なシステムの振る舞いを分析する上で、特にビジネスプロセス管理において不可欠な前提条件である。どのプレースとトランジションが並列に実行可能であるかを特定することは、他の振る舞い関係（例：因果関係、排他関係）の導出を可能にし、類似性の測定を容易にする。既存のアルゴリズム、特に Kovalyov と Esparza によるもの（KovEs）は、ライブかつ有界なフリーチョイス・ネットに対して解を提供しているが、その計算量は、高い並行性を持つ大規模なネットに対しては非常に高価になる可能性がある。KovEs アルゴリズムは、一般的なライブかつ有界なネットに対して $O((P + T)TP^2)$、ライブかつ有界なフリーチョイス・ネットに対しては $O(P(P + T)^2)$ の時間計算量で動作する。実用上、ネットに多数の並行ノードのペアが含まれる場合、これらのアルゴリズムは大幅な計算時間の増大を招く。さらに、既存の分解手法（例：SESE フラグメント）は、非構造的なフラグメント（リジッド）を含むネットでは機能しないことが多く、より高次な計算量を持つ一般的な手法の使用を必要とする。

手法
本論文では、サウンド・フリーチョイス・ワークフローネット（FW-ネット）に特化して設計された並行パス（CP）アルゴリズムを導入する。この手法は、主に以下の2つの理論的柱に基づいている：

1. パス・トゥ・エンド（Path-to-End）定理： サウンドな FW-ネットにおいて、到達可能なマーキングがいかなる非循環的なシンクへのパスに対しても、2つ以上のトークンを含むことはない。これは、2つのノードが並行である場合、それらの間にパスが存在しないことを意味する。
2. 改訂された並行性ロジック： 著者らは KovEs アルゴリズムで使用されている観察事項を改訂した。彼らは、サウンドな非循環型フリーチョイス・ワークフローネット（AFW-ネット）において、2つのノード $x$ と $s$ が並行であるための必要十分条件は、既知の並行ペアを介して既にリンクされているという条件下で、$x$ から $s$ へのパス（およびその逆）が存在しないことであることを確立した。

CP アルゴリズムは2つのステージで進行する：

• 非循環型ネット（AFW-ネット）の場合： アルゴリズムは全ノードに対する HasPath 関係（到達可能性の判定）を計算する。次に、初期の並行ペア（複数の出力プレースを持つトランジションまたは初期トークンから派生したもの）を反復処理する。各ペア $(x, y)$ について、$x$ から到達可能だが $y$ からは到達できないノードの集合（$\bar{R}^y_x$）と、$y$ から到達可能だが $x$ からは到達できないノードの集合を計算する。改訂されたロジックに基づき、これらの方程式の不連続な集合の間に並行関係を直接追加することで、KovEs で用いられるような反復的なペアごとの拡張を回避する。
• 循環型ネットの場合： アルゴリズムはループ分解を採用する。ループ（強連結成分）を特定し、それらを単一の「ループ・プレース」に置き換えることで、循環型ネットを一連の非循環型ネットへと実質的に分解する。CP アルゴリズムを各結果として得られた非循環型ネットに適用する。最後に、仮想的なループ・プレースの並行性を、元のループ内の実際のノードへとマッピングすることで、並行関係を再結合する。

主な貢献

1. 新アルゴリズム（CP）： パス解析を利用して、パス探索ではなく経路分析を行う、サウンド・フリーチョイス・ワークフローネットのための新しい並行性検出アルゴリズム。
2. 非循環型ネットにおける計算量の改善： CP アルゴリズムは、非循環型ネットに対して $O(P^2 + T^2)$ の最悪時間計算量を達成する。これは、この特定のクラスのネットに対する KovEs アルゴリズムの $O(P(P + T)^2)$ という計算量と比較して、大幅な改善となる。
3. 循環型ネットの処理： 本論文は、ループ分解を通じて循環型ネットへとアプローチを拡張している。循環型ネットの最悪時間計算量は依然として $O(P^3 + PT^2)$ と立方オーダーであるが、著者らは、最悪のシナリオ（多くの入れ子になったループ）は稀であると主張している。
4. 並列化可能性： CP アルゴリズムは本質的に並列化に適している。非循環型ネットへの分解により、サブネットの並列処理が可能となり、HasPath の計算およびその後の関係更新も並列化できる。

結果と評価
著者らは、IBM WebSphere Business Modeler データセット（644 個のサウンド FW-ネット）を用いて、CP アルゴリズムを KovEs アルゴリズムと比較評価した。

• 高並行性におけるパフォーマンス： CP アルゴリズムは、並行性の度合いが高いネットにおいて大幅な高速化を示した。約 42,000 個の並行ペアを含む特定のケースでは、KovEs が 10,500 ms を要したのに対し、CP は 45 ms であった。高並行性を持つ 87 個のネット全体で、CP は約 82 倍高速であった。
• 低並行性におけるパフォーマンス： 低並行性（データセットの大部分）を持つネットについては、CP アルゴリズムの「スタートアップ・コスト」（パス計算およびループ分解）により、KovEs アルゴリズムの方がわずかに優れた性能を示した。しかし、そのオーバーヘッドは最小限であった。
• スケーラビリティ： 評価の結果、KovEs の計算負荷は並行ペアの数に対して二次関数的に増加するのに対し、CP の負荷は線形に増加することが示された。
• 循環型ネット： データセット内の 40 個の循環型ネットについては、ループ分解のオーバーヘッドと、それらのネットにおける並行ノードの比率が低かったことから、KovEs の方が高速であった（16 ms 対 43 ms）。しかし、著者らは、高並行性を持つ循環型ネットをテストした際、CP は競争力のある性能を維持したと述べている。

意義と主張
本論文は、CP アルゴリズムが既存の並行性検出ツールのパレットを補完し、特にサウンド・フリーチョイス・ワークフローネットのパフォーマンスを最適化することを主張している。

• 効率性： 主な意義は、多くの並行ノードを持つネットを効率的に処理できる能力にあり、非循環的なケースにおいて、ノード数に対する計算依存性を二次関数的な依存から、より扱いやすい二次的な依存へと減少させることにある。
• 実用性： 著者らは、循環型ネットの最悪時間計算量は改善されていないものの、最悪のシナリオ（高度に入れ子になったループ）は実務上稀であることを強調している。したがって、平均的なパフォーマンスは、特に大量のネットをバルクで分析するプロセス・マイニングやインデックス作成などのタスクにおいて、より優れたものになることが期待される。
• 将来的な有用性： 著者らは、この効率性が、クエリ言語におけるネットのより効果的なインデックス作成を可能にし、ビジネスプロセス管理および情報システム研究における他の振る舞い関係（因果関係、排他関係）の導出を促進すると示唆している。

本論文は、低並行性や特定の循環構造を持つネットにおいては、従来の KovEs アルゴリズムの方が好ましい場合があることを認めつつも、CP が複雑で高度に並行化したワークフローモデルが増加する中で、堅牢な代替案を提供することを主張し、控えめな立場を維持している。