Concurrency and local reasoning under reverse exchange
Concurrency and local reasoning under reverse exchange
复制标题
反向交换下的并发与局部推理
DOI：
10.1016/j.scico.2013.07.006
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Möller
中科院分区：
文献类型：
--
作者：
H.-H. Dang;B. Möller
并发的很多方面都是通过顺序组合之间的不等式交换律（P⁎Q）；（R⁎S）⩽（P；R）⁎（Q；S）来体现；和并发组合⁎。特别是，最近的研究表明，在一定的语义定义下，该定律的有效性相当于我们熟悉的霍尔三元组并发规则的有效性。不幸的是，虽然该定律在并发克莱恩代数的标准模型中成立，但在基于关系的代数分离逻辑设置中并不成立。然而，我们表明，在温和条件下，逆不等式 (P; R)⁎(Q; S)⩽(P⁎ Q);(R⁎ S) 仍然成立。从这个反向交换法则中，我们得出了并发规则的稍微受限但仍然相当有用的变体。此外，使用相应的局部性定义，我们还获得了框架规则的变体，其中 ⁎ 现在被解释为分离合取。这些结果允许将关系设置也用于模块化和并发推理。最后，我们通过讨论该方法的几种变体来进一步解释结果。
Quite a number of aspects of concurrency are reflected by the inequational exchange law (P⁎ Q);(R⁎ S)⩽(P; R)⁎(Q; S) between sequential composition; and concurrent composition⁎. In particular, recent research has shown that, under a certain semantic definition, validity of this law is equivalent to that of the familiar concurrency rule for Hoare triples. Unfortunately, while the law holds in the standard model of concurrent Kleene algebra, its is not true in the relationally based setting of algebraic separation logic. However, we show that under mild conditions the reverse inequation (P; R)⁎(Q; S)⩽(P⁎ Q);(R⁎ S) still holds there. From this reverse exchange law we derive slightly restricted but still reasonably useful variants of the concurrency rule. Moreover, using a corresponding definition of locality, we obtain also a variant of the frame rule, where⁎ now is interpreted as separating conjunction. These results allow using the relational setting also for modular and concurrency reasoning. Finally, we interpret the results further by discussing several variations of the approach.
登录
查看更多内容
DOI：
10.1145/964001.964024
发表时间：
2004-01
期刊：
Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages
影响因子：
--
作者：
P. O'Hearn;Hongseok Yang;J. C. Reynolds
通讯作者：
P. O'Hearn;Hongseok Yang;J. C. Reynolds
DOI：
--
发表时间：
2011
期刊：
International Conference on Concurrency Theory
影响因子：
--
作者：
C. Hoare;A. Hussain;B. Möller;P. O'Hearn;R. Petersen;G. Struth
通讯作者：
G. Struth
代数分离逻辑
DOI：
--
发表时间：
2011
期刊：
J. Log. Algebraic Methods Program.
影响因子：
--
作者：
Han;P. Höfner;B. Möller
通讯作者：
B. Möller
克莱恩变得懒惰
影响因子：
1.3
作者：
B. Möller
通讯作者：
B. Möller
DOI：
--
发表时间：
2011
期刊：
J. Log. Algebraic Methods Program.
影响因子：
--
作者：
Tony Hoare;Bernhard Möller;G. Struth;Ian Wehrman
通讯作者：
Ian Wehrman