论文标题
一致性算法的框架
A Framework for Consistency Algorithms
论文作者
论文摘要
我们提出了一个框架，为给定的内存模型提供确定性的一致性算法。这种算法检查在模型定义的公理中，共享内存并发程序的执行是否一致。对于诸如SC和TSO之类的内存模型，检查一致性是NP完整的。我们的框架表明，尽管使用细粒度复杂性的工具，可以通过使用硬度硬度，快速确定性的一致性算法。该框架基于一个通用的一致性问题，可以通过不同的内存模型实例化。我们为在时间o*（2^k）中运行的问题构建算法，其中k是检查中的执行中写入访问的数量，以确保一致性。然后，框架的每个实例都接受O*（2^k） - 时间一致性算法。通过应用框架，我们获得了SC，TSO，PSO和RMO的相应一致性算法。此外，我们表明，在细粒度上，获得的SC，TSO和PSO的算法是最佳的：除非指数时间假设失败，否则这些在时间2^o（k）中没有一致性算法。
We present a framework that provides deterministic consistency algorithms for given memory models. Such an algorithm checks whether the executions of a shared-memory concurrent program are consistent under the axioms defined by a model. For memory models like SC and TSO, checking consistency is NP-complete. Our framework shows, that despite the hardness, fast deterministic consistency algorithms can be obtained by employing tools from fine-grained complexity. The framework is based on a universal consistency problem which can be instantiated by different memory models. We construct an algorithm for the problem running in time O*(2^k), where k is the number of write accesses in the execution that is checked for consistency. Each instance of the framework then admits an O*(2^k)-time consistency algorithm. By applying the framework, we obtain corresponding consistency algorithms for SC, TSO, PSO, and RMO. Moreover, we show that the obtained algorithms for SC, TSO, and PSO are optimal in the fine-grained sense: there is no consistency algorithm for these running in time 2^o(k) unless the exponential time hypothesis fails.
