• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Decidability and Complexity for Quiescent Consistency
【24h】

Decidability and Complexity for Quiescent Consistency

机译：静态一致性的可判定性和复杂性

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Quiescent consistency is a notion of correctness for a concurrent object that gives meaning to the object's behaviours in quiescent states, i.e., states in which none of the object's operations are being executed. The condition enables greater flexibility in object design by allowing more behaviours to be admitted, which in turn allows the algorithms implementing quiescent consistent objects to be more efficient (when executed in a multithreaded environment).Quiescent consistency of an implementation object is defined in terms of a corresponding abstract specification. This gives rise to two important verification questions: membership (checking whether a behaviour of the implementation is allowed by the specification) and correctness (checking whether all behaviours of the implementation are allowed by the specification). In this paper, we consider the membership and correctness conditions for quiescent consistency, as well as a restricted form that assumes an upper limit on the number of events between two quiescent states. We show that the membership problem for unrestricted quiescent consistency is NP-complete and that the correctness problem is decidable, coNEXPTIME-hard, and in EXPSPACE. For the restricted form, we show that membership is in PTIME, while correctness is PSPACE-complete.
机译：静态一致性是针对并发对象的正确性的概念，该概念为处于静态状态（即，其中未执行任何对象操作的状态）的对象行为赋予了含义。该条件通过允许更多行为被接受而在对象设计中提供了更大的灵活性，这反过来又使实现静态一致对象的算法更加有效（在多线程环境中执行时）。相应的抽象规范。这就产生了两个重要的验证问题：成员资格（检查规范是否允许实现行为）和正确性（检查规范是否允许实现所有行为）。在本文中，我们考虑了静态一致性的隶属度和正确性条件，以及一种假定两个静态状态之间的事件数具有上限的受限形式。我们表明，无限制的静态一致性的隶属度问题是NP完全的，而正确性问题是可判定的，coNEXPTIME困难的，并且在EXPSPACE中。对于受限形式，我们显示成员资格以PTIME表示，而正确性为PSPACE完全。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号