Decomposing Data Structure Commutativity Proofs with $m\!n$-Differencing
Decomposing Data Structure Commutativity Proofs with $m\!n$-Differencing
复制标题
用 $m!n$ 差分分解数据结构交换性证明
DOI：
10.1007/978-3-030-67067-2_5
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kshitij Bansal
中科院分区：
文献类型：
--
作者：
Eric Koskinen;Kshitij Bansal
。数据结构方法的交换性在并行化编译器、事务存储器、推测执行和软件可伸缩性等上下文中一直是人们感兴趣的问题。尽管有这样的兴趣，但我们缺乏有效的理论和技术来辅助交换性验证(fffiVersion)。在本文中，我们引入了一种新的分解来改进从数据结构实现中验证方法对交换性条件的任务。关键的使能洞察力--称为MN-differging-defi--使得抽象足够细粒度所需的精确度，使得抽象领域中的方法实现的交换性带来具体领域中的交换性，但可能不如全功能正确性所需的精确度。我们将这种分解结合到证明规则中，以及用于交换性验证的自动机理论归约中。fi。最后，我们讨论了我们的简单概念验证实现和实验结果，实验结果表明，Mn-diff建立导致了一些简单例子的更可伸缩的交换性验证。
. Commutativity of data structure methods is of ongoing interest in contexts such as parallelizing compilers, transactional memory, speculative execution and software scalability. Despite this interest, we lack effective theories and techniques to aid commutativity verification. In this paper, we introduce a novel decomposition to improve the task of verifying method-pair commutativity conditions from data structure implementations. The key enabling insight—called mn -differencing—defines the precision necessary for an abstraction to be fine-grained enough so that commutativity of method implementations in the abstract domain entails commutativity in the concrete domain, yet can be less precise than what is needed for full-functional correctness. We incorporate this decomposition into a proof rule, as well as an automata-theoretic reduction for commutativity verification. Finally, we discuss our simple proof-of-concept implementation and experimental results showing that mn - differencing leads to more scalable commutativity verification of some simple examples.
影响因子：
1.8
作者：
Houshmand, Farzin;Lesani, Mohsen
通讯作者：
Lesani, Mohsen