可满足（≠，=）工作流的静态k弹性否决条件

摘要

静态k弹性反映安全工作流从资源失效异常中恢复运行的能力,但其验证须求解多达C(|U|,k)个工作流可满足决策问题(U为资源集),代价巨大。已有工作提出通过1次工作流可满足计数来量化其异常恢复能力,但该指标相当粗糙,仅能在可满足无解情形下给出精确的否定结论。对互斥和绑定约束下的工作流,建立了以k弹性可满足计数下界概念为核心的新颖模型,并首次证明了一个非平凡的下界,由此可将k弹性的否决条件从可满足无解推广到有解情形,具有理论上的代表性意义,也扩大了前述指标精确适用的范围。

关键词