• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Predicate control: synchronization in distributed computations with look-ahead
【24h】

Predicate control: synchronization in distributed computations with look-ahead

机译：谓词控制：分布式计算中的同步功能

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an off-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural. We define predicate control formally and show that, in its full generality, the problem is NP-complete. We find efficient solutions for some important classes of predicates including "disjunctive predicates", "mutual exclusion predicates", and "readers writers predicates". For each class of predicates, we determine the necessary and sufficient conditions for solving predicate control and describe an efficient algorithm for determining a synchronization strategy. In the case of "independent mutual exclusion predicates", we determine that predicate control is NP-complete and describe an efficient algorithm that finds a solution under certain constraints.
机译：谓词控制问题涉及同步分布式计算以维护给定的全局谓词。与诸如互斥，读者作家和用餐哲学家等许多流行的分布式同步问题相反，谓词控制假定先行，因此计算是离线输入而不是在线输入。谓词控制的目标是回滚恢复，调试和乐观计算之类的应用程序，在这些应用程序中，这种提前计算是很自然的。我们正式地定义了谓词控制，并证明，从总体上看，问题是NP完全的。我们为一些重要的谓词类型（包括“析取谓词”，“互斥谓词”和“读者作家谓词”）找到了有效的解决方案。对于每一类谓词，我们确定解决谓词控制的必要条件和充分条件，并描述一种用于确定同步策略的有效算法。在“独立互斥谓词”的情况下，我们确定谓词控制是NP完全的，并描述了一种有效算法，该算法可在某些约束条件下找到解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号