计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (23): 35-39.DOI: 10.3778/j.issn.1002-8331.1808-0475

• 理论与研发 • 上一篇    下一篇

可满足(≠,=)工作流的静态k弹性否决条件

翟治年,王中鹏,叶绿,向坚,王富忠,庞海云   

  1. 1.浙江科技学院 信息与电子工程学院,杭州 310023
    2.浙江科技学院 经济与管理学院,杭州 310023
  • 出版日期:2019-12-01 发布日期:2019-12-11

Negative Condition of Static k Resiliency for Satisfiable(≠,=) Workflow

ZHAI Zhinian, WANG Zhongpeng, YE Lv, XIANG Jian, WANG Fuzhong, PANG Haiyun   

  1. 1.School of Information and Electronics Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China
    2.School of Economics and Management, Zhejiang University of Science and Technology, Hangzhou 310023, China
  • Online:2019-12-01 Published:2019-12-11

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

关键词: 工作流, 授权, 约束, 资源分配, 弹性, 可满足性

Abstract: Static [k] resiliency is concerned with the ability for workflows to recover executing from exceptions of resource unavailability. To verify it, up to [C(|U|,k)] Workflow Satisfiability(WS) decision problems should be solved(where [U] is the set of all resources) and the corresponding costs are huge. In existing work, one WS counting problem is solved to quantify the ability of a workflow to recover from exceptions. However, this indicator is somewhat rough, and only in the case of no satisfiability solution an accurate negative conclusion can be given. In this paper, for an exclusion and binding constrained workflow, a novel model which surrounds the concept of satisfiability counting lower bound of static [k] resiliency is established, and such a no-trivial lower bound is proved for the first time. Therefore, the negative condition of [k] resiliency is generalized, from unsatisfiable cases to satisfiable ones. This result has representative meanings in theory, by which the precisely applied range of the aforesaid indicator is also extended.

Key words: workflow, authorization, constraint, resource allocation, resiliency, satisfiability