💻 computer science

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

本文介绍了并发路径（Concurrent Paths, CP）算法，该算法将无环健全自由选择工作流网中的并发检测最坏情况复杂度提升至 $O(P^2 + T^2)$ ，在网络包含大量并发节点时，与现有方法相比具有显著的性能优势。

原作者： Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

发布于 2026-02-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在管理一个庞大且复杂的工厂。在这个工厂里，有许多不同的工作站（称为场所）和机器（称为变迁），它们沿着传送带系统移动产品。有时，工厂的设计使得两台不同的机器可以同时工作而互不干扰。这被称为并发性（concurrency）。

了解哪些机器可以并行运行至关重要。这有助于你了解工厂的运作方式、寻找瓶颈，并确保系统不会崩溃。然而，在一个庞大且错综复杂的工厂中，准确找出究竟哪些机器对可以同时运行，是一个巨大的数学难题。

旧方法：缓慢的侦探

长期以来，解决这一问题的最佳方法是由 Kovalyov 和 Esparza 开发的一种方法（我们称之为“旧侦探”）。这种方法效果不错，但它有一个缺陷：如果工厂中有大量机器在并行运行，计算所需的时间就会爆炸式增长。

想象一下，旧侦探们试图检查每一对机器是否可以协同工作。如果你有 1,000 台机器，他们可能需要检查数百万个组合。如果工厂充满了并行活动，他们的笔记本会变得非常厚重，导致计算耗时极长。

新方法：“并发路径”（CP）算法

这篇论文介绍了一种更聪明的新型侦探方法，称为并发路径（CP）算法。它是专门为遵循特定规则（即“健全自由选择工作流网”）的工厂设计的。

以下是新方法的工作原理，使用简单的类比来解释：

1. “无路径”规则（针对简单工厂）
首先，作者研究了没有任何循环（没有循环往复的传送带）的工厂。他们发现了一个简单的真理：如果机器 A 和机器 B 可以同时工作，那么它们之间不存在直接的道路连接。 如果存在从 A 到 B 的道路，则 A 必须在 B 开始之前完成，因此它们不能是并发的。

新算法利用了这一规则。它不再逐一检查每一对机器，而是绘制出工厂中所有的道路（路径）。

类比： 想象你有一张工厂地图。与其询问“A 和 B 能一起工作吗？”针对每一对组合进行询问，你只需要看地图即可。如果你看到一条从 A 到 B 的路，你立刻就知道它们不能并发。如果没有路，并且它们处于工厂的正确部分，那么它们可以并发。
结果： 这将一个缓慢、沉重的计算过程变成了一个快得多的过程。对于简单的、非循环的工厂，新方法是二次方级的（它的扩展性更好）。如果工厂规模翻倍，时间不会爆炸式增长，而只是稳步增长。

2. “循环”技巧（针对带有圆圈的工厂）
许多真实的工厂都有循环（机器重复某个过程）。旧方法可以处理循环，但新的“无路径”规则在处理循环时会变得棘手。

为了解决这个问题，CP 算法使用了循环分解技术。

类比： 想象一个带有巨大环形轨道的工厂。新方法拿起一把剪刀，把圆圈剪开，让它在瞬间变成一条直线。它先分析这条直线（这很容易且快速），然后在脑海中将圆圈“粘合”回去。
结果： 尽管这种“剪切与粘合”会额外消耗一些时间，但它允许算法在这些碎片上使用快速的“无路径”规则。

大考：它真的有效吗？

作者使用来自 IBM 的 644 个工厂模型的真实数据集，将他们的新算法与“旧侦探”进行了对比测试。

胜出者： 新的 CP 算法整体速度快了大约 50 倍。
甜点区（优势区间）： 当工厂非常繁忙、有很多事情同时发生时，新方法表现尤为出色。在一个包含 42,000 对并发机器的特定测试案例中，旧方法耗时超过 10 秒，而新方法耗时不到半秒。
局限性： 如果工厂非常简单且几乎没有并发活动，新方法会稍慢一些，因为它需要先花费时间绘制地图。但对于复杂、繁忙的系统，这是一个巨大的进步。

总结

把旧方法想象成一个人在迷宫中穿行，通过检查每一面墙来判断是否是死胡同。而新方法则像是一个带着无人机的人，从高空俯瞰整个迷宫，一眼就能看出整张地图，并瞬间知道哪些路径是通畅的。

这篇论文声称，对于特定类型的系统（健全自由选择工作流网），这种“无人机”式的方法（CP 算法）是一种更高效的寻找并行发生情况的方法，尤其是在系统规模庞大且复杂时。它并不声称能解决所有类型的系统，但对于它所针对的那些系统，它显著提升了速度的极限。

技术摘要：突破极限：无环健全自由选择工作流网中 $O(P^2 + T^2)$ 复杂度的并发检测

问题陈述
并发检测是 Petri 网中一个基础性的前提条件，对于分析复杂系统行为（尤其是在业务流程管理领域）至关重要。识别哪些位置（places）和变迁（transitions）可以并行执行，能够为推导其他行为关系（如因果关系、排他关系）提供支持，并促进相似性度量。现有的算法，特别是 Kovalyov 和 Esparza 的算法（KovEs），虽然为活且有界的自由选择网提供了解决方案，但其计算复杂度在处理具有高度并发性的庞大网络时可能会变得难以承受。KovEs 算法对于一般的活且有界网的运行时间复杂度为 $O((P + T)TP^2)$ ，对于活且有界的自由选择网为 $O(P(P + T)^2)$ 。在实践中，当网络包含大量并发节点对时，这些算法会导致显著的计算耗时。此外，现有的分解方法（例如 SESE 片段）在遇到包含非结构化片段（刚性结构/rigids）的网络时往往会失效，因此必须使用更通用的、复杂度更高的技术。

方法论
本文引入了 并发路径（Concurrent Paths, CP）算法，该算法专门针对 健全自由选择工作流网（FW-nets） 设计。其方法论依赖于两个主要的理论支柱：

路径终点定理（Path-to-End Theorem）： 在健全的 FW-nets 中，任何可达标记在任何通往汇点（sink）的无环路径上都不包含超过一个标记。这意味着，如果两个节点是并发的，则它们之间不存在路径。
修正后的并发逻辑： 作者修正了 KovEs 算法中所使用的观察结果。他们确立了对于健全的无环自由选择工作流网（AFW-nets），两个节点 $x$ 和 $s$ 是并发的，当且仅当 $x$ 到 $s$ 之间不存在路径（反之亦然），前提是它们已经通过一个已知的并发对相关联。

CP 算法分为两个阶段进行：

针对无环网络（AFW-nets）： 算法计算所有节点的 HasPath 关系（确定可达性）。然后，它遍历初始并发对（由具有多个输出位置的变迁或初始标记推导而来）。对于每一对 $(x, y)$ ，它计算从 $x$ 可达但从 $y$ 不可达的节点集 ( $\bar{R}^y_x$ )，以及从 $y$ 可达但从 $x$ 不可达的节点集。基于修正后的逻辑，它直接在这些不相交的集合之间添加并发关系，从而避免了 KovEs 中使用的迭代式对对扩展。
针对有环网络： 算法采用 循环分解（loop decomposition） 技术。它识别循环（强连通分量），并将它们替换为单个“循环位置”，从而有效地将有环网络分解为一组无环网络。随后，在每个生成的无环网络上应用 CP 算法。最后，通过将虚拟循环位置的并发关系映射回原始循环中的实际节点，来重新组合并发关系。

主要贡献

新算法 (CP)： 一种用于健全自由选择工作流网的并发检测新算法，它利用路径分析而非迭代状态探索。
改进了无环网络的复杂度： CP 算法在无环网络下的最坏情况时间复杂度为 $O(P^2 + T^2)$ 。这对于此类特定类型的网络而言，相比 KovEs 算法的 $O(P(P + T)^2)$ 复杂度有了显著提升。
处理有环网络： 本文通过循环分解扩展了该方法。虽然有环网络的最坏情况复杂度仍为三次方级 $O(P^3 + PT^2)$ （与 KovEs 持平），但作者认为，最坏情况（即存在大量嵌套循环）在实际中并不常见。
可并行性： CP 算法本质上非常适合并行化。将其分解为无环网络的方法允许对子网进行并行处理，且 HasPath 的计算及随后的关系更新也可以并行化。

结果与评估
作者使用 IBM WebSphere Business Modeler 数据集（包含 644 个健全 FW-nets）将 CP 算法与 KovEs 算法进行了对比评估。

高并发性能： 在具有高并发度的网络中，CP 算法表现出了显著的加速效果。在处理一个包含约 42,000 个并发对的具体案例时，CP 仅需 45 毫秒，而 KovEs 则需要 10,500 毫秒。在 87 个高并发网络的测试中，CP 的速度大约快了 82 倍。
低并发性能： 对于低并发网络（数据集中的大多数情况），由于 CP 算法存在“启动成本”（计算路径和分解循环），Koves 算法的表现略优。然而，这种开销非常小。
可扩展性： 评估表明，Koves 的计算负载随并发对的数量呈二次方增长，而 CP 的负载随之呈线性增长。
有环网络： 在 40 个有环网络上，Koves 速度更快（16 毫秒 vs 43 毫秒），这归因于循环分解的开销以及这些特定网络中并发节点比例较低。然而，作者指出，在测试具有高并发度的有环网络时，CP 依然保持了竞争力。

意义与主张
本文声称，CP 算法补充了现有的并发检测工具库，特别是在优化 健全自由选择工作流网 的性能方面。

效率： 其主要意义在于能够高效处理具有许多并发节点的网络，将计算时间从对节点数的二次方/三次方依赖降低到了对于无环情况更易处理的二次方依赖。
实用性： 作者强调，虽然对于有环网络的最坏情况复杂度并未改善，但最坏情况（高度嵌套的循环）在实践中很少见。因此，在平均情况下，其性能有望更优，特别是在需要大规模处理或索引网络任务的流程挖掘和信息系统研究中。
未来用途： 作者建议，这种效率使得在查询语言中对网络进行更有效的索引成为可能，并有助于在业务流程管理和信息系统研究中推导其他行为关系（如因果关系、排他关系）。

本文保持了审慎的态度，承认对于低并发或具有特定循环结构的网络，传统的 KovEs 算法可能仍然更具优势，但同时断言 CP 为日益复杂的、高并发的工作流模型提供了一个强有力的替代方案。

旧方法：缓慢的侦探

新方法：“并发路径”（CP）算法

大考：它真的有效吗？

总结

类似论文